计算机理论入门03
- 1. 計算機理論入門 3 2012 年度後期 垂水共之 tarumi@ems.okayama-u.ac.jp 20121003 20121017 講義終了後、誤植を修正
- 2. 2 進数、 8 進数、 10 進数、 16 進数 ? 10 進数 – ０から９まで 10 種類の「文字」を使い １０のベキ乗で位取り 例１） １ ２ ３ ＝ １ × １０２ ＋ ２ × １０１ ＋ ３ × １００ ↑ ↑ ↑ 10 ２ 10 １ 10 ０ の の の （例２） １ ０ １ ＝ １ × ２ ＋ ０ × ２ ＋ １ × ２ ２ １ 位 位 位 ↑ ↑ ↑ ＝ ４ ＋ ０ ＋ １ ２２ ２１ ２０ の の の 位 位 位 ? ２進数 – ０と１の 2 種類の「文字」を使い ２のベキ乗で位取り – 電気の Off 、 On に対応して０，１ – ビット (bit) ０，１の 2 つの状態しか取れない情 報の単位
- 3. 進数表記 ? １０１ – 10 進数？ – ２ 進数？ ? １０１ (10) ? １０１ (2) ? ああ
- 4. １０進２進変換（その１ 整数の場合） ? 2 進数 to １０進数 – （位取り）２進数の各桁に２の対応するベキ乗をかけて加える ｂｎ ｂｎ－１…ｂ２ ｂ１ ｂ０ ＝ ｂｎ × ２ｎ＋ｂｎ－１ × ２ｎ－１＋…＋ｂ２ × ２２＋ｂ１ × ２１＋ｂ０ × ２０ ここにｂｎ，ｂｎ－１，…，ｂ２，ｂ１，ｂ０は０か１． ? 10 進数 to ２進数 – １０進数の値を２で割ってその余りを，商が０になるまで求め て行く – 上の式の両辺を２で割れば、 1 桁右にずれて ｂｎ ｂｎ－１…ｂ２ ｂ１ ｂ０ ÷ ２ ＝ ｂｎ ｂｎ－１…ｂ２ ｂ１ 余り ｂ０ ｂｎ × ２ｎ ＋ｂｎ－１ × ２ｎ－１＋…＋ｂ２ × ２２＋ｂ１ × ２１＋ｂ０ × ２０ ÷ ２ ＝ ｂｎ × ２ｎ－１＋ｂｎ－１ × ２ｎ－２＋…＋ｂ２ × ２１＋ｂ１ × ２０ 余り ｂ０
- 5. ａ０を与えられた１０進数としたとき， ａ１ ＝ ａ０ ÷ ２ ＋ ｂ０ ａ２ ＝ ａ１ ÷ ２ ＋ ｂ１ ： ａｎ ＝ ａｎ－１ ÷ ２ ＋ ｂｎ－１ ａｎ＋１ ＝ ａｎ ÷ ２ ＋ ｂｎ ここに ｂｉ（ｉ＝０，１，…，ｎ）は０か１，ａｎ＋１＝０ とする。 このとき， ａ０（１０）＝ｂｎ ｂｎ－１ …ｂ２ ｂ１ ｂ０（２） となる。
- 6. 例 3 10 進数の１２３を 2 進数へ変換 ２）１２３ ２）６１ ．．．１（＝ｂ０） ２）３０ ．．．１（＝ｂ１） ２）１５ ．．．０（＝ｂ２） ２）７ ．．．１（＝ｂ３） ２）３ ．．．１（＝ｂ４） ２）１ ．．．１（＝ｂ５） ０ ．．．１（＝ｂ６） よって １２３（１０） ＝ １１１１０１１（２）
- 7. １０進２進変換（その２ 純小数 （整数部の無い） の場合） ? ２進数から１０進数に変換するには，下のように２進数 の各桁に２の対応するベキ乗をかけて加えればよい。一 般には次式で表される。 ０．ｂ－１ｂ－２ｂ－３……………（２） ＝ ｂ－１ × ２－１＋ｂ－２ × ２－２＋ｂ－３ × ２－３……………（１０） ここにｂ -1 ，ｂ -2 ，…，ｂ -(n-1) ，ｂ -n は０か１ ? この式の両辺を２倍すると小数点の位置が一桁右にずれ ｂ－１．ｂ－２ｂ－３……………（２） ＝ ｂ－１＋ｂ－２ × ２－１＋ｂ－３ × ２－２……………（１０） ? となり、整数部にｂ－１が浮かび上がってくる。整数部の ｂ－１を横に置いて、 ０．ｂ－２ｂ－３……………（２） ＝ ｂ－２ × ２－１＋ｂ－３ × ２－２……………（１０）
- 8. （例４） ０．１ （１０） を２進数に変換する。 ０．１ × ２ ｜－－－－－－－－－－－－－－－－－－－－－－－ ０．２ ｜ × ２ ｜｜－－－－－－－－－－－－－－－－－－－－－－ ０．４ ｜｜ × ２ ｜｜｜－－－－－－－－－－－－－－－－－－－－－ ０．８ ｜｜｜ × ２ ｜｜｜｜－－－－－－－－－－－－－－－－－－－－ １．６ ｜｜｜｜ × ２ ｜｜｜｜｜－－－－－－－－－－－－－－－－－－－ １．２ ｜｜｜｜｜ × ２ ｜｜｜｜｜｜－－－－－－－－－－－－－－－－－－ ０．４ ↓↓↓↓↓↓ ０．０００１１０…………… ? 以下同様に行えば、 0011 が繰り返す循環小数とな る ０．１（１０） ＝ ０．０００１１（２）
- 9. 一般の小数の場合 ? 整数部と小数部とに分け、 各々に上記の方法で変換すればよい。 ? 整数部 – ２で割った余りを ? 小数部 – ２を掛けた整数部を
- 10. 8 進数、 16 進数 ? １０進数を２進数に変換すると，桁数が多くる。 ? このため３個ずつ区切って８進数（２３＝８）で表現す ることも多い。 （例５） １ | １１１ | ０１１（２） ＝ １７３（８） ＝ １ × ８２＋７ × ８１＋３ × ８０ ? 近年は別の理由から４個づつ対応させて１６進数（２４ ＝１６）で表現することが多い。 – １６進数では１つの桁を表すのに１６種類の文字がいるので， ０，１，…，９，Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆを用いている。 （例６） １１１ | １０１１（２） ＝ ７Ｂ（１６） ＝ ７ × １６１＋１３ × １６０
- 11. 進数変換 １０進数 ２進数 ８進数 １６進数 ０ ００００ ００ ０ ? 【注意】８進数、１ １ ０００１ ０１ １ ６進数に変換する場 ２ ００１０ ０２ ２ ３ ００１１ ０３ ３ 合、２進数を経由し ４ ０１００ ０４ ４ なくてもよい。 ５ ０１０１ ０５ ５ ? １０進２進の変換方 ６ ０１１０ ０６ ６ ７ ０１１１ ０７ ７ 法で２をかけたり、 ８ １０００ １０ ８ ２で割ったりすると ９ １００１ １１ ９ ころで、２の代わり １０ １０１０ １２ Ａ １１ １０１１ １３ Ｂ に８、または１６を １２ １１００ １４ Ｃ 用い、余り、または １３ １１０１ １５ Ｄ 整数部を取り出せば １４ １１１０ １６ Ｅ １５ １１１１ １７ Ｆ よい。
- 12. ビット、バイト、語 ? ビット（ｂｉｔ） – 計算機の最小記憶単位であり，１ビットで０，１の２種類の状 態を表現する。 ? バイト（Ｂｙｔｅ） – 文字の記憶単位であり，昔の計算機では１つの文字を表現する のに６ビットを用いるものが多かったが，近年の計算機では１ つの文字を表現するのに８ビット又は９ビットを用いている。 これをバイトという。 ? ニブル（ nibble ） – 最近は１Ｂ＝８ bits のマシンが増え、 16 進数で表現する機会が 増えてきた。このため 16 進数一桁に対応する 4bits を「ニブル 」という。
- 13. ? 語 word – 数値の記憶単位であり，そのビット数は機種によりまちまちで ある。近年のマイコンを除き次のような数の機種がある。 – １語 ＝ １６ビット – ＝ ３２ – ＝ ３６ – ＝ ４８ – ＝ ６０ – 以前は小型，中型では１６ビット（＝２バイト）、大型では３ ２ビット（＝４バイト）以上と分かれていたが、近年では３２ ビットが普通になった。昨年あたりから６４ビットが普及し始 めている。 – 以下の例では１バイト＝８ビット，１語＝１６ビット＝２バイ トで述べることが多い。
- 14. 数値の表現形式 ? 数値の記憶単位である「語」の中に、実際の値をどのよ うに格納するか、それが「数値の表現形式」である。 – 固定小数点形式 fixed binary – 浮动小数点形式 flowting binary – 10 進数形式 BCD = binary coded decimal ? よく用いられるのは上の２つ、固定小数点形式と浮動小 数点形式である。
- 15. 固定小数点形式 fixed binary ? 小数点の位置が固定された表現形式 ‥‥通常，最右桁の次に小数点の位置を仮定する‥‥ であり，通常整数値に用いる。 （例１） ７の固定小数点表現 ０００００００００００００１１１ ↑ ここに小数点を仮定する
- 16. 浮动小数点形式 flowting binary ? 固定小数点形式では小数点の位置が固定されているため 通常の実数（少数）を表現できない。 ? このため１０進数の精度表現で用いたように １５００ と ０ . １５ × １０ 4 小数と１０のベキ乗の積という形と似た形式で表現する のが浮动小数点形式である。計算機では１０のベキ乗と は限らず一般には ０．ｍ 1 ｍ 2 ??? × ｂｅ 1 ｅ 2 ??? （例えば，０．１１０１ (2) × ２ 11(2) ＝ １１０．１ (2) ＝ ６ ．５ (10) ） という形式で表す。ここで ｍ 1 ｍ 2 ??? の部分を〈仮数部〉， ｅ 1 ｅ 2 ??? の部分を〈指数部〉， ｂ を〈底〉という。
- 17. つづき （例２） ０．１１０１（２） × ２１１（２） の浮動小数点表現 ???００１１ | ０ | １１０１??? 指数部 ↑ 仮数部 この位置を仮の小数点（仮想小数点）という。
- 18. 負数の表現形式 ? この節では固定小数点に限って話しをしていく – 浮動小数点のときには，仮数部の負数の表現形式と考えればよ い ? 正整数の固定小数点形式表現は前節で述べた通りで ? 負の整数はどのように表現したらよいか考えてみよう。 ? 符号付き絶対値表現 ? 下駄上げ表現 ? ２の補数表現
- 19. 符号付き絶対値表現 ? １語を構成するｂｉｔ列のうち，特定のビットが符号を 表すことにする。 ? 通常第０ビットを符号に用い，オフ（０）のとき 正 又は 零，オン（１）のとき 負を表す。 ? 残りのビットは符号を除いた絶対値を固定小数点形式で 表現する。 （例１） １０（１０） ＝ ００００００００００００１０１０（２） ↑ 正 －１０（１０） ＝１０００００００００００１０１０（２） ↑ 負
- 20. 下駄上げ表現 ? 負数の表現形式の一つとして、「下駄はかせ」の方式が ある。いわゆるテストの点数に下駄を履かせて成績を付 けるやつである。テストの点数の場合には０点から１０ ０点までの値しかなく、下駄を例えば３０点とすれば、 テストの生点に３０点加えたものが成績の点数になる。 ? 計算機の値の表現の場合も考え方は同じで、表現したい 生の値に「下駄」の値を加えた値を，内部的に表現する ことにする。「下駄」の値としては最左端ビットだけを １にしたもの（１語ｎビットの場合 ２ n-1 ）を用いるの が普通である。
- 21. 下駄上げ表現（つづき） １００ (10) ＝１１００１００ (2) をあらわす場合、 ０００００００００１１００１００ ＋）１０００００００００００００００ ( 下駄 ) １００００００００１１００１００ －１００ (10) では １０００００００００００００００ ( 下駄 ) －）０００００００００１１００１００ ０１１１１１１１１００１１１００ ? 結果的に最左端ビットが符号を表すことになり、０ の時負、１の時正の値を表す。 ? この下駄上げ表現は「浮動小数点」の「指数部」 の表現として使われることが多い。
- 22. ２の補数表現 ? 与えられた負数の絶対値を固定小数点表現したものを， 各ビットの０，１を反転し（“１の補数”という）， その値に１を加える（“２の補数”という） ? これを，与えられた負数の表現形式とするものであり， 結果として第０ビットが符号を表す。 （例２） －１０（１０）の“２の補数表現” 絶対値 （＋１０（１０）） ００００００００００００１０１０ ビット反転（１の補数） １１１１１１１１１１１１０１０１ １加える （２の補数） １１１１１１１１１１１１０１１０ ? 負数の絶対値の求め方 与えられた負数 １１１１１１１１１１１１０１１０ ビット反転 ００００００００００００１００１ １加える ００００００００００００１０１０
- 23. ? 計算機では２の補数表現が使われる。 ? 符号付き絶対値表現では 2 つの値の足し算は、符号が （＋、＋）、（＋、－）、（－、＋）、（－、－） に応じて処理する必要があつ。 ? ２の補数表現の時には２つの値の符号を考えずに、単純 に足し算を行えばよい。 ? このことを、例で見ていこう。
- 24. 例３） ５ ＋ １０ ＝ １５ ０００００００００００００１０１ ＋） ００００００００００００１０１０ ００００００００００００１１１１ 例４） ５ ＋ （－１０） ＝ －５ ０００００００００００００１０１ ＋） １１１１１１１１１１１１０１１０ １１１１１１１１１１１１１０１１ （例５） （－５） ＋ １０ ＝ ５ （例６） （－５） ＋ （－１０） ＝ －１ １１１１１１１１１１１１１０１１ １１１１１１１１１１１１１０１ ＋） ００００００００００００１０１０ ＋） １１１１１１１１１１１１０１１ １０００００００００００００１０１ １１１１１１１１１１１１１０００ ↑ ↑ はみ出した部分は無視する はみ出した部分は無視する
- 25. 練習問題 ? 問１ 10 進数の１２３．６７５を 2 進数、 8 進数、 16 進数に変換しよう。 ? 問２ 10 進数のー１２３を 2 進数、 8 進数、 16 進数に 変換しよう。 ? 問３ なぜ ２の補数表現，１の補数表現と呼ばれるか 浮動小数点の仮数部に適用して考えよ。 ? 問４ １語のビット数をｎとしたとき符号つき絶対値表 現，２の補数表現とでは，各々どのような値の範囲を表 現できるか？
- 26. 単位 ＫＭＧＴＰＥ ? 計算機では２進数が使われるため、２の巾乗で数えるこ とが多い。２の１０乗が１０２４と１０００に近いため 、計算機の世界では２ 10 を１Ｋ（キロ）として取り扱う 。すなわち、 １Ｋ（キ ロ） ＝ ２１０ ＝ ２１０ （千） １Ｍ（メ ガ） ＝ ２１０Ｋ ＝ ２２０ （百万） １Ｇ（ギ ガ） ＝ ２１０Ｍ ＝ ２３０ （十億） １Ｔ（テ ラ） ＝ ２１０Ｇ ＝ ２４０ （一兆） １Ｐ（ペ タ） ＝ ２１０Ｔ ＝ ２５０ （千兆） １Ｅ（エクサ） ＝ ２１０Ｐ ＝ ２６０ （百京）
- 27. 浮動小数点の表現 ? IEEE754 交換形式 – 符号ビット – 指数部 ? 下駄上げ表現 – 仮数部 ? 絶対値表現
- 28. 32bits 単精度 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 符 指数部（ 8 ビット） 仮数部（ 23 ビット、ケチ表現） 号 ? 指数部 – 下駄 01111111 – 1 ～ 254 – 0 のとき、仮数部０であればゼロ – 255 のとき、無限大（仮数部０）、または NaN （仮数部 非 ０） ? 仮数部 – 絶対値表現 – 1.xxxx に正規化し、頭の１は記録しない 64bits 倍精度 128bits4 倍精度 指数部 11 ビット 指数部 15 ビット 仮数部 52 ビット 仮数部 112 ビット
- 29. 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 符 指数部（ 8 ビット） 仮数部（ 23 ビット、ケチ表現） 号 3 F 8 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3F800000 10 進数に直すと？ 10 進数の -118.625 はどんなビット配列になるかな？