从逻辑门到加法器
计算机不会「算数」——它只会用逻辑门一层层搭积木。这一讲我们亲手用 XOR、AND、OR 门搭建出一个能算加法的电路，从半加器到全加器再到 4 位加法器，逐级构建。
生活中的加法——列竖式的启示
回想你在纸上做加法的过程。计算 37 + 58：
先算个位：7 + 8 = 15，写 5，进 1。
再算十位：3 + 5 + 进位1 = 9，写 9，结果是 95。
这个过程揭示了三个关键点：
1. 逐位计算：每一位只关心自己的两个加数和来自低位的进位。
2. 进位传播：低位算完可能产生进位，这个进位要传给高位。
3. 最低位特殊：最低位没有来自更低位的进位，只需要处理两个加数。
计算机做加法也是这个思路：把一个大问题（多位加法）拆成许多小问题（1位加法），然后逐个击破。
半加器——最低位的 1 位加法
最低位没有进位输入，只需要把两个 1 位二进制数相加。能处理这种情况的电路叫半加器（Half Adder）。
半加器有两个输入 A 和 B，两个输出：和位 Sum 和 进位 Carry。
半加器真值表：
| A | B | Sum（和） | Carry（进位） |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
观察真值表，一个惊人的巧合出现了：
Sum = A XOR B。当 A 和 B 不同时 Sum=1，相同时 Sum=0——这正是异或门的真值表。
Carry = A AND B。只有两个输入都是 1 时才产生进位——这正是与门的真值表。
半加器只需要 1 个 XOR 门 + 1 个 AND 门就能实现。乔治·布尔恐怕自己都没想到，他发明的代数系统有一天会成为加法器的数学基础。
全加器——处理进位的完整加法
半加器有一个致命缺陷：它不能接收来自低位的进位。除最低位外，每一位都要处理三个数：A、B、来自低位的进位 Cin。
能同时处理两个加数和一个进位输入的电路叫全加器（Full Adder）。
全加器真值表：
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
一个巧妙的设计：用两个半加器就能搭出全加器。
第一步：半加器 1 处理 A 和 B，得到中间和 S1 和进位 C1。
第二步：半加器 2 处理 S1 和 Cin，得到最终和 Sum 和进位 C2。
第三步：最终进位 Cout = C1 OR C2（任意一个半加器产生进位，最终就输出进位）。
全加器的电路结构：2 个半加器 + 1 个 OR 门。层层叠加，每个半加器内部又是 XOR + AND。这种分层构建的思想贯穿整个计算机体系结构。
级联全加器——4 位行波进位加法器
有了全加器，多位加法就简单了：把多个全加器串起来，低位的进位输出连到高位的进位输入。
一个 4 位加法器的级联结构：
第 0 位（最低位）：全加器处理 A0、B0，进位入 = 0，产生和 S0 和进位 C0。
第 1 位：全加器处理 A1、B1，进位入 = C0，产生和 S1 和进位 C1。
第 2 位：全加器处理 A2、B2，进位入 = C1，产生和 S2 和进位 C2。
第 3 位（最高位）：全加器处理 A3、B3，进位入 = C2，产生和 S3 和进位 C3（最终进位）。
进位像水波一样从低位逐级「荡漾」到高位，因此这种结构叫行波进位加法器（Ripple Carry Adder）。
行波进位加法器简单直观，但有一个性能瓶颈：最坏情况下，进位需要从第 0 位一直传到最高位，经过 N 级全加器的延迟。现代 CPU 使用超前进位（Carry Lookahead）等技术优化，但理解行波进位是理解一切加法器优化的前提。
Python 代码演示
实例
# 第8讲：从逻辑门到加法器 - Python 演示
# runoob 教程系列
# ============================================
def half_adder(a, b):
"""
半加器：两个 1 位二进制数相加，不考虑进位输入。
参数:
a, b: 各为 0 或 1
返回:
(sum_bit, carry_out): 和位与进位
电路实现:
sum_bit = a XOR b （异或门）
carry_out = a AND b （与门）
"""
sum_bit = a ^ b # XOR：相同为 0，不同为 1
carry_out = a & b # AND：两者都为 1 时才进位
return sum_bit, carry_out
def full_adder(a, b, carry_in):
"""
全加器：两个 1 位二进制数相加，考虑进位输入。
参数:
a, b, carry_in: 各为 0 或 1
返回:
(sum_bit, carry_out): 和位与进位
实现技巧——用两个半加器级联：
第一步：half_adder(a, b) → (s1, c1)
第二步：half_adder(s1, carry_in) → (sum_bit, c2)
最终进位：carry_out = c1 OR c2
"""
s1, c1 = half_adder(a, b)
sum_bit, c2 = half_adder(s1, carry_in)
carry_out = c1 | c2 # OR 门：任意一个有进位，最终就有进位
return sum_bit, carry_out
def adder_4bit(a_bits, b_bits):
"""
4 位行波进位加法器：4 个全加器级联。
参数:
a_bits: 4 位二进制列表，a_bits[0] 为最低位（LSB）
b_bits: 4 位二进制列表，b_bits[0] 为最低位（LSB）
返回:
(sum_bits, final_carry): 4 位和（低位在前）与最终进位
打印进位传播的完整过程，展示行波进位的工作方式。
"""
carry_in = 0
sum_bits = []
print("=" * 55)
print(" 4 位行波进位加法器 —— 进位传播过程")
print("=" * 55)
# 高位在前显示，方便人阅读
print(f" 加数 A: {list(reversed(a_bits))} (高位在前)")
print(f" 加数 B: {list(reversed(b_bits))} (高位在前)")
print()
for i in range(4):
s, carry_out = full_adder(a_bits[i], b_bits[i], carry_in)
sum_bits.append(s)
print(f" [第 {i} 位] (最低位为第 0 位)")
print(f" 输入: A[{i}]={a_bits[i]}, B[{i}]={b_bits[i]}, 进位入={carry_in}")
print(f" 输出: 和位={s}, 进位出={carry_out}")
if carry_out:
print(f" >> 产生进位！Carry={carry_out} 将传递给第 {i+1} 位")
carry_in = carry_out # 当前进位成为下一位的进位入
print()
print(f" 计算结果: {list(reversed(sum_bits))} (高位在前)")
print(f" 最终进位: {carry_in}")
print("=" * 55)
return sum_bits, carry_in
def decimal_to_4bit(n):
"""将 0-15 的十进制数转为 4 位二进制列表（低位在前）"""
return [(n >> i) & 1 for i in range(4)]
def bits_to_decimal(bits):
"""将二进制位列表（低位在前）转为十进制整数"""
return sum(bit * (2 ** i) for i, bit in enumerate(bits))
# ============================================
# 测试用例
# ============================================
print(">>> runoob 半加器测试 <<<")
for a in (0, 1):
for b in (0, 1):
s, c = half_adder(a, b)
print(f" half_adder({a}, {b}) => sum={s}, carry={c}")
print()
print(">>> runoob 全加器测试 <<<")
test_cases = [
(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)
]
for a, b, cin in test_cases:
s, c = full_adder(a, b, cin)
print(f" full_adder({a}, {b}, carry_in={cin}) => sum={s}, carry={c}")
print()
print(">>> runoob 4 位加法器测试: 7 + 5 <<<")
a_dec, b_dec = 7, 5
a_bits = decimal_to_4bit(a_dec)
b_bits = decimal_to_4bit(b_dec)
result_bits, final_carry = adder_4bit(a_bits, b_bits)
result_dec = bits_to_decimal(result_bits)
print(f" 期望: {a_dec} + {b_dec} = {a_dec + b_dec}")
print(f" 结果: {result_dec} (进位={final_carry})")
print(f" runoob 验证: {'通过!' if result_dec == a_dec + b_dec else '失败!'}")
print()
print(">>> runoob 额外测试: 10 + 6 (可能溢出) <<<")
a_bits2 = decimal_to_4bit(10)
b_bits2 = decimal_to_4bit(6)
result_bits2, carry2 = adder_4bit(a_bits2, b_bits2)
result_dec2 = bits_to_decimal(result_bits2)
full_result = result_dec2 + (carry2 * 16)
print(f" 期望: 10 + 6 = 16")
print(f" 4 位结果: {result_dec2}, 进位: {carry2}, 完整 5 位值: {full_result}")
print(f" runoob 验证: {'通过!' if full_result == 16 else '失败!'}")
运行代码，观察进位如何在每一位之间传播——最低位先算，产生进位后传给下一位，下一位再算，产生进位再往后传。这就是「行波进位」名称的由来。
交互演示：4 位加法器级联动画（runoob 进位传播演示）
下方用纯 div+SVG 模拟了一个 4 位行波进位加法器。点击按钮逐步演示进位如何从第 0 位（最低位）传到第 3 位（最高位），也可以用「自动演示」观看完整过程。