補数・負数の表現
補数
数値の各桁の重みの基本となる数を基数という。補数とは、与えられた数Aを、定められた数Bから引いた数のことである。
１．基数の補数―定められた数Bに、基数のべき乗を用いる。
K桁のN進数のNの補数：
２．基数-1の補数―定められた数Bに、基数のべき乗−1を用いる。
K桁のN進数のN-1の補数:
(例1)Aが10進数の100のときの補数
・10の補数：1,000-100=900
・9の補数：1,000-1-100=899
(例2)Aが2進数の00000110のときの補数
・2の補数：100000000-00000110=11111010
・1の補数：100000000-1-00000110=11111001
2進数の補数の求め方
１．1の補数―与えられた数Aのビットを反転する。
２．2の補数―1の補数に1を加える。
(例1)8桁の2進数00001111の1の補数は、反転させて11110000となる。
(例2)上の結果に1を加えると11110001となり、これが2の補数。
ちなみに直接2の補数を計算するには、たとえば00001111を考えるとき、9桁の100000000から引けばよい。
※基数−1の補数の定義である、K桁のN進数のN-1の補数:
(この例では、Nは2、Kは8、Aは00001111)より、まず
を計算したのが11111111というわけ。
負数の表現
・多くのコンピュータでは負数を2の歩数で表す。
・1番左のビットを符号ビットとする。(0：正かゼロ、1：負)
したがって、上の例を借りてくれば、2進数00001111(10進数で15)の2の補数11110001は-15となる。(例)10進数の35-13の計算
35を二進数に変換すると00100011となる。-13については、まず13を2進数に変換すると00001101となり、これを反転させて1を加えると11110011となる。これが-13である。
あふれた9桁目のビットは捨て、8ビットを残すと00010110。すなわち22となり、計算ができた。
負数を2の補数で表せば、値が成果付加を気にすることなく、加算回路で計算できる。
補数がちょっと分かりにくいのでチェック問題も解いてみた。
チェック問題：
問1．次の2進数の2の補数を示せ。
(1)01011100
(2)11101110問2．負数を2の補数で表すコンピュータで、10進数の-56の2進数表現は8ビットでいくらか。ただし、一番左のビットを符号ビットとし、1の場合が負である。
解答：
問1．反転させて1を加えればよい。
(1)反転させて10100011。1加えて10100100。
(2)反転させて00010001。1加えて00010010。問2．まず56の2進表現を求め、その数を反転させて1を加えればできあがり。
56の2進表現は8+16+32だから、つまり00111000。反転させて11000111。1加えて11001000。これが−56の2進表現である。
今日はここまで。補数と負数は初めはややこしい感じがしたけど、慣れるとそうでもないように思う。2進数の足し算引き算ができれば問題なし！
2進数、10進数、16進数
2進数から10進数への変換、16進数から10進数への変換などなどについて。
10進数 0 1 2 3 4 5 6 7 8 9 10
2進数 0 1 10 11 100 101 110 111 1000 1001 1010
10進数 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16進数 0 1 2 3 4 5 6 7 8 9 A B C D E F
2進数から10進数
二進数01101001を10進数に直すには、右から2のk-1乗(kは数字の数)で重み付けていけばよい。
0 1 1 0 1 0 0 1
128 64 32 16 8 4 2 1
64 +32 + 8 + 1 = 105
10進数から2進数
上と似たようなもの。重み付けを調整しながら足して求めたい値にすればよい。たとえば132なら128+4=+
、つまり1000100となる
16進数から10進数
これも16の(k-1)乗で重みをかけて足せばよい。たとえば16進数FEDCは
上の表より、
重み
4096 256 16 1
16進数 F E D C
10進数 15 14 13 12
10進数から16進数
10進数を16で割って商と余りを求め、商に対しても同様に繰り返す。
商が0となったときの余りFから順に数え、その結果がFEDC。
余り 12 -> C
余り 13 -> D
余り 14 -> E
余り 15 -> F
2進数から16進数
右側から4桁ずつ区切って、1桁の16進数に直す。たとえば2進数10100111は、
よりA7
8 4 2 1 8 4 2 1
1 0 1 0 | 0 1 1 1
(8+2=10)->A (4+2+1=7)->7
16進数から2進数
16進数を1桁ずつ4桁の2進数に直す。たとえば16進数9Eは、
8 4 2 1 8 4 2 1
1 0 0 1 | 1 1 1 0
ここまで〜。2進数、10進数、16進数の変換は大事そうだからよく覚えておいた方が良さそうな気がするな。
アルゴリズムの正しさ
プログラムの勉強をしていると必ずぶつかるのがアルゴリズムという言葉。このアルゴリズムとは一体何なのかというと、問題を解くための手順を定めたものだ。この手順をきちんと定めればコンピュータに問題を解かせることができる(もちろんアルゴリズムはコンピュータに限った話ではないけど)。
ここで、どういうアルゴリズムが正しいアルゴリズムなのかということを知らなくちゃいけない。正しいアルゴリズムの条件とは次のようなものだ
(1)どんな入力データに対しても間違った答を与えないこと、言い換えると、答を与える場合にはその答が正しいこと。
(2)どんな入力データに対しても有限の時間で答を与えること、すなわち、計算を完了すること。
つまり、アルゴリズムが出す答は正しくなければならず、かつそれが本当に答を出すことを保証していなければならない。
アルゴリズムの証明の方法
プログラムの中の特定の場所で変数の値の間に成立する条件式を表明(assertion)、ループの中で回るたびに常に成立している表明のことをループ不変条件(loop invariant)という。アルゴリズムの正しさを証明する基本的な手法は、ループ不変条件の成立を示すことだ。
例)ユークリッドの互除法
ステップ1：mをnで割って、余りをrとする。
ステップ2：r=0であれば、アルゴリズムは終了する。このときnが最大公約数である。
ステップ3：m<--nとする。次にn<--rとして、ステップ1に戻る。
たとえば、36と14の最大公約数をユークリッドの互除法を用いて求めると下のようになる。これは上のステップを繰り返し適用して求めたものだが、繰り返しの手順を経ても、最大公約数は変化しない。これがループ不変条件。
m n 商 r
- -
36 / 14 = 2 … 8 <--36と14の最大公約数は2
14 / 8 = 1 … 6 <--14と8の最大公約数は2
8 / 6 = 1 … 2 <--8と6 〃
6 / 2 = 3 … 0 <--6と2 〃
ループ不変条件が成立することを証明するには、次の2つのことを確認する。
(1)繰り返しが始まる直前にこの条件が成立していること。
(2)この条件が成立している時に繰り返しを1回進めると、再び条件が成立すること。
これはちょうど数学的帰納法による証明と同じである。
・・・と、いまアルゴリズムについて勉強しているので書いてみた。
参考文献：
アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学 3)
- 作者: 石畑清
- 出版社/メーカー: 岩波書店
- 発売日: 1989/03/30
- メディア: 単行本
- 購入: 10人 クリック: 83回
- この商品を含むブログ (17件) を見る
勉強その2
毎日少しずつ勉強。継続が肝心だ(｀・ω・´)
コンピュータの種類
１．マイクロコンピュータ(マイコン)
・1個から数個のLSI(大規模集積回路)で構成される処理装置を家電製品や自動車などに組み込み、制御に用いる小さなコンピュータ。
２．パーソナルコンピュータ(パソコン)
・マイクロコンピュータを組み込んで、個人利用をおおな目的として開発されたコンピュータ。
３．ワークステーション(WS)
・高解像度ディスプレイを備え、パソコンよりも高速な処理能力を持ち、通常ネットワーク携帯で利用される業務目的の個人用コンピュータ。
・LAN(Local Area Network)やインターネット環境では、サーバとして利用されることも多い。
・研究やプログラム開発など、主として技術者(エンジニア)が使うものを、エンジニアリング・ワークステーション(EWS)と呼ぶ。
４．汎用コンピュータ(メインフレーム)
・事務計算から科学技術計算まで、幅広い分野で利用できる高度な処理能力を持つコンピュータ。
・ホストコンピュータとして、複数の端末装置を接続して共同利用する。
５．スーパーコンピュータ
・原子力発電所や気象予測など、膨大な科学技術計算を極めて短時間で行える、超高速な汎用コンピュータ。
コンピュータの構成
コンピュータの五大装置
１．制御装置―主記憶装置上の命令に従って、各装置を制御する。
２．演算装置―各種演算を行い、結果を主記憶装置に格納する。
３．主記憶装置(main storageまたはメインメモリ(main memory))―データやプログラムを記憶する。
４．入力装置―データやプログラムを主記憶装置に読み込む。
５．出力装置―主記憶装置上のデータを外部に送り出す。
・処理装置とは、制御装置と演算装置、あるいは主記憶装置までを含めた総称。
・周辺装置とは、入力装置、出力装置、補助記憶装置の総称。
・パソコンでは、制御装置と演算装置の機能が1つのLSIに組み込まれており、このLSIをMPU(Micro Processing Unit)、あるいはCPU(Central Processing Unit)と呼ぶ。
・主記憶装置の情報は電源を切ると消えてしまうので、データを保存するのにハードディスクなどの補助記憶装置を用いる。補助記憶装置は、データを読み書きする速度は遅いが、主記憶装置よりも大きな記憶容量を持つ。
今日はここまで。目標は毎日継続だ。
勉強その1
基本情報技術者試験を受けることにしたので、気が変わらないうちに早速今日勉強したことを書いてみる。
ちなみに教材はこれ
基本情報「午前」完全合格教本〈2007年度版〉 (情報処理技術者試験)
- 作者: 福嶋宏訓
- 出版社/メーカー: 新星出版社
- 発売日: 2006/12
- メディア: 単行本
- この商品を含むブログ (1件) を見る
コンピュータの機能
・ハードウェアとソフトウェア
ハードウェア―物理的な装置。簡単に言えばコンピュータの機械の部分のこと。
ソフトウェア―ハードウェアを動かすためのプログラムのこと。設計書やマニュアルなども含む。
・コンピュータの特徴
１．高速性―超高速演算ができる
２．正確性―常に安定した結果を出す
３．記憶性―大量にデータを管理できる
４．汎用性―活用分野が広い
汎用性があるおかげで、一台のパソコンでワープロが打てたりゲームができたりインターネットができたりするわけ。
コンピュータの利用
コンピュータで行う仕事を処理という。
・利用形態の分類
１．定型処理―決められた手順で繰り返し行う処理のこと。文字通りに「型で定まった処理(を繰り返す)」と考えてみるとちょっと覚えやすい気がする。
２．非定型処理―毎回異なる手順で行う処理のこと。ワープロでの文書作成などがその例。
・企業の情報処理システム
１．オフィス・オートメーション(OA)―事務処理の自動化
２．ファクトリ・オートメーション(FA)―工場の自動化
３．EUC(End User Computing)―エンドユーザ(利用者)が自らコンピュータを活用する
４．EUD(End User Development)―エンドユーザが情報処理システムを開発する
・ネットワークで広がる利用価値
１．集中処理型のネットワーク―1台のホストコンピュータが集中制御する。たとえば銀行のオンラインシステムなど。
２．分散処理型のネットワーク―複数のコンピュータが互いに協調制御する。たとえばインターネットなど。
・身近な情報処理システムの例
銀行のCDやATM、電子商取引などなどいっぱいある。
今日はここまで。試験は4月だからあとおよそ4ヶ月ある。まあまだ時間はあるけど。直前にあせって徹夜で勉強するってのは嫌だからちょっとづつ勉強を進めていこうと思う。
