ドパベン！
← 記事一覧へ戻る

シリーズ「コンピュータの計算のしくみ」 第1回

回路が「足す」とは？

電卓は答えを知っているのか

電卓に 7 と 8 を入れて「＋」を押すと 15 が出る。 これは当たり前に見えるが、電卓の中に「7 + 8 = 15」と対応付けられた表が入っているわけではない。 もしすべての答えを表にして持っておくとしたら、桁が増えるたびに表は爆発的に大きくなる。 ちなみに、一般的な電卓でよく使われている12 桁どうしの足し算までを表にするには、2.1ヨタバイト必要だ。 ヨタバイトという聞きなれない単位ではどのくらいか想像しづらいだろう。そこでこれをMP3の音楽データに換算してみよう。 なんと約４兆年ほどのデータになる。ビッグバンが起こったのは約１３８億年前だから…今までの宇宙の歴史を３００回繰り返すことでようやく１周聞き終えられるということになるのだ…！

流石に電卓にそんな大容量が入るとは思えない。では、代わりに何をしているのだろう。私たちが小学校で習った筆算を思い出してほしい。 筆算では、どんなに大きな数でも、やっていることは1 桁の足し算と繰り上がりだけだ。 一の位を足して、繰り上がったら十の位に 1 を送る。それを桁の数だけ繰り返す。

つまり足し算の正体は「 1 桁の足し算の組み合わせ 」である。 ならば回路も、まずは 1 桁を足せればいい。その最小の仕組みが 半加算器 だ。 例によって、まず触ってみてほしい。

半加算器 シミュレータ

A・B のスイッチをクリックして、2 つの数を足してみてください

XORANDA0B0和繰り上がり

0 + 0 = 0

押して、確かめる

上の回路には A と B の 2 つのスイッチと、「和」「繰り上がり」の 2 つのランプがある。 A と B が、足したい 2 つの数だ。0 か 1 しか入れられない。

  • A も B も 0 のとき。和は消えたまま。0 + 0 = 0。
  • A だけ 1 にすると、和が点く。1 + 0 = 1。
  • B だけ 1 にしても、和が点く。0 + 1 = 1。
  • そして A も B も 1 にすると——和は消える。代わりに「繰り上がり」が点く。

最後の 1 つで手が止まったかもしれない。 1 + 1 なのに、和のランプは消えてしまった。壊れているわけではない。 消えた分は、隣の「繰り上がり」に移っている。

消えた 1 はどこへ行ったのか

ここで、私たちが普段使っている数の書き方を思い出してほしい。 9 + 1 を筆算するとき、一の位はどうなるだろうか。 10 と書きたいところだが、一の位に「10」という数字は入らない。 私たちが使える数字は 0 から 9 までの 10 個しかなく、9 の次に書ける数字がもう無いからだ。 だから一の位を 0 に戻し、代わりに十の位へ 1 を送る。それが「10」という書き方である。

回路の世界では、使える数字がもっと少ない。0 と 1 の 2 個だけだ。 ということは、1 の次で早くも数字が尽きる。 やることは十進法のときと同じで、その桁を 0 に戻し、上の桁へ 1 を送るしかない。 書くと「10」。ただし読み方は「ジュウ」ではなく「イチゼロ」で、十進法でいう 2 のことだ。

つまり、和のランプが消えたのは計算に失敗したからではない。桁が上がったからだ。 消えた 1 は無くなったのではなく、隣の「繰り上がり」のランプに移っている。 シミュレータの下に出ている式が、そのまま 1 + 1 = 10 になっているのを確かめてほしい。

前回、コンピュータは 0 と 1 の世界で考えていると書いた。 数字が 2 個しかないというのは一見不便だが、足し算に関してはむしろ話が早い。 1 桁の足し算で起こりうる組み合わせは、たった 4 通りしかないのだから。

2 つのランプの正体

和のランプにつながっているゲートは XOR、繰り上がりのランプにつながっているのは AND という。 どちらも NOR と同じで、前の状態を覚えたりはしない。入力だけで出力が決まる。

XOR は、入力が食い違っているときだけ 1 になる。

入力1入力2出力
000
011
101
110

AND は、入力が両方とも 1 のときだけ 1 になる。

入力1入力2出力
000
010
100
111

XOR は eXclusive OR、日本語では排他的論理和という。OR（どちらか一方でも 1 なら 1）から 「両方とも 1」の場合だけを除いたもの、と読むとわかりやすい。

なぜこの 2 つで足し算になるのか

さきほど「1 桁の足し算は 4 通りしかない」と書いた。その 4 通りを表にしてみよう。 答えは 2 つの欄に分けて書く。その桁に残る数（和）と、上の桁へ送る数（繰り上がり）だ。

AB和繰り上がり
0000
0110
1010
1101

そのうえで、ひとつ上に戻って XOR と AND の表をもう一度見てほしい。

「和」の列は、XOR の出力の列とまったく同じである。

「繰り上がり」の列は、AND の出力の列とまったく同じである。

順番を間違えないでほしい。 誰かが「足し算をする回路」を思いついて、その中身として XOR と AND を選んだ——のではない。 XOR も AND も、足し算とは何の関係もなく、ただ入力に対して決まった出力を返すだけの部品だ。 その振る舞いが、たまたま 1 桁の足し算の答えと一致していた。 だから 2 つ並べて置くだけで、この回路は足し算をしているように見える。

回路は足し算を理解していない。理解していないのに、答えは合っている。

なお、この回路には前回のようなフィードバックがない。 上級モードにチェックを入れて確かめてみてほしい。 スイッチを変えた直後はまだランプが変わらず、「1ステップ進む」を1回押すと出力が追いつく。 そこで終わりだ。SR ラッチのように信号が回り続けることはない。 入力が決まれば出力が決まる。この回路は、前の状態を覚えていない。

これでは足りない

ところで、この回路の名前には「半」という字がついている。半加算器。何が半分なのだろうか。

もう一度、筆算に戻ってほしい。今度は 2 桁の足し算だ。 一の位はこれまでどおり、2 つの数を足せばいい。ここは半加算器の出番である。 では十の位はどうか。十の位にある 2 つの数を足す——だけでは済まない。 一の位から上がってきた繰り上がりも足さなければならない。 足す数が 3 つあるのだ。

ところが半加算器の入力は 2 本しかない。 繰り上がりを送り出すことはできるのに、受け取ることができない。 つまりこの回路が担当できるのは、一番下の桁だけだ。「半」とはそういう意味である。

ならば入力を 3 本にすればいい。 3 つの数を足して、和と繰り上がりを出す回路を 全加算器 という。 そしてそれを桁の数だけ横に並べ、繰り上がりを隣へ渡していけば—— 同じ部品を 4 つ並べるだけで、4 桁の足し算ができてしまう。

次回はそれを作って、実際に押してみよう。

参考文献

シリーズ「コンピュータの計算のしくみ」