全加算器の仕組み ── コンピュータが「3 + 1 = 4」を計算するとき、桁はどう上がるのか

この記事の前提 前回の記事で、1 + 1 = 10₂ という1ビットの足し算が、XOR と AND というたった2個の論理ゲートだけで実現できることを見ました。今回はその続編です。「桁上がり」が次の桁に伝わっていくという、もう一段深い話に踏み込みます。

1 + 1 はなぜ 2 になる？ ― コンピューターが足し算する仕組みを「半加算器」から覗いてみる | hirota.noの技術ブログ〜 It’s all over the network.

読む前にパッと耳で！この記事のポイント、サクッと音声でお届け

ポッドキャスト音声
このポッドキャスト音声は、本記事をもとに、AIツール（NotebookLM）を用いて自動生成したものです。発音や言い回しに不自然な点や、内容に誤りが含まれる可能性があります。あくまで「理解の補助」としてご活用いただけますと幸いです。

まずは触ってみてください
はじめに ── 半加算器には致命的な弱点があった
3 + 1 を2進数で筆算してみる
半加算器では足りない理由
全加算器の真理値表
全加算器を半加算器2個で作る
3 + 1 を全加算器で実行してみる
なぜこれが「リップルキャリー(Ripple Carry)」と呼ばれるのか
まとめ ── 「+」記号の中身を見てきた

まずは触ってみてください

「3 + 1 = 4」という当たり前の足し算 ―― これをコンピュータの中の論理回路でやると、16個のゲートが順番に発火する という、ちょっと驚きの世界が広がっています。

文章で説明する前に、まずは動かしてみるのが早いと思うので、ブラウザ上で動く小さなシミュレーターを用意しました。

👉 全加算器シミュレーターを体験する

「次のゲートへ」ボタンを押すたびに、HA1(青)→ HA2(橙)→ OR(ピンク) の3つのブロックが順番に光り、配線をキャリー信号がスーッと流れていきます。9回押せば 3 + 1 = 4 が回路の中で完成する様子を最後まで追えます。

HA1 = 半加算器1個目(A⊕B と A∧B を計算)
HA2 = 半加算器2個目(前桁のキャリーを混ぜる)
OR = 2つのキャリー候補をまとめて次の桁へ送る

下位の FA0 から上位の FA2 へ向けて、キャリー(繰り上がり)が右に右にとリレーしていく 様子が一目で分かるはずです。

「全加算器って結局なんで半加算器2個とORで足し算できるんだっけ?」が体感できたら、この記事の本編に進んでください。理屈の部分がスッと入ってくるはずです。

はじめに ── 半加算器には致命的な弱点があった

前回の半加算器(Half Adder)は、A と B という2つの入力ビットを受け取って、SUM と CARRY を出力する回路でした。

A	B	SUM	CARRY
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

「1+1 のときだけ桁が上がって CARRY=1 が出る」というアレです。

ここで素朴な疑問が湧きます。

じゃあ、その出てきた CARRY=1 は、どこに行くの?

半加算器は、出力するだけして、それを受け取る場所がないんです。だから「Half(半分の)」加算器なんですね。

3 + 1 のような複数桁の足し算をしようとすると、この弱点がいきなり露呈します。

3 + 1 を2進数で筆算してみる

10進数の 3 + 1 = 4 を、2進数の世界で書き直してみましょう。

   011    (= 3)
 + 001    (= 1)
 -----
   100    (= 4)

小学校で習った筆算と全く同じ手順で、右の桁から順に足していきます。

第0桁(一番右)

  1
+ 1
---
 10  ← ここで桁が上がる!

1 + 1 = 10₂。この桁の答えは 0 で、1 は左隣の桁に繰り上がります。これが「キャリー(carry)」、繰り上がりです。

第1桁(真ん中)

ここがポイント。この桁では足すべき数字が3つあります。

A の第1桁: 1
B の第1桁: 0
第0桁から繰り上がってきた 1

つまり 1 + 0 + 1 = 10₂。再び桁上がり発生。

第2桁(一番左)

A の第2桁: 0
B の第2桁: 0
第1桁から繰り上がってきた 1

0 + 0 + 1 = 1。今度は桁上がりなし。

結果を並べると 100₂ = 4。正解。

半加算器では足りない理由

筆算をやってみてハッキリしました。

2桁目以降の足し算では、ビットを「3つ」足さないといけない。

でも半加算器の入力は A と B の2つだけ。 繰り上がりを受け取る入り口がないんです。

そこで登場するのが 全加算器(Full Adder) です。

種類	入力	出力
半加算器	A, B	SUM, CARRY
全加算器	A, B, C_in (前桁からの繰り上がり)	SUM, C_out (次桁への繰り上がり)

入力に C_in(キャリーイン)、出力に C_out(キャリーアウト)が増えただけ。たったこれだけのことが、「足し算可能な桁数を一気に増やす」という大きな結果を生みます。

全加算器の真理値表

入力が3つになったので、組み合わせは 2³ = 8 通り。

A	B	C_in	SUM	C_out	意味
0	0	0	0	0	0+0+0 = 0
0	0	1	1	0	0+0+1 = 1
0	1	0	1	0	0+1+0 = 1
0	1	1	0	1	0+1+1 = 10₂
1	0	0	1	0	1+0+0 = 1
1	0	1	0	1	1+0+1 = 10₂
1	1	0	0	1	1+1+0 = 10₂
1	1	1	1	1	1+1+1 = 11₂

注目してほしいパターンが2つあります。

SUM のパターン: 1の数が奇数個のときだけ 1 になっている。これはまさに 3入力XOR の挙動です。

C_out のパターン: 1の数が2個以上のときに 1 になっている。これは「多数決」と呼ばれる関数で、論理ゲートで言うと「2個以上のANDのOR」で作れます。

全加算器を半加算器2個で作る

ここからが面白いところ。全加算器は、半加算器を2つ並べるだけで作れます。

順を追うと:

HA1(1個目の半加算器)が A と B を足して、途中結果 S1 と C1 を出す
HA2(2個目の半加算器)が S1 と C_in(前桁からの繰り上がり)を足して、最終的な SUM と C2 を出す
C_out は、C1 か C2 のどちらかが 1 なら 1(ORゲート)

なぜ C1 と C2 を OR するの? 「A+B で繰り上がった」ケースと、「(A+B) + C_in で繰り上がった」ケースが同時に起きることはないからです。 S1 は最大でも 1 で、それに C_in を足しても 2 までしか行かない。だから2つの C のどちらかが立っていれば、即座に C_out = 1 でOK、というわけ。

論理式で書けば、こうなります:

SUM   = A XOR B XOR C_in
C_out = (A AND B) OR ((A XOR B) AND C_in)

たった2行。これだけで「桁上がりを受け継ぎながら任意桁の足し算ができる回路」の本質が表せます。

3 + 1 を全加算器で実行してみる

3ビットの加算器を作るには、全加算器を3個直列につなぎます。

右から順に信号が伝わっていきます。

FA0 (一番右の桁) の動き

入力: A=1, B=1, C_in=0 計算: 1 + 1 + 0 = 10₂ 出力: SUM=0, C_out=1

桁上がり発生。C_out=1 が左隣の FA1 の C_in に流れ込みます。

FA1 (真ん中の桁)

FA0 から C_in=1 が届くまで、FA1 は計算を始められません。これはゲート遅延と呼ばれる物理的な待ち時間で、現代CPUの速度を制限する根本要因の一つでもあります。

入力: A=1, B=0, C_in=1 計算: 1 + 0 + 1 = 10₂ 出力: SUM=0, C_out=1

また桁上がり発生。C_out=1 が FA2 に流れます。

FA2 (一番左の桁)

入力: A=0, B=0, C_in=1 計算: 0 + 0 + 1 = 1 出力: SUM=1, C_out=0

ここで桁上がりが止まりました。

最終結果

桁2から桁0の SUM を並べると 100₂ = 4。電気信号だけで、私たちが筆算でやっているのと完全に同じことを実現しています。

なぜこれが「リップルキャリー(Ripple Carry)」と呼ばれるのか

3+1の例で見たように、繰り上がりは右から左へ、波(ripple)のように順番に伝播していきます。

これが Ripple Carry Adder という名前の由来です。シンプルで美しい設計ですが、欠点があります。

桁数が増えると、計算が完了するまでの時間が線形に増える。

64ビットCPUで A + B をするとき、最悪ケースでは桁0からのキャリーが桁63まで64段のゲートを順に通っていく必要があります。これは遅い。

そこで実際のCPUでは、Carry Lookahead Adder という「キャリーを先読みする」改良版が使われます。原理を一言で言うと:

「各桁で A=1 AND B=1 なら、C_in を待たなくても絶対に C_out=1 になるよね?」「だったら全部の桁の C_out を、最初の C_in から並列に計算しちゃおう」

このアイデアの効果は劇的で、64ビット加算が O(N) 時間から O(log N) 時間に短縮されます。ただし回路は複雑になり、トランジスタ数は増える。CPUの設計はいつも、こういうトレードオフの積み重ねです。

まとめ ── 「+」記号の中身を見てきた

ここまでで、私たちは a + b という何気ない式の中で何が起きているかを、回路レベルで追いかけてきました。

1ビットの足し算は 半加算器(XORとAND)で実現できる
でも半加算器だけでは桁上がりを受け取れないので、複数桁の足し算ができない
全加算器は半加算器を2個 + ORゲートで作れて、3つのビットを足せる
全加算器を直列につなぐと、任意のビット幅の加算器ができる(リップルキャリー)
ただしリップルキャリーは桁数に比例して遅くなるので、実際のCPUは先読み式を使う

普段プログラムで 3 + 1 と書いた瞬間、CPU の中ではこれだけのことが、ナノ秒以下の時間で起きています。

「数を足す」という、人類が何千年もやってきた行為が、電気信号と論理ゲートの組み合わせで完璧に再現できる。 コンピュータがコンピュータである所以は、ここにあると私は思っています。

次回は、引き算がどう実現されているか(ヒント: 2の補数を使うと、足し算回路をそのまま引き算回路として使い回せます)を見ていきましょう。