情報システム演習 (2016) 第2回

情報の基礎理論 2/2

情報の基礎理論1/2に続いて,情報基礎理論2/2では教科書「平成28年度 イメージ&クレバー方式でよくわかる栢木先生の基本情報技術者教室 (情報処理技術者試験)」第1章の残り半分を勉強します.主な内容は

  • 半加算器と全加算器
  • 補数表現と固定小数点表示
  • 浮動小数点表示
  • 誤差
  • シフト演算
  • オートマトン

です.が,最後のオートマトンは適切なタイミングになるまで後回しにします.

半加算器

前回の情報の基礎理論1/2の後半で見たとおり,2進数1桁の足し算の結果は一般に2桁で,

0+0=00
0+1=01
1+0=01
1+1=10

でした.これらの右辺を1桁目と2桁目に分解します.まず1桁目です.

0+0=0 (1桁目)
0+1=1 (1桁目)
1+0=1 (1桁目)
1+1=0 (1桁目)

これは前回見たとおりXORというルールでした.そこで1桁目を

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

という風に書くことにします.これをまとめて

A XOR B = Q1

という風に書くことにしましょう.次に2桁目を見てみます.

0+0=0 (2桁目)
0+1=0 (2桁目)
1+0=0 (2桁目)
1+1=1 (2桁目)

これは前回見たANDルールでした.そこで2桁目を

0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

という風に書くことにします.これをまとめて

A AND B = Q2

と書きます.二つの入力 A, B に対して結果 Q1, Q2 を求める操作を半加算と言います.半加算器の動作をまとめると次のようになります.このような表は真理値表と言います.

半加算器

全加算器

半加算器は2進数1桁同士の足し算しか出来ませんでした.もし半加算器が隣の桁からの繰り上げを受け付けるなら,それを桁数分並べて任意の桁数の加算器が作れます.この繰り上げを受け付ける半加算器のことを全加算器と呼びます.

半加算器とは,2進数1桁の数値Aと2進数1桁の数値Bとから,ABの和の1桁目Q1と2桁目Q2を計算する器械でした.全加算器はこれに加えて,下の桁からの繰り上げCを受け付けます.

全加算器の真理値表は次のようになります.

全加算器

補数表現

全加算器によって足し算が出来るようになりました.では引き算はどうしたらいいでしょうか?ここで10進数で7–4を考えてみます.ストレートに7–4を計算するのではなく,次のように考えます.

7–4=7–(10–6)=7+6–10

計算をわざわざ難しくしただけにも見えますが,よく考えてみると10の部分は十分大きな数であれば任意でよく,かつ固定できます.引き算に関係する部分はこの任意の数だけですから,ここだけ特別な計算をすればあとは足し算だけです.

次に4から6を導く部分ですが,これは10の補数表現と言います.10進数1桁ではたかだか10個の補数表現があれば十分ですから,これは引き算ではなくて記憶の問題です.(桁数が多い場合は10の補数ではなく9の補数を使うとより便利です.自分で確かめてみましょう.)

これを2進数で行ったのが2の補数表現です.

2の補数表現は負数を表す方法としてもよく使われます.特に2の補数表現が優れているのは,桁数が予め決まっている場合,2進数の最上位ビットを調べれば正負がわかることです.負数の場合,最上位ビットは必ず1になります.

固定小数点表示

負数は2の補数表現で表現出来ました.では小数(実数)はどうでしょうか?

厳密な意味では,デジタル計算機は実数を扱うことが出来ません.扱えるのは整数だけです.そこで,例えば下から2桁は必ず小数というふうに決めて,小数を含む数を扱うことがあります.10進数で言えば,1234と書いて12.34のことと決めておくようなものです.これを固定小数点表示と言います.小数点以下が0の場合,例えば12.00は1200と表現します.これは簡単ですね.

浮動小数点表示

固定小数点表示は簡単な反面,融通が効きません.例えば0.000123と456000は同じく有効数字3桁ですが,両方を同時に固定小数点表示をするためには000000.000123と456000.000000のように12桁が必要になります.

そこで

0.000123 = 1.23 / 10000
456000 = 4.56 * 100000

という風に考えましょう.これをそれぞれ

0.000123 = 1.23E–4
456000 = 4.56E5

という風に書きます.1.23や4.56のようなEよりも前の部分を仮数部と言います.Eよりも後ろの,小数点の位置を表す数を指数部と言います.このように実数を仮数部と指数部に分けて表示したものを浮動小数点表示と言います.

誤差

浮動小数点表示をしたところで,計算機が扱える桁数は有限です.しかし,実数は本来は無限の桁数を持っています.つまり,何がしかの実数を計算機で扱おうとすると,一般に真の値と計算機内部での値とに誤差が出てしまいます.

誤差が生じる理由はこれだけではありません.講義では以下の誤差についても説明します.

  • 桁あふれ誤差
  • 丸め誤差
  • 桁落ち
  • 情報落ち
  • 打切り誤差

さて,あとはシフト演算ですね.

シフト演算

まずは論理シフト演算というシフト演算を見てみましょう.シフト演算には左論理シフト演算と右論理シフト演算があります.

いま2進数011101があるとします.これを1桁,つまり1ビット左にずらして,左端に0を入れてみます.つまり

011101 → 0111010

とします.一番左,すなわち一番小さな桁に0を挿入し,全体を左に1ビットシフトさせました.この時,桁数が元の桁数よりもひとつ大きくなってしまいますから,普通は一番左のビットを捨ててしまいます.つまり

011101 → 111010

とします.これが左シフト演算でした.

右シフト演算は左シフト演算の逆で,2進数全体を1ビット右にずらします.一番右のビットは捨ててしまい,左端に0をつけます.例えばこんな感じです.

011101 → 001110

シフト演算は何の役に立つのでしょうか?まず,左シフト演算に着目すると,ビット全体を左にひとつずらすことは,数値を2倍にすることと同じなので,2倍の掛け算のかわりに左シフト演算が使えることがわかります.

実はシフト演算は非常に高速に計算出来るため,掛け算のかわりに使えるケースではシフト演算が使われます.同じく右シフト演算は数値を1/2にするのに使えます.

ただし,論理シフト演算で2倍,1/2倍が出来るのは,正の整数だけです.2の補数表現を使っている場合,負数の最上位ビットは必ず1になるのでした.そこで,最上位ビットだけは手を付けずに,残りのビットを左シフトする算術左シフト演算が考えだされました.算術左シフト演算は次のような感じで働きます.

011101 → 011010

算術左シフト演算とは逆に,右方向にシフトする算術右シフト演算もあります.算術右シフト演算は最上位ビットは手を付けずに,右シフトによって出来る隙間には最上位ビットと同じ数字を埋めます.例えばこんな感じです.

011101 → 001110

ここらへんはどうしても紙面では表現しにくいので,ホワイトボードで説明します.(いずれアニメーション素材を探すか作るかするとしましょう.)

Show your support

Clapping shows how much you appreciated Ichi Kanaya’s story.