ゲートで数を足すしくみ

2つのビットを足すには、XORゲート1つとANDゲート1つで十分です。全加算器を4つつなげば、0から15までの2つの数を足せます。

先を読む前にやってみましょう。0101と0011を、10進数の足し算と同じやり方で、紙の上で2進数のまま足します。桁上がりは次の列の上に書きましょう。必要な事実は3つだけです。0 + 0 = 0、0 + 1 = 1、そして1 + 1 = 10、つまり0を書いて1繰り上げます。下の桁から繰り上がりがあるときは1 + 1 + 1 = 11なので、1を書いて1繰り上げます。計算は次の段落にあるので、先に隠しておきましょう。

計算はこうなります。いちばん右の列：1 + 1 = 10、0を書いて1繰り上げ。次：0 + 1に繰り上がりを足すとまた10、0を書いて1繰り上げ。次：1 + 0に繰り上がりを足して10、0を書いて1繰り上げ。いちばん左：0 + 0に繰り上がりを足すと1。答えは1000で、これは8です。5 + 3 = 8ですね。4つの列のうち3つで桁上がりがありました。電卓も、ゲームも、表計算ソフトも、最後にはまさにこれをしています。プロセッサーの中では、どの列も数個のゲートが受け持ち、シーンも同じ足し算から始まります。次に、そこで9 + 8を試してみましょう。5番目のビットが必要になります。

いちばん右の列はゲート2つだけでよい

いちばん右の列だけを見てみましょう。そこでの答えのビット、つまり和は、ちょうど1つの入力が1のときに1です。これはXORの規則です。桁上がりは両方の入力が1のときだけ1です。これはANDの規則です。だから、同じ2つの入力を受け取るXORゲートとANDゲートを並べれば、2つのビットを足せます。この小さな回路が半加算器です。「半」なのは、右の列からの桁上がりを受け取る方法がないからです。

ほかの列では3つのビットを足す

ほかのどの列でも3つのビットが出会います。それぞれの数から1つずつと、右からの桁上がりです。全加算器はこの3つすべてを受け取ります。和はA XOR B XOR（下からの桁上がり）で、3つのうち奇数個が1のときに1です。上への桁上がりは、少なくとも2つが1のときに1です。半加算器2つとORゲート1つで全加算器が1つできます。全加算器を4つ並べ、それぞれの上への桁上がりを左どなりの加算器の下からの桁上がりにつなげば、4ビット加算器になります。最後の列が落ち着くまで、桁上がりが右から左へ順に伝わっていかなければならないので、この設計はリップルキャリー加算器と呼ばれます。実際のプロセッサーは、桁上がりを前もって計算する、もっと工夫された回路で64ビットの数を足しますが、各列の規則は同じです。

答えが大きすぎるとどうなるか

4ビットには0から15が入ります。9と8を足すと本当の答えの17は2進数で10001、つまり5ビットです。4ビットしか持たないレジスタには0001、つまり1が入り、左に余った桁上がりが警告の印になります。これがオーバーフローです。4ビットで15 + 1を計算すると0000が残ります。プロセッサーはこれが起きるとフラグを立て、プログラムが気づけるようにします。引き算も同じ加算器を使います。A − Bを求めるには、プロセッサーはBのすべてのビットを反転して1を足し、Bの2の補数を作ります。それをAに足して、余分な桁上がりを捨てます。4ビットで5 − 3を計算すると、3は0011、反転すると1100、1を足すと1101です。そして0101 + 1101 = 10010で、4ビットだけ残すと0010、つまり2です。

かけ算はずらして足すこと

かけ算も同じ部品からできます。2進数で2をかけると、すべてのビットが1つ左にずれます。10進数で10をかけると0が1つ増えるのと同じです。0011（3）は0110（6）になります。5 × 3では、3が2 + 1であることに注目しましょう。だから5 × 3 = 5 × 2 + 5 × 1 = 1010 + 0101 = 1111で、15です。乗算回路は、2つ目の数の1のビットを1つずつ取り上げながら、このようにずらして足していきます。