学习 › 第 7 讲

二进制加法器：半加器、全加器与串行进位加法器

阅读约 8 分钟 · bitGateLab 团队

加法是计算机中最重要的运算：减法、乘法、存储器地址的计算和事件计数都要靠它。本文将带你从零搭建一个加法器：先是一位的半加器，然后是能接收进位的全加器，接着是多位的串行进位加法器，最后看看同一个电路如何利用补码做减法。

手算二进制加法

两个二进制位相加的规则有四条：0 + 0 = 0，0 + 1 = 1，1 + 0 = 1，1 + 1 = 10₂，也就是本位得 0，并向下一列进 1。如果还有一个进位过来，则 1 + 1 + 1 = 11₂：本位得 1，进位为 1。和十进制一样，从右到左逐列相加，把进位传给左边一列。

半加器

半加器把 A 和 B 两个位相加，给出两个输出：和 S 与进位 C。

A	B	C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

S 列是 XOR 的真值表，C 列是 AND 的真值表。因此：

S = A ⊕ B C = AB

半加器：XOR 门给出和 S，AND 门给出进位 C。圆点表示每个输入在此处分支，分别接到两个门。

之所以叫“半”加器，是因为它没有接收前一列进位的输入端，所以只能用于最低位。

全加器

全加器把三个位相加：A、B 和进位输入 C_in。它给出和 S 与进位输出 C_out。注意，(C_out, S) 这一对值用二进制表示的，正是各输入中 1 的个数。

A	B	C_in	C_out	S
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

当 1 的个数为奇数时 S 为 1：S = Σm(1, 2, 4, 7) = A ⊕ B ⊕ C_in。当有两个或更多个 1 时 C_out 为 1：C_out = Σm(3, 5, 6, 7)，化简后就是多数表决函数：

C_out = AB + AC_in + BC_in

如果你试着在 S 的卡诺图上画圈，会发现没有任何一个 1 与另一个 1 相邻：这是 XOR 特有的棋盘格图案，无法化简成更简单的与或式。

用两个半加器构成全加器

一种实用的搭法是把两个半加器和一个 OR 门串接起来：

第一个半加器：P = A ⊕ B，G = AB。
第二个半加器，输入为 P 和 C_in：S = P ⊕ C_in，以及一个部分进位 P·C_in。
C_out = G + P·C_in = AB + (A ⊕ B)C_in。

这个表达式与多数表决式等价：如果 A 和 B 都为 1，AB 已经产生进位；如果两者中恰好有一个为 1，进位就取决于 C_in。G 称为进位生成信号，P 称为进位传递信号。

串行进位加法器

要把 n 位的数相加，就把 n 个全加器排成一排连接起来：每一级的 C_out 作为下一级的 C_in。第一级的 C_in 置为 0，最后一级的 C_out 就是最终进位。这种结构称为串行进位加法器，也叫行波进位（ripple carry）加法器，因为进位像波浪一样逐级“传播”。74HC 系列中有一种芯片，内部就是四个已经这样连接好的全加器（74HC283）。

例 1：用 4 位加法器计算 1011 + 0110。用十进制表示就是 11 + 6。

级	A_i	B_i	C_in	S_i	C_out
0	1	0	0	1	0
1	1	1	0	0	1
2	0	1	1	0	1
3	1	0	1	0	1

和：S₃S₂S₁S₀ = 0001，最终进位为 1，即 10001₂ = 17。正确：11 + 6 = 17，4 位放不下，所以出现了最终进位。

代价是时间。第 3 级必须等第 2 级的进位到达后才能给出最终结果，而第 2 级又要等第 1 级的进位。如果每一级产生进位需要两级门的延迟，那么 n 位加法器在最坏情况下大约需要 2n 个门延迟。对 64 位来说这太慢了，所以处理器使用超前进位加法器，由 G 和 P 信号并行地算出各个进位。在模拟器的时序图中，你可以看到输出是如何一步一步变化、直到稳定下来的。

用同一个加法器做减法

正如数制一文所述，在补码中 B 的相反数是 B + 1。于是：

A − B = A + B + 1

要实现它，只需在 B 的每一位上加一个 XOR 门，XOR 门的另一个输入接到控制线 M，同时把 M 也接到第一级的 C_in。当 M = 0 时，XOR 门让 B 原样通过，且 C_in = 0：电路做加法。当 M = 1 时，XOR 门把 B 取反，而 C_in = 1 提供了那个“+1”：电路做减法。

例 2：4 位减法。

9 − 5：A = 1001，B = 0101，B = 1010。1001 + 1010 + 1 = 1 0100。丢弃最终进位：0100 = 4。
5 − 9：A = 0101，B = 1001，B = 0110。0101 + 0110 + 1 = 0 1100。没有最终进位。1100 按补码解释等于 −8 + 4 = −4。

无符号数相减时，最终进位表明是否发生了借位：1 表示 A ≥ B，0 表示 A < B。

对于有符号数，只用一个 XOR 门就能检测溢出：V = C₃ ⊕ C₄，其中 C₃ 是进入最后一级的进位，C₄ 是从最后一级输出的进位。如果两者不同，说明结果超出了 4 位有符号数的表示范围。

常见错误

在中间各级使用半加器。凡是要接收进位的级都必须用全加器。
让第一级的 C_in 悬空。做加法时它应接 0，在加减法器中则应接 M。
把最终进位和溢出混为一谈。对有符号数，最终进位应丢弃；溢出要用 C₃ ⊕ C₄ 来检测。
做减法时忘了“+1”，只接了反相器：结果会比正确值小一。
用 OR 写成 S = A + B + C_in。一位的和是 XOR，不是 OR。

在模拟器中试一试

在编辑器里搭一个加法器，是连接逻辑门与算术运算的最好桥梁。先从一位开始，再扩展到四位。

放置两个输入、一个 XOR 门和一个 AND 门，按半加器的电路图连接。生成它的真值表。
用两个半加器和一个 OR 门搭出全加器，并对照本文的真值表核对它的 8 行。
把全加器复制四份，并把进位串接起来。把第一个 C_in 置为 0。
把输入设为 1011 和 0110，观察输出应为 0001，最终进位为 1。
打开时序图，改变一个能迫使进位走完四级的输入（例如 1111 + 0001），观察各输出是如何稳定下来的。

练习

计算 S 和 C_out：全加器的输入为 A = 1，B = 0，C_in = 1。
答案
有两个 1：S = 0，C_out = 1（1 + 0 + 1 = 10₂）。
用 4 位加法器计算 0111 + 0101，并指出每一级的进位。
答案
第 0 级：1 + 1 = 0，进位 1。第 1 级：1 + 0 + 1 = 0，进位 1。第 2 级：1 + 1 + 1 = 1，进位 1。第 3 级：0 + 0 + 1 = 1，进位 0。结果为 1100 = 12（7 + 5）。
用 4 位加减法器计算 6 − 3，并写出 M 的取值。
答案
M = 1。0110 + 1100 + 1 = 1 0011。丢弃进位：0011 = 3。
把它们看作 4 位有符号数，0111 + 0101 会溢出吗？
答案
会。7 + 5 = 12 超出了 −8 到 +7 的范围。结果 1100 会被读成 −4。进位为 C₃ = 1，C₄ = 0，V = 1 ⊕ 0 = 1。