【情報Ⅰ 第45講】半加算器・全加算器──論理回路がなぜ計算になるのか

こんにちは、数強塾代表の藤原進之介です。この記事は参考書『藤原進之介の最強120講義』の第45講「半加算器・全加算器」のWeb版です。共通テスト「情報Ⅰ」での重要度はA、情報Ⅱでの接続先は(3)情報とデータサイエンスです。

AND・OR・NOT・XORそのものと、MIL記号・NANDの万能性は第44講「論理回路（AND・OR・NOT・XOR）」で、真理値表とベン図は第43講「論理演算とベン図」で扱いました。この第45講は、そのゲートを組み合わせて「計算機」にする話だけに絞ります。

1. この講の問い

論理回路は「正しいか正しくないか」を判定する装置のはずです。それがなぜ「計算」になるのでしょうか。

2. 結論

3. なぜそうなるのか

3-1. 先に制度の話——「加算器」は国の本文のどこにも書かれていない

第44講で、高等学校学習指導要領（平成30年告示）解説 情報編の全文に「論理回路」「論理演算」「回路」という語が1件も出てこないことを確認しました。「加算器」も同じく0件です（2026年8月3日、PDFをテキスト化して確認）。

では文部科学省「情報Ⅰ」教員研修用教材はどうか。ここが面白いところです。

• 「半加算器」「全加算器」という語は0件。
• 「加算器」はたった1件。しかもそれは本文の解説ではなく、第3章の末尾にある指導上の配慮の表の中の一文です。

国が書いているのは「加算器を教えなさい」ではなく、「加算器は身体を介して理解させなさい」という教え方だけなのです。それでいて同じ教材の演習2は、名前を伏せたまま半加算器そのものを組ませています。

文部科学省の「授業・研修用コンテンツ」も見ました。「コンピュータとプログラミング」の動画・スライドは6本ありますが（センサーライト、100連ガチャ、公平な順番決め、天気予報表示マシーン、オリジナルAIなど）、論理回路や加算器を扱う回はありません（2026年8月3日確認）。

一方、情報処理推進機構（IPA）の試験シラバスを見ると、線がきれいに引かれています。

• ITパスポート試験（レベル1）シラバス Ver.6.5：「論理回路」「半加算器」「全加算器」は0件。あるのは「(3) 論理演算　論理演算の考え方と基本的な演算，及び真理値表の利用方法」だけで、活用例は「AND，OR，NOT，XOR（排他的論理和）を使った条件検索」。つまり検索の文脈です
• 基本情報技術者試験（レベル2）シラバス Ver.9.2：ここで初めて「AND 回路，OR 回路，NOT 回路などの基本となる論理回路の組合せによって半加算器，全加算器が実現され，演算が行われていることを理解する」が出てきます

加算器はレベル1には無く、レベル2にあります。 それを高校生が共通テストで問われる。参考書ごとに扱いの深さがバラバラなのは、国の本文に定義が無いからです。だからこの講は「教科書の要点まとめ」では書けません。

3-2. 本講の核心——足し算の表を作ると、答えが論理演算と一致してしまう

2進法で1桁どうしを足します。全部で4通りしかありません。

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10   ← 2桁になる

4行目だけ2桁になるので、答えを最初から2桁で書くことにします。上の桁を C（桁上がり／carry）、下の桁を S（和／sum）と呼びます。

ここで C の列を縦に読みます。0, 0, 0, 1。これは AND の真理値表です。
次に S の列を縦に読みます。0, 1, 1, 0。これは XOR の真理値表です。

私はここを「似ている」で済ませたくありません。なぜ一致するのかを、言葉で説明できるようになってほしいのです。

• 桁上がりが起きるのはどういうときか。 「A も B も 1 のとき」だけです。日本語で「A かつ B」と言った瞬間、それは AND の定義そのものです
• 和の桁が 1 になるのはどういうときか。 足した合計が奇数のとき、つまり「片方だけが 1 のとき」です。日本語で「A と B が異なるとき」と言った瞬間、それは XOR の定義そのものです（第44講で XOR を不一致検出器と呼んだのはこのためです）

つまり偶然の一致ではありません。「繰り上がるのは両方のとき」「1桁目が立つのは片方だけのとき」という算数の言い方が、そのまま論理演算の言い方になっているのです。

もう一段だけ抽象化しておきます。数を1桁ずつに刻んだ瞬間、算術は論理に化けます。 10進数の足し算のままでは論理演算には見えません。しかし2進法にして1桁に切り出すと、扱う値は0と1しかなくなり、「数の計算」と「真偽の判定」の区別が消えます。第40講「2進数・10進数・16進数の変換」で基数変換をやり、第43講で論理演算をやったものが、ここで1本につながります。コンピュータが計算機である理由は、突き詰めればこの4行の表に書いてあります。

なお教員研修用教材も、この順番で導入しています。教材は「0+0=0／0+1=1／1+0=1 は or で対応できる」「1+1=10 は or で対応できない」と書き、そのうえで「A + B = CF、C は桁上がり，F は1桁目の値」と定義します。or では4行目だけが合わない、だから別のものが要るという筋道です。天下り式に XOR を与えていません。

3-3. 半加算器——ゲート2個でできてしまう

上の式をそのまま部品にします。入力 A・B、出力 C・S。XOR ゲート1個と AND ゲート1個。それだけです。これを半加算器（half adder）といいます。

なぜ「半」なのか。下位の桁からの桁上がりを受け取る口が無いからです。入力が2つしかありません。だから1桁目（いちばん右の桁）にしか使えないのです。

3-4. なぜ半加算器では足りないのか

2桁どうしの足し算を筆算でやってみます。2進法で 11 + 01（10進で 3 + 1）です。

   1 1
 + 0 1
 ------

1の位：1 + 1 = 10。和の桁は 0、桁上がり 1。
2の位：ここで足すのは 1 + 0 + 1（下からの桁上がり） の3つです。

ここで詰みます。半加算器の入力は2つしかない。3つ目の数を入れる場所がありません。

だから入力が3つの加算器が要ります。A、B、そして下位からの桁上がり Cin（carry in）。これが全加算器（full adder）です。「全」は「桁上がりまで含めて全部面倒を見る」の意味だと思ってください。

3-5. 全加算器＝半加算器2つ＋OR、そしてなぜ最後がORでよいのか

3つの数を足すのだから、2つずつ順に足せばよい。

1. まず半加算器①で A + B を計算する。結果は（桁上がり C1、和 S1）
2. その和 S1 に、下位からの Cin を半加算器②で足す。結果は（桁上がり C2、和 S）
3. S がこの桁の和になる。桁上がりは C1 と C2 のどちらかが立っていれば1なので、C1 OR C2

ここで多くの参考書が黙って通り過ぎる箇所があります。なぜ最後が OR でよいのか。 桁上がりが2回出るなら、それを足し算しなければならないのではないか。足し算をするために加算器を作っているのに、その中でまた足し算が要るなら、無限に部品が増えてしまいます。

答えは「C1 と C2 が同時に1になることは絶対に無いから」です。理屈はこうです。

• C1 = 1 になるのは A = B = 1 のときだけ。そのとき半加算器①の和は S1 = 0 です
• すると半加算器②がやるのは 0 + Cin なので、桁上がりは絶対に出ません。C2 = 0
• 逆に C2 = 1 になるのは S1 = Cin = 1 のとき。S1 = 1 なら A と B は片方だけが1なので C1 = 0

つまり「両方1」の行が存在しない。両方1の行が無いなら、OR と足し算の結果は一致します。だから OR で足りるのです。8行の真理値表を全部確かめると、C1 と C2 が同時に1になる行は0件です（4-2節、Python で確認済み）。

ここで無限後退が止まります。これが全加算器の設計の一番きれいなところです。

3-6. 数珠つなぎにすると何桁でも足せる（リップルキャリー加算器）

全加算器の Cout（桁上がり出力）を、1つ上の桁の全加算器の Cin につなぎます。いちばん下の桁の Cin には 0 を入れておきます（下位が無いので桁上がりも無い）。これを桁の数だけ並べる。

4ビットなら全加算器4個。8ビットなら8個。以上です。桁数を増やす方法が「同じ部品を1個足す」だけというのが、この構造の強さです。

桁上がりが下から上へ、さざ波（ripple）のように伝わっていくので、これをリップルキャリー加算器（桁上げ伝搬加算器）と呼びます。

最上位から出た桁上がりは、行き場がありません。これがあふれ（オーバーフロー）です。4ビットの加算器で 1111 + 0001 をやると、答えは 0000 と桁上がり1になります。4ビットの箱には 16 が入らないので、0 に戻ってしまうのです。第40講で「決められたビット数のデータしか扱えない」と書いたことが、ここで具体的な形で現れます。

3-7. 速さの代償——桁を増やすほど遅くなる

ここが本講のもう一つの主戦場です。

上の桁は、下の桁の答えが出るまで自分の答えを確定できません。桁上がりを待たないといけないからです。ゲートには必ず遅れがあるので、桁上がりの波が下から上まで伝わりきるのを待つ必要があります。

段数を数えてみます。ゲートの出力が確定する「段数」を、入力を0段として「入力の段数の最大 + 1」と定義します（XORは1個のゲートとして数えます）。すると、

• 半加算器：S も C も1段
• 全加算器：Cin が来てから Cout が出るまで、さらに2段
• nビットのリップルキャリー加算器：最上位の桁上がりが確定するまで 2n + 1 段

実際に計算すると、4ビットで9段、8ビットで17段、16ビットで33段、32ビットで65段、64ビットで129段になります（4-4節、Python で確認）。桁数に正比例します。 64ビットの整数を足すのに、129段のゲートを順に通るのを待つわけです。

では「表引き」にすればよいのではないか。入力の全パターンを表にして、一発で答えを引けば1段で済みます。これは正しいのですが、行数が爆発します。

32ビットの足し算を表引きでやろうとすると、1844京行の表が要ります。物理的に不可能です。つまり、

• リップルキャリー：部品は少ない（全加算器n個）が、遅い（2n+1段）
• 表引き：速い（1段）が、部品が絶望的に多い（2の2n乗行）

これが速度と回路規模のトレードオフです。実際のCPUはこの両極端の中間にあたる方式（桁上がりを先に見積もる方式など）を使いますが、そこは高校範囲を大きく超えるので名前だけ挙げておきます。受験生に必要なのは「桁数が増えると遅くなる、それは桁上がりが順番に伝わるからだ」という理由のほうです。

3-8. 引き算も同じ回路でできる

最後に一言だけ。2の補数を使うと、引き算は足し算に化けます。だから加算器が1つあれば、足し算も引き算もできてしまうのです。IPAの基本情報技術者試験シラバス Ver.9.2 でも、プロセッサを構成する部品として「加算器，レジスタ，デコーダ」が挙げられ、用語例に「アキュムレーター，補数器」が並んでいます。加算器と補数器はセットなのです。

補数の中身は第41講「負の数の表現と2の補数」の担当なので、ここでは扉だけ開けて先へ進みます。

4. 手で確かめる

4-1. 半加算器の真理値表（全4行）

右2列が一致しています。4通りしかないので、これで証明が終わっています。

4-2. 全加算器の真理値表（全8行）

C1 と C2 の列を見比べてください。両方が1になっている行は1つもありません。 だから最後が OR でよいのです（3-5節）。

4-3. 4ビットのリップルキャリーで 0110 + 0111 を1桁ずつ追う

10進で 6 + 7 = 13 です。下の桁（bit0）から順に見ます。

上から下へ Cout が次の行の Cin に入っていることを確認してください。答えは上位から並べて 1101、10進で 8+4+0+1 = 13。正しい。

桁上がりが最悪まで伝わる例として 1111 + 0001 も見ておきます。

答えは 0000、桁上がり1。4ビットには 16 が入らないのであふれました。そしてbit0 の桁上がりが bit3 まで4段階伝わっています。これが「遅さ」の正体です。

4-4. Python でゲートから組み立てて検算する

以下は2026年8月3日に実際に実行し、出力を確認したものです。標準ライブラリだけで動きます。

import itertools
AND = lambda a, b: a & b
OR  = lambda a, b: a | b
NOT = lambda a: 1 - a
XOR = lambda a, b: AND(OR(a, b), NOT(AND(a, b)))
def half_adder(a, b):
    return AND(a, b), XOR(a, b)          # (carry, sum)
def full_adder(a, b, cin):
    c1, s1 = half_adder(a, b)
    c2, s2 = half_adder(s1, cin)
    return OR(c1, c2), s2                # (carry, sum)
for a, b in itertools.product((0, 1), repeat=2):
    c, s = half_adder(a, b)
    print(a, b, "->", "C=%d S=%d" % (c, s), "OK" if 2 * c + s == a + b else "NG")

実行結果：

0 0 -> C=0 S=0 OK
0 1 -> C=0 S=1 OK
1 0 -> C=0 S=1 OK
1 1 -> C=1 S=0 OK

XOR は第44講で確かめた (A OR B) AND NOT(A AND B) から組み立てています。つまりこの加算器は AND・OR・NOT だけでできています。全加算器も8行すべてで検算しました。

ok = True
for a, b, x in itertools.product((0, 1), repeat=3):
    c, s = full_adder(a, b, x)
    ok = ok and (2 * c + s == a + b + x)
print("full adder all rows OK:", ok)

full adder all rows OK: True

次に4ビットのリップルキャリーを組んで、256通りを全部試します。

def ripple_add(xs, ys, n=4):
    carry, out = 0, []
    for i in range(n):
        carry, s = full_adder(xs[i], ys[i], carry)
        out.append(s)
    return out, carry
to_bits = lambda v, n=4: [(v >> i) & 1 for i in range(n)]
bad = 0
for x in range(16):
    for y in range(16):
        out, cout = ripple_add(to_bits(x), to_bits(y))
        got = sum(b << i for i, b in enumerate(out)) + (cout << 4)
        if got != x + y:
            bad += 1
print("mismatches:", bad)

mismatches: 0

16×16 = 256通りすべてで正しい。 全パターンを尽くしたので、この4ビット加算器は「テストに通った」のではなく「証明された」のです。この違いは第6ブロックで効いてきます。

最後に、段数を数えて「遅さ」を確かめます。

def half_adder_lv(la, lb):
    return max(la, lb) + 1, max(la, lb) + 1      # (carry, sum)
def full_adder_lv(la, lb, lcin):
    lc1, ls1 = half_adder_lv(la, lb)
    lc2, ls2 = half_adder_lv(ls1, lcin)
    return max(lc1, lc2) + 1, ls2
for n in (4, 8, 16, 32, 64):
    lcin = 0
    for _ in range(n):
        lcin, ls = full_adder_lv(0, 0, lcin)
    print("%2dbit: 最上位の桁上がりまで %3d 段" % (n, lcin))

 4bit: 最上位の桁上がりまで   9 段
 8bit: 最上位の桁上がりまで  17 段
16bit: 最上位の桁上がりまで  33 段
32bit: 最上位の桁上がりまで  65 段
64bit: 最上位の桁上がりまで 129 段

きれいに 2n + 1 になっています。桁数に比例します。

5. 共通テストではこう出る（重要度 A）

5-1. 一次資料で確認できる出題実績

大学入試センターが公表した「令和7年度大学入学共通テスト 試作問題『情報』の概要」には、試作問題『情報Ⅰ』第1問 問3の意図がこう書かれています。

配点は6点、第1問（20点）の3割です。「示された演算処理を実現するための真理値表及び論理回路」——加算器はまさにこの型です。

もう一つ、教材側の裏付けを挙げます。文部科学省は演習の解答も公開しています。第3章（学習11〜17）の演習解答PDFに、学習11 演習2の解答がこう書かれています。

第44講で Python を使って独立に導いた ①AND ②NOT ③AND と、公式解答が一致しました。同じPDFの演習1(3)には「※（３）は A と B の排他的論理和といい，A XOR B と表現される」という注記もあります。 国の教材が XOR を名指ししているのは、私が確認した限りこの1行だけです。

5-2. 出題の型（問題文は転載しません）

1. 回路図 → 真理値表。 半加算器や全加算器の図が示され、出力の列を埋める。中間信号に名前を付けて左から順に列を作れば必ず解けます
2. 真理値表 → 回路。 「桁上がりの列が 0,0,0,1 になる」といった条件から、入るゲートを選ぶ
3. 空欄補充。 回路の一部が空欄で、AND・OR・NOT・XOR のどれが入るかを答える（教員研修用教材の演習2と同じ形式）
4. 多桁の加算のトレース。 4ビットの足し算を1桁ずつ追わせ、途中の桁上がりや最終出力を答えさせる
5. あふれの判定。 決められたビット数に収まるかどうかを問う（第40講・第41講と合わせて出やすい）

5-3. 引っかけ

• C と S を逆に書く。 桁上がりが AND（4行目だけ1）、和が XOR（4行目が0）。「4行目を見る」の一手で区別できます
• 半加算器を最上位に使ってしまう。 半加算器が使えるのは最下位だけ。それより上は必ず全加算器です
• 最下位の Cin を書き忘れる。 最下位の Cin は 0。空欄になっていたら 0 を入れます
• 桁上がりの向きを逆にする。 桁上がりは下位から上位へ。図で右が下位なら、桁上がりは右から左へ流れます
• あふれた桁上がりを答えに足してしまう。 nビットの加算器の出力はnビット。はみ出した桁上がりは「あふれ」であって答えの一部ではありません
• 全加算器の最後を XOR にしてしまう。 最後は OR。C1 と C2 が同時に1にならないので OR で足ります

5-4. 自作の練習問題

6. 情報Ⅱではこうなる

本講の接続は一言で言えます。単純な素子を同じ向きに何段も重ねると、単体では絶対に出せない複雑な機能が現れる。 この構造が、加算器とニューラルネットワークでそっくり同じなのです。

6-1. 「重ねると複雑になる」を、教材はこう書いている

文部科学省「情報Ⅱ」教員研修用教材 第3章後半 学習17「ニューラルネットワークとその仕組み」の「ニューラルネットワークの概念」の節に、次の一文があります。

「次の入力として渡していくことを繰り返す」——これは加算器で私たちがやったことと、まったく同じ操作です。

• 加算器：桁上がりを次の桁の入力として渡していくことを繰り返すと、何桁でも足せる
• ニューラルネットワーク：隠れ層の出力を次の層の入力として渡していくことを繰り返すと、より複雑な出力に対応できる

方向が違うだけです。加算器は「桁の方向」に重ね、ニューラルネットワークは「層の方向」に重ねる。素子1個は、加算器なら「両方1なら1」しか言えず、ニューロンなら「重み付き和がしきい値を超えたか」しか言えません。それを重ねると、片方は64ビット整数の加算になり、もう片方は手書き文字の認識になります。

第44講で確かめたことも、ここに効いてきます。XOR は1個のしきい値素子では絶対に作れません（重みを −4〜4 の整数、バイアスを 0.5 刻みで全探索しても該当0件でした）。だから XOR を作るにはゲートを2段にする。ニューラルネットワークに「層」が要る理由の、いちばん小さい実例がこれです。そして本講の半加算器は、その XOR を積み木として使っています。

6-2. 「重ねると遅くなる」も、教材が歴史として書いている

3-7節で、桁を重ねるほど遅くなるというトレードオフを見ました。同じことが情報Ⅱ側にも書いてあります。同じ教材の「ニューラルネットワークの由来」の節です。

深くすれば強くなる。しかし深くすれば計算量と計算時間が増える。 この綱引きが、ニューラルネットワークを何十年も止めていたと教材は書いています。リップルキャリー加算器で「桁を増やすと段数が 2n+1 に増える」のと、まったく同じ形の問題です。ハードウェアの進歩（GPU）が壁を破ったという結末まで、加算器の高速化の歴史と重なります。

6-3. 決定的に違うのは「全部確かめられるかどうか」

最下行が決定的です。4-4節で私は256通りを全部試して「不一致0件」を出しました。これは検査ではなく証明です。ところがニューラルネットワークでは、入力の組合せが 3-7節の表引きと同じ勢いで爆発するので、全通りを確かめることが原理的に不可能になります。

ここで面白いことが起きています。まったく同じ「組合せ爆発」が、2つの場面でまったく違う意味を持つのです。

• 加算器では、爆発は「表引きをやめて回路にする理由」になりました。全部の答えを表に持てないから、桁ごとの小さな部品を数珠つなぎにするという設計が生まれた
• 機械学習では、爆発は「正しさを証明できない理由」になります。全部の入力を試せないから、テストデータでの正解率という間接的な評価で我慢するしかない

情報Ⅰのうちに「4行を全部書く」「8行を全部書く」「256通りを全部試す」をやっておくと、情報Ⅱで「なぜ全部は試せないのか」「だから正解率90%とはどういう意味なのか」が体で分かります。全部確かめた経験のある人だけが、全部は確かめられないことの重さを理解できます。 ここが本講を情報Ⅱのデータサイエンスにつなぐ橋です。

まとめ

• 2進法1桁の足し算は、桁上がりが AND、和が XOR。算術が論理演算に化ける瞬間がここ。
• 半加算器＝XOR＋AND。下位からの桁上がりを受け取れないので「半」。
• 全加算器＝半加算器2つ＋OR。C1 と C2 が同時に1にならないので、最後は OR で足りる。
• 全加算器を数珠つなぎにするとリップルキャリー加算器。桁数を増やす方法は「同じ部品を1個足す」だけ。
• ただし桁上がりが下から上へ伝わるので、段数は 2n+1。表引きなら1段だが行数が 2の2n乗に爆発する。速度と回路規模のトレードオフ。
• 情報Ⅱでは、同じ「重ねると複雑になる」構造がニューラルネットワークの層として現れる。違いは、加算器は全通り確かめられるが、機械学習は確かめられないこと。

出典（すべて2026年8月3日に取得）

• 文部科学省「高等学校学習指導要領（平成30年告示）解説 情報編」平成30年7月
• 文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第3章 コンピュータとプログラミング（令和2年）
• 文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材（演習解答等）」第3章 学習11〜17（2021年1月27日公表）
• 文部科学省「高等学校情報科『情報Ⅱ』教員研修用教材」第3章 情報とデータサイエンス 後半（令和2年6月）
• 文部科学省「授業・研修用コンテンツ」（高等学校情報科）
• 独立行政法人大学入試センター「令和7年度大学入学共通テスト 試作問題『情報』の概要」
• 情報処理推進機構（IPA）「基本情報技術者試験（レベル2）シラバス Ver.9.2」
• 情報処理推進機構（IPA）「ITパスポート試験（レベル1）シラバス Ver.6.5」

本講は参考書『藤原進之介の最強120講義』の1講です。全講の一覧は情報Ⅰ 最強120講義の目次にあります。情報Ⅰがなぜ必修科目になったのかという背景は情報Ⅰはなぜ必修になったのかに書きました。制度の話は2026年8月時点の情報です。