加法器是怎么造出来的
加法器是怎么造出来的
有一个问题困扰过很多刚接触计算机原理的人：逻辑门只能做"与、或、非"这些布尔操作，它是怎么学会"算数学"的？
答案就藏在几个简单电路的组合里，而且妙到令人拍案叫绝。这一章，我们从最简单的 1+1 出发，一步步搭出能做 64 位加法的完整电路。
Level 1：建立直觉
加法的本质是什么
让我们回到小学课堂。你是怎么做加法的？
拿 37 + 48 来说：
37
+ 48
----
85
你从最低位开始：7 + 8 = 15，写下 5，进位 1。 然后下一位：3 + 4 + 1（进位）= 8，写下 8。 结果：85。
这个过程，其实只包含两个动作：
- 求和：两个数字加上进位，得到当前位的值
- 判断进位：结果是否超过了当前位能表示的最大值，如果超过就产生进位
二进制加法也是完全一样的逻辑，只是数字只有 0 和 1：
0 + 0 = 0（和为0，无进位）
0 + 1 = 1（和为1，无进位）
1 + 0 = 1（和为1，无进位）
1 + 1 = 10（和为0，有进位1）
这四条规则，就是整个加法电路要实现的全部内容。
半加器：最简单的加法电路
我们先只考虑一位的加法，不管进位输入（就像只算个位，不考虑来自更低位的进位）。
输入：两个比特 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 和 B 不同时为 1——这是 XOR（异或） 门的行为！
- Carry 只在 A 和 B 都为 1 时才为 1——这是 AND（与） 门的行为！
所以：
Sum = A XOR B
Carry = A AND B
电路图（文字描述）：
A ──┬──┤XOR├──── Sum
│
B ──┴──┤AND├──── Carry
用两个逻辑门就实现了一位加法！这就是半加器（Half Adder）。
"半"的意思是：它只能处理两个输入，没有考虑来自更低位的进位输入。
全加器：考虑进位的完整加法单元
真正做多位加法时，每一位都需要处理三个输入：A、B，以及来自更低位的进位输入（Cin）。
全加器的真值表：
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
规律：
- Sum = A XOR B XOR Cin（三个数的奇偶性）
- Cout = (A AND B) OR (B AND Cin) OR (A AND Cin) （任意两个输入都为1时就产生进位）
全加器可以用两个半加器加一个 OR 门搭出来：
┌─────────────────┐
A ───────►│ Half Adder 1 ├─── Sum_1 ───►│ Half Adder 2 ├─── Sum (最终)
│ │ │ │
B ───────►│ ├─── Carry_1 ─►│ ├─── Carry_2 ──┐
└─────────────────┘ └─────────────────┘ │
Cin ──────────────────────────────────────►│ Half Adder 2 │ │
│
┌────────┐ │
Carry_1 ─► OR ├─── Cout │
Carry_2 ─► │ │
└────────┘ │
（图示简化了连线，实际上：Sum = HA1的和 XOR Cin，Cout = HA1的进位 OR HA2的进位）
波纹加法器：把全加器串联起来
有了全加器，做多位加法就简单了：把 N 个全加器串联起来，每个全加器的进位输出接到下一个的进位输入。
以 4 位加法为例（计算 0101 + 0011 = 1000，即 5+3=8）：
Cin=0
│
▼
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
A0=1 →│ FA 0 │→ C01 → │ FA 1 │→ C12 → │ FA 2 │→ C23 → │ FA 3 │→ Cout=0
B0=1 →│ │ B1=1→│ │ B2=0→│ │ B3=0→│ │
└──┬───┘ └──┬───┘ └──┬───┘ └──┬───┘
│S0=0 │S1=0 │S2=0 │S3=1
从最低位（右边）开始：
- 位0：A=1, B=1, Cin=0 → Sum=0, Carry=1
- 位1：A=0, B=1, Cin=1 → Sum=0, Carry=1
- 位2：A=1, B=0, Cin=1 → Sum=0, Carry=1
- 位3：A=0, B=0, Cin=1 → Sum=1, Carry=0
结果：Sum=1000 = 8。正确！
这就是行波进位加法器（Ripple Carry Adder）——进位像波浪一样从低位"波纹"传播到高位。
Level 2：原理剖析
XOR 门：异或的本质
异或（XOR）门在加法器里是核心器件，值得深入理解它的本质。
XOR 的定义：当且仅当两个输入不同时，输出为 1。
另一种说法：XOR 检测奇偶性——输入中有奇数个 1 时，输出为 1。
真值表：
A B | A XOR B
0 0 | 0 (偶数个1)
0 1 | 1 (奇数个1)
1 0 | 1 (奇数个1)
1 1 | 0 (偶数个1)
XOR 的代数性质（这些在数字电路设计中非常有用）：
- A XOR 0 = A（与0异或保持不变）
- A XOR 1 = NOT A（与1异或取反）
- A XOR A = 0（自身异或为0）
- A XOR B = B XOR A（交换律）
- (A XOR B) XOR C = A XOR (B XOR C)（结合律）
有趣的应用：不用临时变量交换两个变量：
// 传统方法需要临时变量
int temp = a;
a = b;
b = temp;
// XOR 交换（不需要额外内存）
a = a ^ b;
b = a ^ b; // 现在 b = 原来的 a
a = a ^ b; // 现在 a = 原来的 b
证明：
- 第1步后：a = A⊕B
- 第2步后：b = (A⊕B)⊕B = A⊕(B⊕B) = A⊕0 = A
- 第3步后：a = (A⊕B)⊕A = (A⊕A)⊕B = 0⊕B = B
XOR 的另一个重要应用是错误检测和纠错码——后面会讲到。
行波进位加法器的时延问题
行波进位加法器结构简单，但有个严重问题：速度。
进位必须从最低位一路"波纹"传到最高位，每经过一个全加器就有一个门延迟。如果每个门的延迟是 1ns，那么一个 64 位的行波进位加法器需要 64 × 多个门延迟 ≈ 100ns 以上才能得到结果。
这在现代 CPU 里是完全不可接受的——现代 CPU 每个时钟周期只有 0.3ns（3GHz）。
解决方案：超前进位加法器（Carry Lookahead Adder, CLA）。
CLA 的核心思想是：与其等待进位从低位传来，不如提前计算任何位置可能产生的进位。
对于每一位 i，定义：
- 生成（Generate）：Gᵢ = Aᵢ AND Bᵢ，表示该位无论进位输入是否为 1，都会产生进位
- 传播（Propagate）：Pᵢ = Aᵢ OR Bᵢ，表示该位会传播进来的进位
有了 G 和 P，就可以直接计算任意位的进位：
C₁ = G₀ OR (P₀ AND C₀)
C₂ = G₁ OR (P₁ AND G₀) OR (P₁ AND P₀ AND C₀)
C₃ = G₂ OR (P₂ AND G₁) OR (P₂ AND P₁ AND G₀) OR (P₂ AND P₁ AND P₀ AND C₀)
这些计算都可以并行进行——不需要等待！所有进位几乎同时算出来，然后所有位同时做最终加法。
实际效果：64 位 CLA 加法器的延迟从 100ns 缩短到约 5-10ns，快了 10-20 倍。
减法：加法的别名
你知道吗，CPU 通常没有专门的减法器？
减法被实现为加法：A - B = A + (-B)
而 -B 的计算，利用了二补数的性质：
-B = (~B) + 1
（取反加一就是负数的二补数表示）
所以：
A - B = A + (~B) + 1
在实现上：
- 对 B 取反（一个 NOT 门的功能）
- 把 Cin 设为 1（代替那个 +1）
- 送入加法器
同一个加法器，只需要一个控制信号（是否取反B，是否设Cin=1），就能同时实现加法和减法！
这个设计之美在于统一：芯片面积更小，验证更简单。
乘法器：加法的重复
乘法可以分解为移位和加法：
A × B = A × (b₃ × 2³ + b₂ × 2² + b₁ × 2¹ + b₀ × 2⁰)
= A×b₃×8 + A×b₂×4 + A×b₁×2 + A×b₀×1
这就是小学里学的"列竖式"乘法的二进制版本：
1101 (13)
× 1011 (11)
---------
1101 (13 × 1 = 13)
1101 (13 × 1，移位 = 26)
0000 (13 × 0，移位 = 0)
1101 (13 × 1，移位 = 104)
---------
10001111 (143 = 13 × 11)
每一行都是 A 左移不同位数后与 B 的某一位相乘（乘 0 或 1 很简单），然后把这些"部分积"相加。
现代 CPU 里的乘法器不是简单地串行计算这些部分积，而是用**Wallace 树（Wallace Tree）**等技术并行压缩多个部分积，使延迟接近 O(log N)。
典型数据：32 位整数乘法在现代 CPU 上只需 3-5 个时钟周期（~1ns）。
除法：最慢的基本运算
与加法（1 周期）、乘法（3-5 周期）相比，除法要慢得多：
- 32 位整数除法：通常需要 20-40 个时钟周期
- 64 位浮点除法：通常需要 15-30 个时钟周期（取决于操作数）
除法没有高效并行化的好方法——它本质上是一个迭代过程，每次迭代产生结果的一部分。这就是为什么你在优化代码时，能用乘以倒数代替除法，往往会更快：
// 慢（除法）
float result = x / 4.0f;
// 快（乘法）
float result = x * 0.25f;
编译器通常会自动优化除以常数的情况，但对于除以变量，要么手动优化，要么就接受较慢的除法。
Level 3 · 规范怎么定义的（资深）
加法器的形式化与 IEEE 标准
加法运算的硬件实现受 IEEE 754 浮点标准和 Verilog/VHDL 硬件描述语言标准（IEEE Std 1364/IEEE Std 1076）的双重约束。在整数加法层面，补码加法的溢出检测有严格的形式化定义：两个同符号操作数相加，结果符号不同则溢出。这个条件在硬件中用一个 XOR 门即可检测，其正确性由补码的数学性质保证。
在高性能加法器设计中，超前进位加法器（Carry-Lookahead Adder, CLA）的理论基础是 1958 年 Weinberger 和 Smith 的论文。CLA 将进位传播从 O(n) 降低到 O(log n)，其核心是将进位函数分解为"生成"（Generate, G=AB）和"传播"（Propagate, P=A⊕B）两个局部函数，然后用树状结构并行计算所有位的进位。更进一步的 Kogge-Stone 加法器（1973 年）和 Brent-Kung 加法器（1982 年）在理论上证明了 n 位加法的最优延迟下界是 O(log n)，最优面积-延迟乘积下界是 O(n log n)。
浮点加法器的规范更为复杂。IEEE 754 要求浮点加法必须执行"对阶-尾数相加-规格化-舍入"四个步骤，且最终结果必须等同于无穷精度运算后的正确舍入值。为满足这一要求，硬件通常需要额外的保护位（guard bit）、舍入位（round bit）和粘滞位（sticky bit）——总共 3 个额外比特来确保舍入正确性。
Level 4 · 边界与陷阱（所有人）
陷阱 1：进位链是 CPU 频率的隐形天花板
一个朴素的 64 位波纹进位加法器（Ripple Carry Adder）需要进位信号从最低位逐级传播到最高位，经过 64 级门延迟。在 5nm 工艺下，每级门延迟约 10-15 皮秒，64 级就是约 1 纳秒——对应 1GHz 的频率上限。这就是为什么现代 CPU 从不使用波纹进位加法器，而是采用 Kogge-Stone 或 Han-Carlson 等并行前缀加法器，将延迟压缩到 6-7 级门延迟（约 100 皮秒）。如果你在 FPGA 上实现自定义加法器却使用了朴素串行进位，综合工具会报出极低的最大频率——这是 FPGA 新手最常见的性能陷阱。
陷阱 2：减法溢出比加法更容易被忽视
补码减法 a - b 等价于 a + (~b + 1)，但当 b 等于该类型的最小值时，-b 本身就会溢出。例如在 32 位有符号整数中，-(-2147483648) 仍然是 -2147483648，因为 2147483648 超出了正数范围。C 标准库的 abs() 函数对 INT_MIN 的行为是未定义的。2006 年，GCC 的一个优化 pass 曾假设 abs(x) >= 0 恒成立，导致安全检查被删除，引发了一个真实的编译器 bug。
陷阱 3：浮点加法不满足结合律
整数加法满足结合律 (a+b)+c == a+(b+c)，但浮点加法不满足。经典反例：(1e20 + -1e20) + 1.0 == 1.0，但 1e20 + (-1e20 + 1.0) == 0.0，因为 -1e20 + 1.0 由于精度限制仍等于 -1e20。这意味着编译器不能随意重排浮点加法的顺序来优化——除非程序员显式使用 -ffast-math（GCC）或 /fp:fast（MSVC）放弃精度保证。科学计算中，使用 Kahan 求和算法可以将 n 个浮点数求和的误差从 O(n*eps) 降低到 O(eps)，但代价是每次加法多出 4 步运算。