运算器与加法器

概念

运算器（arithmetic unit）是 CPU 里真正"干活"的部件，核心是 ALU（Arithmetic Logic Unit，算术逻辑单元）。它接受两个操作数 $A$、$B$ 和一段操作码，输出运算结果 $F$ 与若干标志位（flag）。

一条指令"做加法"落到硬件上，就是 ALU 里的一个加法器在跳；"做减法"则不是另造一个减法器，而是用加法器加一个补码——这正是第 02 篇补码思想在硬件层的兑现。

本章的主线只有一条：怎么把"进位"这件事算快。 加法器的速度瓶颈全在进位链上。

原理

一、ALU 在 CPU 里的位置

         A ──┬──────────────┐
             │              │
         B ──┼──┐           ▼
             │  │   ┌───────────────┐
   操作码 ───┼──┼──→│      ALU      │──→ F（结果）
             │  │   └───────┬───────┘
             │  │           │
             │  │           ▼
             │  │   ┌───────────────┐
             └──┴──→│  标志位  ZF/SF │
                    │  CF/OF        │
                    └───────────────┘

ALU 内部由四部分组成：

部件	作用
加法器	算术运算（加、减）
逻辑门阵列	按位逻辑运算（与、或、非、异或）
移位器	左移、右移，是乘除 2 的基础
多路选择器（MUX，multiplexer）	按操作码从上述结果里选一个输出

"ALU 不是一堆运算电路的堆叠，而是'并行算出所有可能结果 + 选一个'。" MUX 是 ALU 的关键：所有运算同时算出来，再由操作码选中。这样 ALU 的延迟等于最慢那条路的延迟——所以加法器的速度直接决定 ALU 速度。

二、一位全加器（FA，Full Adder）

要算多位数相加，先解决一位：输入 $A_i$、$B_i$ 与低位来的进位 $C_i$，输出本位和 $S_i$ 与向高位的进位 $C_{i+1}$。

真值表（8 行，必须能背或能秒推）：

$A_i$	$B_i$	$C_i$	$S_i$	$C_{i+1}$
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

由此得两条标准逻辑式：

$$S_i=A_i\oplus B_i\oplus C_i$$$$C_{i+1}=A_i{B}_i+(A_i\oplus B_i)C_i$$

第二个式子是整个加法器世界的种子：一旦把 $A_i{B}_i$ 记作 $G_i$、$A_i\oplus B_i$ 记作 $P_i$，

$$C_{i+1}=G_i+P_i{C}_i$$

就得到了先行进位的全部依据。

• $G_i=A_i{B}_i$：进位生成（generate）。本位两个 1，必然向高位送进位，与低位无关。
• $P_i=A_i\oplus B_i$：进位传递（propagate）。本位只要来一个进位就继续往上送。

三、串行进位加法器（行波进位，ripple carry）

把 $n$ 个 FA 串起来，低位的进位输出接高位的进位输入：

C0 ─→[FA0]─C1─→[FA1]─C2─→[FA2]─→ … ─→[FA(n-1)]─→ Cn
      S0        S1        S2               S(n-1)

结构极简，但进位像水波一样一级级往上爬。设与门/或门延迟为 $t$，则每级进位要经过"与-或"两级门，共 $2t$：

$$T_{\text{串行}}=2nt(\text{纯进位链})T_{\text{全和}}\approx 2nt+2t$$

$n=32$ 时是 $66t$——这就是为什么高速 CPU 绝不用纯串行进位。

四、先行进位加法器（CLA，Carry Look-Ahead）

核心思想：不再等进位爬，而是提前把它算出来。 把 $C_{i+1}=G_i+P_i{C}_i$ 逐级代入展开，得到只依赖 $C_0$ 的表达式：

$$\begin{array}{rl}{C}_1& =G_0+P_0{C}_0\\ C_2& =G_1+P_1{G}_0+P_1{P}_0{C}_0\\ C_3& =G_2+P_2{G}_1+P_2{P}_1{G}_0+P_2{P}_1{P}_0{C}_0\\ C_4& =G_3+P_3{G}_2+P_3{P}_2{G}_1+P_3{P}_2{P}_1{G}_0+P_3{P}_2{P}_1{P}_0{C}_0\end{array}$$

所有进位都只经过"一级与 + 一级或"（两级门）就能得到，不再逐级传递。代价是逻辑式项数按 $2^i$ 增长——第 4 位就有 5 项，所以不能无限展开，只能分组。

分组策略（这是本节最常考的点）：

方案	结构	特点
组内并行 + 组间串行	4 位一组，组内 CLA，组间把进位像串行加法器一样传	实现简单，组数多时仍然慢
组内并行 + 组间并行（两级先行）	把每组再看作一位，用组进位生成 $G^{\ast }$、组进位传递 $P^{\ast }$ 做第二级 CLA	快，是标准做法

两级的衔接靠组进位信号：

$$G^{\ast }=G_3+P_3{G}_2+P_3{P}_2{G}_1+P_3{P}_2{P}_1{G}_0,P^{\ast }=P_3{P}_2{P}_1{P}_0$$

含义与单个位完全一致——把"一组 4 位"当成"一位"，就能递归套用同一套公式。

五、用加法器做减法

$$A-B=A+(-B)=A+\overline{B}+1$$

硬件上只需两处改动：

1. 在 $B$ 的每一位前面插一个异或门，另一端接控制信号 SUB。SUB = 0 时 $B_i\oplus 0=B_i$（原样通过）；SUB = 1 时 $B_i\oplus 1=\overline{B_i}$（取反）。
2. 把 SUB 直接接到加法器的最低位进位输入 $C_0$。做减法时 $C_0=1$，正好补上那个"+1"。

一个控制信号同时完成"取反"和"加一"，这就是补码设计的优雅之处：加法和减法共用同一套电路，只是 B 端和 C0 不同。

六、ALU 的操作选择与 74181

以 8 种操作为例，操作码 3 位即可覆盖：

操作码	运算	结果通路
000	$A+B$	加法器
001	$A-B$	加法器（B 取反、$C_0=1$）
010	$A\wedge B$	逻辑门阵列
011	$A\vee B$	逻辑门阵列
100	$A\oplus B$	逻辑门阵列
101	$\overline{A}$	逻辑门阵列
110	$A+1$	加法器（$B=0$、$C_0=1$）
111	$A$	直通

末尾的 MUX 由操作码选通一路输出。

74181 是经典的 4 位 ALU 芯片，它把上面这些东西集成为一片：

• $M$ 引脚：$M=0$ 做算术运算，$M=1$ 做逻辑运算。
• $S_3{S}_2{S}_1{S}_0$：选择具体的 16 种运算（与、或、异或、加、减、传送等）。
• $C_n$：最低位进位输入，做减法时置 1。
• 内部就是先行进位结构，另提供组进位输出 $G$、$P$ 供多片级联做第二级先行。

记 74181 只需抓两条：M 管"算术还是逻辑"，S 管"哪一种"，Cn 管"加不加 1"。

七、标志位的生成

标志	含义	生成方式
ZF（zero）	结果为零	结果各位全 0 的或非
SF（sign）	结果符号	直接取结果最高位
CF（carry）	进位/借位	加法器的最高位进位 $C_n$（减法时表示借位）
OF（overflow）	有符号溢出	$C_n\oplus C_{n-1}$

CF 与 OF 的分工必须分清：CF 服务于无符号数（第 $n$ 位向外的进位），OF 服务于有符号数（符号位被错误改写）。同一次加法，两个标志可能一个置位一个不置位。

示例

例 1：验证全加器逻辑式（真值表全覆盖）

完整验证过程：

对 8 种输入组合，用两条逻辑式各算一遍，与真值表对照：

$A_i$	$B_i$	$C_i$	$A_i{B}_i$	$A_i\oplus B_i$	$S_i=A\oplus B\oplus C$	$C_{i+1}=AB+(A\oplus B)C$
0	0	0	0	0	0	$0+0\cdot 0=0$
0	0	1	0	0	1	$0+0\cdot 1=0$
0	1	0	0	1	1	$0+1\cdot 0=0$
0	1	1	0	1	0	$0+1\cdot 1=1$
1	0	0	0	1	1	$0+1\cdot 0=0$
1	0	1	0	1	0	$0+1\cdot 1=1$
1	1	0	1	0	0	$1+0\cdot 0=1$
1	1	1	1	0	1	$1+0\cdot 1=1$

八行与真值表逐行一致，逻辑式正确。

例 2：串行进位加法器的延迟

设与门、或门延迟均为 $1t$，异或门延迟 $2t$。求 16 位、32 位串行进位加法器的延迟。

完整计算过程：

第一步，单级进位延迟。从 $A_i,B_i,C_i$ 到 $C_{i+1}$，走的是 $G_i+P_i{C}_i$ 这条"与-或"路径：

• 求 $G_i=A_i{B}_i$：$1t$
• 求 $P_i{C}_i$：与门 $1t$（$P_i$ 已算好时）
• 求 $C_{i+1}$：或门 $1t$

共 $2t$（在 $G_i$、$P_i$ 已就绪的前提下）。

第二步，$n$ 位进位链总延迟：

$$T_{\text{进位链}}=2nt$$

第三步，代入：

$$T_{16}=2\times 16t=32t,T_{32}=2\times 32t=64t$$

第四步，算最终和还要在末位加一级异或门（$S_i=A_i\oplus B_i\oplus C_i$ 需要等进位到齐）：

$$T_{\text{全和},16}=32t+2t=34t,T_{\text{全和},32}=64t+2t=66t$$

结论：延迟随位数线性增长，32 位要 $66t$。位数翻倍，延迟就翻倍——这是串行进位的死穴。

例 3：4 位先行进位的进位展开（逐项验证）

$A=0111$，$B=0001$，$C_0=0$。用先行进位展开式求 $C_1\sim C_4$，并与串行加法器的进位链对照。

完整计算过程：

第一步，逐位求 $G_i$、$P_i$：

$i$	$A_i$	$B_i$	$G_i=A_i{B}_i$	$P_i=A_i\oplus B_i$
0	1	1	1	0
1	1	0	0	1
2	1	0	0	1
3	0	0	0	0

即 $G=(G_3{G}_2{G}_1{G}_0)=0001$，$P=(P_3{P}_2{P}_1{P}_0)=0110$。

第二步，代入展开式：

$$C_1=G_0+P_0{C}_0=1+0\cdot 0=\mathbf{1}$$$$C_2=G_1+P_1{G}_0+P_1{P}_0{C}_0=0+1\cdot 1+1\cdot 0\cdot 0=\mathbf{1}$$$$C_3=G_2+P_2{G}_1+P_2{P}_1{G}_0+P_2{P}_1{P}_0{C}_0=0+0+1\cdot 1\cdot 1+0=\mathbf{1}$$$$C_4=G_3+P_3{G}_2+P_3{P}_2{G}_1+P_3{P}_2{P}_1{G}_0+P_3{P}_2{P}_1{P}_0{C}_0=0+0+0+0+0=\mathbf{0}$$

第三步，与串行加法器对照。 逐位做全加：

$i$	$A_i$	$B_i$	$C_i$	$S_i$	$C_{i+1}$
0	1	1	0	0	1
1	1	0	1	0	1
2	1	0	1	0	1
3	0	0	1	1	0

串行进位链为 $(C_1,C_2,C_3,C_4)=(1,1,1,0)$，与先行进位的结果完全一致。

第四步，读结果。 $S=1000$，$C_4=0$。$7+1$ 在 4 位下有符号意义下溢出了（$1000$ 读作 $-8$），但先行进位算法本身没有任何问题——它只是忠实地算出了 4 位结果。

物理含义解读：$C_2$ 之所以为 1，走的是 $P_1{G}_0$ 这条路——第 0 位产生了进位（$G_0=1$），第 1 位是"传递位"（$P_1=1$），于是进位被一路送了上去。$C_3$ 同理走 $P_2{P}_1{G}_0$。先行进位的本质，就是把"进位从哪来、经过谁"一次性写成布尔表达式，用两级门同时算出来。

例 4：先行进位到底快多少

仍用与门/或门 $1t$、异或门 $2t$ 的假设，比较 16 位加法器的三种实现。

完整计算过程：

方案 A：16 位纯串行

$$T_A=2\times 16t+2t=34t$$

方案 B：4 位一组、组内并行、组间串行

• 求所有 $G_i$、$P_i$：$2t$（$P_i$ 用异或门）
• 组内 4 个进位由两级门生成：$2t$
• 组间进位要穿过 4 个组，每组经"组进位生成/传递 + 组间与或"共 $2t$：$4\times 2t=8t$
• 末级求和异或：$2t$

$$T_B=2+2+8+2=14t$$

更精细的账：组内进位的展开式最长有 5 项，需要"与门一层 + 或门一层"，取 $2t$ 是合理的估计。若题目给的假设不同（例如异或门也算 $1t$），按题目的假设代。

方案 C：两级先行（组内并行 + 组间并行）

• 求 $G_i$、$P_i$：$2t$
• 组进位生成 $G^{\ast }$、$P^{\ast }$：$1t$（与-或一层）
• 第二级先行算出各组进位：$1t$
• 组内进位展开：$2t$
• 末级求和异或：$2t$

$$T_C=2+1+1+2+2=8t$$

加速比对照：

方案	延迟	相对串行提速
A 纯串行	$34t$	1.00×
B 组内先行、组间串行	$14t$	2.43×
C 两级先行	$8t$	4.25×

结论：先行进位把进位延迟从"随位数线性增长"压到了"随分组层数增长"。位数越多，收益越大——这也是为什么现代 CPU 的加法器普遍采用多级先行 + 分组的结构。

例 5：用加法器做减法

用 4 位加法器计算 $7-5$ 与 $5-7$。

完整计算过程：

第一步，套公式 $A-B=A+\overline{B}+1$。

情形一：$7-5$

$$\overline{B}=\overline{0101}=1010$$$$A+\overline{B}+1=0111+1010+1=10010$$

最高位进位 $C_4=1$ 被丢弃（4 位寄存器装不下），结果 0010 $=+2$ ✓

情形二：$5-7$

$$\overline{B}=\overline{0111}=1000$$$$A+\overline{B}+1=0101+1000+1=1110$$

$C_4=0$，无进位丢弃。1110 按 4 位补码读：$-8+4+2=-2$ ✓

关键结论：同一个加法器，只改 SUB 信号就同时支持加法和减法，且结果的"有无进位"恰好对应无符号意义的 CF 标志（$7-5$ 有进位，表示不需要借位；$5-7$ 无进位，表示发生了借位）。

例 6：溢出标志 OF 的计算

用 $C_n\oplus C_{n-1}$ 判断 4 位补码加法的溢出。

完整计算过程：

运算	$A+B$	$C_n$	$C_{n-1}$	OF	真值和	结论
$7+1$	0111 + 0001	0	1	1	8	溢出
$5+3$	0101 + 0011	0	1	1	8	溢出
$5+5$	0101 + 0101	0	1	1	10	溢出
$3+4$	0011 + 0100	0	0	0	7	不溢出

以 $5+5$ 为例逐位展开：

$i$	$A_i$	$B_i$	$C_i$	$S_i$	$C_{i+1}$
0	1	1	0	0	1
1	0	0	1	1	0
2	1	1	0	0	1
3	0	0	1	1	0

$C_3=1$（次高位向最高位有进位），$C_4=0$（最高位向外无进位），$C_4\oplus C_3=1$ → 溢出。

物理解释：进位"进了符号位却没出来"，说明符号位被硬生生推翻了。$5+5$ 本该是 $+10$，结果 1010 读作 $-6$，符号由正变负——这就是溢出的现场。

例 7：C 代码——模拟全加器与四级先行进位

本机不提供代码运行能力，runnable 标记仅为将来接入运行件预留；请自行在本地编译验证。

#include <stdio.h>

/* 一位全加器 */
static void fa(int a, int b, int cin, int *s, int *cout) {
    *s    = a ^ b ^ cin;
    *cout = (a & b) | ((a ^ b) & cin);
}

/* 串行进位：返回进位链 C1..Cn */
static void ripple(int a, int b, int n, int *C) {
    int c = 0;
    for (int i = 0; i < n; i++) {
        int s, co;
        fa((a >> i) & 1, (b >> i) & 1, c, &s, &co);
        c = co;
        C[i] = c;                 /* C1..Cn */
    }
}

/* 4 位先行进位：G/P + 展开式 */
static void cla4(int a, int b, int c0, int *C) {
    int G[4], P[4];
    for (int i = 0; i < 4; i++) {
        int ai = (a >> i) & 1, bi = (b >> i) & 1;
        G[i] = ai & bi;
        P[i] = ai ^ bi;
    }
    C[0] = G[0] | (P[0] & c0);
    C[1] = G[1] | (P[1] & G[0]) | (P[1] & P[0] & c0);
    C[2] = G[2] | (P[2] & G[1]) | (P[2] & P[1] & G[0]) | (P[2] & P[1] & P[0] & c0);
    C[3] = G[3] | (P[3] & G[2]) | (P[3] & P[2] & G[1])
         | (P[3] & P[2] & P[1] & G[0]) | (P[3] & P[2] & P[1] & P[0] & c0);
}

int main(void) {
    int cases[4][2] = {{7,1},{5,3},{3,4},{5,5}};
    for (int k = 0; k < 4; k++) {
        int a = cases[k][0], b = cases[k][1];
        int Cr[4], Cc[4];
        ripple(a, b, 4, Cr);
        cla4(a, b, 0, Cc);
        int Cn = Cr[3], Cnm1 = Cr[2];
        printf("a=%d b=%d 串行 C=%d%d%d%d  先行 C=%d%d%d%d  相同=%s  OF=%d\n",
               a, b, Cr[0], Cr[1], Cr[2], Cr[3],
               Cc[0], Cc[1], Cc[2], Cc[3],
               (Cr[0]==Cc[0] && Cr[1]==Cc[1] && Cr[2]==Cc[2] && Cr[3]==Cc[3]) ? "是" : "否",
               Cn ^ Cnm1);
    }

    /* 减法：A + ~B + 1 */
    int a = 7, b = 5;
    int sub = (a + (~b & 0xF) + 1) & 0xF;
    printf("\n7 - 5 = %d\n", sub);
    a = 5; b = 7;
    sub = (a + (~b & 0xF) + 1) & 0xF;
    printf("5 - 7 = %d (4 位补码)\n", sub >= 8 ? sub - 16 : sub);
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

a=7 b=1 串行 C=1110  先行 C=1110  相同=是  OF=1
a=5 b=3 串行 C=1110  先行 C=1110  相同=是  OF=1
a=3 b=4 串行 C=0000  先行 C=0000  相同=是  OF=0
a=5 b=5 串行 C=1010  先行 C=1010  相同=是  OF=1

7 - 5 = 2
5 - 7 = -2 (4 位补码)

与例 3、例 5、例 6 的结果逐项吻合。

例 8：Python 对照与验算

def ripple(a, b, n):
    c, car = 0, []
    for i in range(n):
        ai, bi = (a >> i) & 1, (b >> i) & 1
        c = (ai & bi) | ((ai ^ bi) & c)
        car.append(c)
    return car

def cla(a, b, c0=0):
    G = [((a >> i) & 1) & ((b >> i) & 1) for i in range(4)]
    P = [((a >> i) & 1) ^ ((b >> i) & 1) for i in range(4)]
    C = []
    for i in range(4):
        s, term = G[i], 1
        for j in range(i - 1, -1, -1):
            term *= P[j + 1]
            s += term * G[j]
        term *= P[0]
        C.append(1 if (s + term * c0) else 0)
    return G, P, C

for a, b in [(7, 1), (5, 3), (3, 4), (5, 5)]:
    car = ripple(a, b, 4)
    G, P, C = cla(a, b)
    print('a=%s b=%s 串行=%s 先行=%s 一致=%s G=%s P=%s OF=%d'
          % (format(a, '04b'), format(b, '04b'), car, C, car == C, G, P,
             car[3] ^ car[2]))

# 延迟模型：与/或 = 1t，异或 = 2t
print('串行 16 位 = %dt ; 32 位 = %dt' % (2*16 + 2, 2*32 + 2))
print('16 位组内先行组间串行 = %dt ; 两级先行 = %dt ; 提速 %.2f 倍'
      % (2 + 2 + 8 + 2, 2 + 1 + 1 + 2 + 2, (2*16 + 2) / 8))

# 减法通路
for a, b in [(7, 5), (5, 7), (25, 38)]:
    n = 4 if max(a, b) < 16 else 8
    s = (a + (~b) + 1) & ((1 << n) - 1)
    print('%d - %d = %s = %d' % (a, b, format(s, '0%db' % n),
                                 s - (1 << n) if s >= (1 << (n - 1)) else s))

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出对照：串行进位链与先行进位链在 4 组测试数据上全部一致，OF 结果与例 6 表一致，减法结果 $2$ / $-2$ / $-13$ 与例 5 一致。

考点

考点

1. 必背公式

• 全加器：$S_i=A_i\oplus B_i\oplus C_i$，$C_{i+1}=A_i{B}_i+(A_i\oplus B_i)C_i$
• 进位生成 / 传递：$G_i=A_i{B}_i$，$P_i=A_i\oplus B_i$，$C_{i+1}=G_i+P_i{C}_i$
• 串行进位延迟：$2nt$（进位链），$2nt+2t$（含末级求和）
• 减法通路：$A-B=A+\overline{B}+1$（$B$ 取反 + $C_0=1$）
• 溢出：$\text{OF}=C_n\oplus C_{n-1}$

2. 高频陷阱

• "算术运算还是逻辑运算"看 M 引脚，不看 S 引脚。74181 的 $M$ 是一级总开关，$S_3{S}_2{S}_1{S}_0$ 只在选中的那一类里细分。
• "最高位有进位"不等于溢出。反例：$5+5$ 在 4 位下 $C_4=0$ 却溢出。必须用 $C_n\oplus C_{n-1}$。
• OF 与 CF 服务不同的数制：CF 管无符号（第 $n$ 位往外有没有进位），OF 管有符号（符号位有没有被推翻）。判断"溢出"时先看题目说的是有符号还是无符号。
• 串行进位的延迟与位数成正比，别答成 $\log n$。
• 先行进位的展开式项数指数增长，所以必须分组。4 位一组时 $C_4$ 有 5 项，这就是"为什么是 4 位一组"的标准答案。
• 两级先行的第二级是"把组当成位"：$G^{\ast }$、$P^{\ast }$ 的定义与单个位的 $G$、$P$ 形式完全相同，只是位数加宽。
• 减法的 $C_0$ 必须置 1。只对 $B$ 取反而忘了 $+1$，结果会差 1——这是最典型的失分点。
• ALU 是"MUX 选结果"，不是"按需造电路"。所有运算并行完成，延迟取决于最慢路径。

3. 解题模板（"算 n 位加法器延迟"）

① 确认题目给的假设：与/或门几 t，异或门几 t
② 串行：进位链 = 2nt，再加末级求和
③ 先行：G/P 一级 → 组内进位两级 →（若两级）组进位生成 + 组间进位 → 末级求和
④ 报告时写清"假设"两字，避免与题目设定的门延迟不匹配

4. 与后续章节的接口

• 本节加法器是第 30 篇数据通路的核心部件：PC 加 1、访存地址计算都靠它。
• 标志位 OF/CF/ZF/SF 直接对应第 20 篇指令系统里的条件转移指令。
• 第 32 篇流水线会再提：加法器延迟直接决定 ALU 类指令的时钟周期下界。

小结

• 一位全加器是地基：$S=A\oplus B\oplus C_i$，$C_{i+1}=AB+(A\oplus B)C_i$。
• 串行进位结构最简单，但延迟 $2nt$ 随手位数线性增长，位数一多就不可接受。
• 先行进位把进位写成只依赖 $C_0$ 的布尔式，用两级门一次性算出，代价是逻辑项指数增长，因此必须分组 + 多级。
• 减法用加法做：$A+\overline{B}+1$，一个 SUB 信号同时完成取反和加一。
• ALU = 运算部件 + MUX，操作码选结果；CF 管无符号，OF 管有符号，$OF=C_n\oplus C_{n-1}$。

下一篇：存储系统概述