論理回路で足し算をする：半加算器をパズルで考える
Hiroki Obara · DeveloperMath Gates使い方
AND・OR・NOTをパズルで考える では、真と偽を組み合わせたり、ひっくり返したりする三つの操作を書きました。この記事はその続きです。コンピュータは、この三つの操作だけで足し算をしています。そのいちばん小さな部品が「半加算器」です。
むずかしそうな名前ですが、中身は4行の表が二つだけです。パズルのつもりで読んでもらえればと思います。
2進数の足し算
コンピュータの中では、数を0と1だけで表します。これを2進数といいます。私たちがふだん使う10進数では、9の次で桁が上がって10になります。2進数では、1の次で桁が上がります。
| 10進数 | 2進数 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 10 |
| 3 | 11 |
| 4 | 100 |
2進数の1桁どうしの足し算は、組み合わせが4通りしかありません。
- 0＋0＝0
- 0＋1＝1
- 1＋0＝1
- 1＋1＝10
最後の 1＋1 だけ、答えが2桁になります。10進数の 5＋5＝10 と同じで、その桁には0が残り、上の桁に1が繰り上がります。
答えを二つに分ける
答えを、その桁に残る数「和」と、上の桁に送る数「桁上がり」の二つに分けて表にします。
| A | B | 和 | 桁上がり |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
ここで、1を真、0を偽と読みかえてみます。前の記事の真理値表と見くらべると、気づくことがあります。
桁上がりの列は、A と B が両方1のときだけ1です。これは AND そのものです。
和の列は、A と B のどちらか一方だけが1のときに1で、両方1のときは0です。これは OR に似ていますが、最後の行だけが違います。前の記事の最後に名前だけ書いた、XOR（排他的論理和）です。
つまり、1桁の足し算は「和は XOR、桁上がりは AND」で計算できます。この二つを組み合わせた回路が、半加算器です。
XOR を AND・OR・NOT で作る
XOR は、AND・OR・NOT から作れます。ここがこの記事のパズルです。
XOR は「どちらか一方が真」で、「両方が真ではない」ものです。言葉をそのまま式にすると、こうなります。
和 ＝ （A OR B） AND NOT（A AND B）
表で確かめます。
| A | B | A OR B | A AND B | NOT（A AND B） | 和 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
最後の列が、さっきの和の列と一致しました。しかも、途中で使った「A AND B」は、桁上がりそのものです。ですから半加算器は、AND を一つ、OR を一つ、NOT を一つ、それにもう一つの AND があれば組めます。
前の記事で書いた、スイッチと豆電球の回路で考えることもできます。直列のスイッチが AND、並列のスイッチが OR でした。半加算器は、そうしたスイッチの組み合わせで「1＋1 のときは和の電球を消して、桁上がりの電球をつける」装置だと言えます。
なぜ「半」なのか
半加算器が足せるのは、1桁と1桁だけです。2桁以上の数を足すときは、下の桁から繰り上がってきた1も一緒に足さなければなりません。3つの1桁を足す回路を「全加算器」といいます。全加算器は、半加算器を二つと OR を一つで作れます。A と B を足し、その和に下からの桁上がりを足し、二つの半加算器の桁上がりのどちらかが1なら、上の桁に1を送ります。
全加算器を桁の数だけ横に並べ、それぞれの桁上がりを隣へ渡せば、何桁の足し算でもできます。2進数の 11＋01（10進数の 3＋1）なら、1桁目は 1＋1 で和0・桁上がり1、2桁目は 1＋0＋1 でまた和0・桁上がり1、3桁目に1が出て、答えは 100（10進数の4）です。
筆算の繰り上がりと、やっていることはまったく同じです。違うのは、使う数字が0と1の二つしかないことだけです。
半加算器や全加算器について、図を見ながら確かめたいときは、Wikipedia の加算器の項目に回路図があります。
余りと商で見る
算数の言葉で言いかえることもできます。A＋B を2で割ると、和は「2で割った余り」、桁上がりは「2で割った商」になります。1＋1＝2 を2で割ると、商1、余り0。表の最後の行と同じです。
私は、この見方を知っておくとよいと考えています。半加算器は、論理の装置であると同時に、「足して、2で割って、余りと商に分ける」計算の装置でもあります。論理と算数は別々の科目ではなく、同じものを二つの言葉で書いている、ということが、ここではっきり見えると思います。
家でできる回路パズル
紙と鉛筆だけで、次のような問題が作れます。
- AND・OR・NOT だけを使って、「A と B が同じときだけ真」になる式を作る（XOR を NOT でひっくり返したものです）
- 半加算器を二つ使って、全加算器の表（8行）を書く
- 2進数の 101＋011 を、全加算器を3つ並べたつもりで、1桁ずつ計算する
1 は、答えを作ったら、4行の真理値表を書いて確かめます。式が合っていれば、表の列が思ったとおりに並びます。うまくいかないときは、どの行で食い違ったかを見ると、AND と OR を取り違えた場所が分かります。
Math Gates の論理の回路
Math Gates は、私が作っている回路パズルのゲームです。盤の空きマスに、数を変える「門」と、進む向きを90度曲げる「鏡」を置き、「うごかす」を押すと、数を持った「ビット」がまっすぐ走ります。目的地の「ポート」は、条件を満たす値しか受け取りません。
最後のワールド「論理の回路」では、比較の門を通った数が真か偽に変わり、NOT・AND・OR の論理門を通ります。論理門には「AND T」のように組み合わせる真偽が書かれていて、ビットの真偽とその値を組み合わせます。盤の上を走るビットは一つなので、二つの入力を同時に受ける半加算器そのものを組むことはできません。それでも、AND が厳しく、OR がゆるく、NOT が裏返す、という性質を、ビットの走り方で何度も確かめられます。ワールド3の「余りの回路」には、余りを出す門もあり、この記事の「2で割った余り」の話とつながります。
7ワールド140問で、対象は8歳からです。無料で遊べて、クリアの合間に広告が入ります。広告は買い切りの課金で消せます。遊び方は Math Gates の始め方 に書きました。
