从加法器到 ALU

概念

上一篇（组合逻辑）我们学会了把任意逻辑功能变成电路。这一篇要回答的是再上一层的问题：

$$\boxed{{\displaystyle \text{一堆门和译码器、选择器，怎么拼成一个"会算数的部件"？}}}$$

答案就是 ALU（Arithmetic Logic Unit，算术逻辑单元）——CPU 里真正"干活"的那块电路。

它的接口只有三样：

端口	说明
操作数 $A$、$B$	两个 $n$ 位输入
操作码	告诉它"这次做哪种运算"
结果 $F$ + 标志位	$n$ 位输出 + 若干状态位（ZF/SF/CF/OF）

ALU 不是"一堆运算电路的堆叠"，而是：

$$\boxed{{\displaystyle \text{所有运算同时算出来，再用多路选择器（MUX）按操作码挑一个}}}$$

回忆上一篇的结论——"$2^{n-1}$ 选 1 MUX + 反相器 = 任意 $n$ 变量函数"。ALU 正是这条原理最壮观的落地：它就是那个"巨大的多路选择器"，只不过它选择的是运算结果，而不是普通逻辑位。

本层（L1 电路）在这里回答了上一层（L2 组成原理）最核心的问题：CPU 数据通路里那个"在跳的加法器"是怎么来的。下一层会直接用这里的加法器、移位器和标志位去搭数据通路。

原理

一、从半加器到全加器：模块化组装的第一步

**半加器（HA）**只加两个位，不管低位来的进位：

$A$	$B$	$S$（和）	$C$（进位）
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

$$S=A\oplus B,C=AB$$

半加器的缺陷：只能当"最低位"。高位的加法必须接收低位送来的进位，所以要三个输入。

**全加器（FA）**加三个位：$A_i$、$B_i$ 和低位进位 $C_i$。

       A_i ──┬───────────┐
             │  ┌─────┐  │  ┌─────┐
       B_i ──┼─→│ XOR │──┼─→│ XOR │──→ S_i = A_i ⊕ B_i ⊕ C_i
             │  └─────┘  │  └──┬──┘
             │           │     ↑
       C_i ──┼───────────┼─────┘
             │           │
             │  ┌─────┐  │  ┌─────┐
             └─→│ AND │──┴─→│ OR  │──→ C_{i+1} = A_iB_i + (A_i⊕B_i)C_i
                └─────┘     └─────┘

真值表（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\equiv G_i+P_i{C}_i$$

这两个新符号是整章的地基：

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

为什么 $P$ 用异或而不是或？ 因为 $A_i+B_i=1$ 有两种情况；当 $A_i=B_i=1$ 时，本位自己就生成进位了（由 $G_i$ 负责），不需要"传递"这个身份。用异或才能把两种身份互斥地分开——这是设计上的关键一笔。

二、多位加法器：全部瓶颈都在进位链上

把 $n$ 个全加器串起来：

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

串行进位（行波进位）：进位像水波一样一级级往上爬。设与门、或门延迟为 $t$，则每级进位走"与-或"两级门 = $2t$：

$$T_{\text{进位链}}=2nt,T_{\text{全和}}\approx 2nt+2t$$

$n=32$ 时是 $66t$——延迟随手位数线性增长，这就是高速 CPU 绝不用纯串行进位的原因。

先行进位（CLA）：不再等进位爬，而是提前把它算出来。把 $C_{i+1}=G_i+P_i{C}_i$ 逐级代入展开：

$$\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$ 增长（$C_4$ 已 5 项），所以不能无限展开，必须分组：

方案	结构	延迟（16 位，与/或 = $1t$、异或 = $2t$）
A 纯串行	无分组	$2\times 16+2=\mathbf{34}\mathbf{t}$
B 组内并行 + 组间串行	4 位一组，组内 CLA，组间像串行一样传	$2+2+8+2=\mathbf{14}\mathbf{t}$（2.43×）
C 两级先行	组内并行 + 组间也用组进位 $G^{\ast }$/$P^{\ast }$ 并行	$2+1+1+2+2=\mathbf{8}\mathbf{t}$（4.25×）

两级的衔接靠组进位信号，形式与单个位完全一样（把"一组 4 位"当成"一位"）：

$$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$$

一句话记法：先行进位 = 把"进位从哪来、经过谁"一次性写成布尔表达式。 位数越多收益越大（16 位提速 4.25×，32 位更悬殊），所以现代 ALU 普遍是多级先行 + 分组。

三、减法不进新电路：一个信号搞定

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

硬件只改两处：

        ┌─────┐
B_i ───→│ XOR │──→ 送加法器 B 端      SUB = 0 → 原样通过
        └──┬──┘                        SUB = 1 → 按位取反
           ↑
         SUB ──────────────→ 加法器最低位进位 C0

一个 SUB 信号同时完成"取反"和"加一"——这就是补码设计最优雅的地方：加减法共用同一套电路。

四、ALU 的骨架：并行算 + MUX 选

现在把上面这些装成一个部件。设操作码 3 位（$O{P}_{2}O{P}_{1}O{P}_0$），ALU 内部是8 条并行通路 + 1 个 8 选 1 MUX：

                ┌──────────────────────────────┐
                │            加法器            │── D0 = A + B
                │   (B 取反 + C0 由 SUB 控制)  │── D1 = A - B
                ├──────────────────────────────┤
                │   AND 阵  ─────────────────  │── D2 = A & B
                │   OR  阵  ─────────────────  │── D3 = A | B
                │   XOR 阵  ─────────────────  │── D4 = A ^ B
                │   NOT 阵  ─────────────────  │── D5 = ~A
                ├──────────────────────────────┤
                │   A + 1（B 接 0、C0 = 1）    │── D6 = A + 1
                │   直通 A ──────────────────  │── D7 = A
                └──────────────────────────────┘
                              │
             OP2 OP1 OP0 ───→ │  8 选 1 MUX  │───→ F（结果）
                              └──────────────┘

操作码	运算	走哪条路
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 只挑一条。

• 优点：控制逻辑极简——操作码直接接 MUX 的选择端，不需要"先译码再逐个使能"。
• 代价：延迟等于最慢那条路。加法器最长，所以：

$$\boxed{{\displaystyle \text{ALU 的速度 = 加法器的速度}}}$$

这就是为什么前面要用先行进位把加法器做快——ALU 的整体性能由它决定。

五、逻辑运算与移位器

逻辑运算就是上一篇的"按位布尔运算"，一个字宽 $n$ 并存 $n$ 个相同的门：

A:  1 0 1 1
B:  0 1 1 0
──────────────── 按位独立，位与位之间"老死不相往来"
AND: 0 0 1 0     OR: 1 1 1 1     XOR: 1 1 0 1

移位器是乘除 $2^k$ 的硬件基础，最简单的做法是多级 MUX 级联：

一位左移：  2 选 1 MUX × n         ┌─ 0        （最低位补 0）
                                  ├─ 原样
                                  └─ 上一位

四位"桶形移位器"（barrel shifter）：
  第 1 级：移 1 位（选择端 = shamt[0]）
  第 2 级：移 2 位（选择端 = shamt[1]）
  ⇒ log2(n) 级就能实现 0 ~ n-1 位任意移位

移位器类型	级数	延迟	用途
逐位串行移位	$n$ 级	$O(n)$	简单，慢
桶形移位器	${\log }_{2}n$ 级	$O(\log n)$	现代 CPU 标配

为什么是 ${\log }_{2}n$？ 因为移位数 $k$ 的二进制每一位对应"移还是不移"——$k$ 有几位，就需要几级。这与"用 $2^{n-1}$ 选 1 MUX 实现 $n$ 变量函数"是同一个思想：用输入的二进制位来选通。

六、标志位：ALU 的"副产品"

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

两个易混点必须钉死：

1. CF 与 OF 服务不同的数制。CF 管无符号（第 $n$ 位往外有没有进位），OF 管有符号（符号位有没有被推翻）。同一次加法，两个标志可能一个置位一个不置位。
2. "最高位有进位" ≠ 溢出。反例：4 位下 $5+5$，$C_4=0$（没往外出）却溢出了。因为进位"进了符号位却没出来"，符号被硬推翻。必须用 $C_n\oplus C_{n-1}$。

七、74181：把 ALU 做进一片芯片

74181 是经典的 4 位 ALU 芯片，就是上面那张结构图的集成电路版：

引脚	作用
$M$	$M=0$ 做算术，$M=1$ 做逻辑（一级总开关）
$S_3{S}_2{S}_1{S}_0$	4 位功能选择，在这两大类里细分 16 种运算
$C_n$	最低位进位输入（做减法时置 1）
$\overline{G}$、$\overline{P}$	组进位生成 / 传递输出，供第二级先行使用
$A=B$	相等指示输出（集电极开路，多片可"线与"）

记 74181 只抓三条：$M$ 管"算术还是逻辑"，$S$ 管"哪一种"，$C_n$ 管"加不加 1"。 （完整 16 种运算对照表请查数据手册；考题一般只考这三条的含义和它内部是先行进位这一点。）

位扩展就是分组：4 片 74181 拼成 16 位 ALU。两种接法正好对应前面方案 B / C：

【方案 B：串行进位】片间直接用 Cn / Cn+4（即低片的最高位进位）串联
   Cn ─→[74181]─Cn+4─→[74181]─→[74181]─→[74181]─→ C16
   ⇒ 16 位延迟 = 14t（组内先行、组间串行）

【方案 C：两级先行】每片的 G、P 输出送到一片 74182 先行进位部件
   G1 P1 ┐            ┌─→ 产生各组进位，回送各片的 Cn
   G2 P2 ├─→ [74182] ─┤
   G3 P3 │            └─→ 同时给出全字进位 C16
   G4 P4 ┘
   ⇒ 16 位延迟 = 8t（真正的两级先行）

74181 + 74182 是教科书上的经典搭档——前者做组内 4 位，后者做组间。这就是"两级先行"从公式变成器件的现场。

八、ALU 的"约束条件"清单

设计 ALU 时还要顺带考虑几件事（考试常作为附加问）：

约束	说明
位宽一致	所有通路都是 $n$ 位，MUX 也是 $n$ 位宽
延迟取最慢路	加法器，所以提速要从进位链下手
扇入限制	CLA 展开式项数多，受门扇入限制 → 必须分组
标志位的产生时机	标志必须在结果稳定后产生，否则会采到毛刺（承接上一篇"竞争冒险"）
无法做乘法	乘法要靠"移位 + 加法 + 循环"或专用乘法器，不在基础 ALU 内（后续组合逻辑可扩展）

示例

例 1：全加器与串行/先行进位链的一致性（逐位验证）

取 $A=0110$，$B=0011$，$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	0	1	0	1
1	1	1	1	0
2	1	0	0	1
3	0	0	0	0

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

第二步，代入先行进位展开式：

$$C_1=G_0+P_0{C}_0=0+1\cdot 0=\mathbf{0}$$$$C_2=G_1+P_1{G}_0+P_1{P}_0{C}_0=1+0+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+1\cdot 1+0+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+(\cdots )C_0=0+0+0+0+0=\mathbf{0}$$

第三步，用串行加法器逐位对照：

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

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

第四步，读结果。 $S=1001=9$，$C_4=0$。$6+3=9$ 正确；无符号意义下没溢出（$C_4=0$），但有符号意义下溢出了（4 位补码最大 $+7$）——见例 4。

例 2：16 位加法器三种实现的延迟（完整计算）

假设与门、或门延迟 $1t$，异或门延迟 $2t$。求 16 位加法器三种实现的延迟与提速比。

方案 A：纯串行

$$T_A=\underset{\mathrm{进}\mathrm{位}\mathrm{链}}{\underbrace{2\times 16}}+\underset{\mathrm{末}\mathrm{级}\mathrm{异}\mathrm{或}}{\underbrace{2}}=34t$$

方案 B：4 位一组，组内先行、组间串行（= 4 片 74181 直接用 Cn/Cn+4 串联）

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

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

方案 C：两级先行（$B$ 方案 + 一片 74182 做组间）

• 求 $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×	4 片 74181 直连
C 两级先行	$8t$	4.25×	+ 1 片 74182

结论：先行进位把进位延迟从"随位数线性增长"压到"随分组层数增长"。位数越多收益越大。

例 3：用 8 选 1 MUX 搭出 8 种运算的 ALU（完整接线）

用上一篇的 74LS151（8 选 1 MUX）实现前面那张操作码表。

第一步：确定数据端。 8 条通路的表达式，正好对应 8 个数据输入：

数据端	表达式	实现
$D_0$	$A+B$	加法器
$D_1$	$A-B=A+\overline{B}+1$	加法器 + 异或取反 + $C_0=1$
$D_2$	$A\wedge B$	AND 阵
$D_3$	$A\vee B$	OR 阵
$D_4$	$A\oplus B$	XOR 阵
$D_5$	$\overline{A}$	NOT 阵
$D_6$	$A+1$	加法器（$B=0$、$C_0=1$）
$D_7$	$A$	直通

第二步：选择端。 $S_2{S}_1{S}_0=O{P}_{2}O{P}_{1}O{P}_0$，操作码直接接选择端，零额外译码。

第三步：逐项验证。 取 $A=0110(6)$，$B=0011(3)$：

操作码	运算	计算	结果（4 位）
000	$A+B$	$6+3$	1001
001	$A-B$	$6-3$	0011
010	$A\mathrm{\&}B$	0110 & 0011	0010
011	$A|B$	0110 | 0011	0111
100	$A\oplus B$	0110 ^ 0011	0101
101	$\sim A$	~0110	1001
110	$A+1$	$6+1$	0111
111	$A$	直通	0110

第四步：点出代价值。 8 条通路里，加法器最长（$34t$ 那种），其余都是 1~2 级门。MUX 虽然"零逻辑代价"，但整块 ALU 的延迟仍是加法器的延迟——这就是 ALU 设计的核心矛盾。

例 4：四个标志位的计算（承接上一篇的冒险话题）

4 位补码加法，求各种情况下的 ZF/SF/CF/OF。

完整计算过程：

运算	$A+B$	真值和	结果	$C_4$	$C_3$	CF	OF	ZF	SF
$7+1$	0111+0001	8	1000	0	1	0	1	0	1
$5+3$	0101+0011	8	1000	0	1	0	1	0	1
$3+4$	0011+0100	7	0111	0	0	0	0	0	0
$5+5$	0101+0101	10	1010	0	1	0	1	0	1
$4-4$	0100+1100	0	0000	1	1	1	0	1	0
$6-3$	0110+1101	3	0011	1	1	1	0	0	0

逐位展开 $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$（最高位向外无进位）→ $OF=C_4\oplus C_3=1$，溢出。

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

再读 $4-4$：结果 0000 → ZF = 1（全 0 的或非为 1），$SF=0$；$C_4=1$ 表示减法没有借位（被减数够减）；$OF=C_4\oplus C_3=1\oplus 1=0$，正确。

读 $6-3$：$C_4=1$（无借位）、$C_3=1$ → $OF=0$，$6-3=3$ 不溢出 ✓。

记牢这张表：减法里 $C_4=1$ 表示无借位，$C_4=0$ 才是有借位——和直觉相反，是高频失分点。

例 5：四位桶形移位器（级数与延迟）

设计一个 4 位桶形左移移位器，支持移 0~3 位。

第一步：分解移位数。 $\text{shamt}=2^1\cdot s_1+2^0\cdot s_0$（两位二进制）。

第二步：级联结构。

级 0（原始）：        b3 b2 b1 b0
                      │
级 1：s0 = 0 ? 不变 : 左移 1 位（低位补 0）   ← 2 选 1 MUX × 4
                      │
级 2：s1 = 0 ? 不变 : 左移 2 位（低位补 0）   ← 2 选 1 MUX × 4
                      │
输出：                y3 y2 y1 y0

第三步：逐位验证（$b=1001$）。

shamt	$s_1{s}_0$	级 1 后	级 2 后	左移结果	期望
0	00	1001	1001	1001	左移 0 位 ✓
1	01	0010	0010	0010	左移 1 位 ✓
2	10	1001	0100	0100	左移 2 位 ✓
3	11	0010	1000	1000	左移 3 位 ✓

第四步：级数结论。 移位数有 $\lceil {\log }_{2}4\rceil =2$ 位 → 正好 2 级 MUX。推广到 $n$ 位：级数 $={\log }_{2}n$。

位宽	串行移位器	桶形移位器
4 位	4 级	2 级
32 位	32 级	5 级
64 位	64 级	6 级

用到的 MUX 总数：每级 $n$ 个 2 选 1 MUX → $n{\log }_{2}n$ 个。64 位桶形移位器 = $64\times 6=384$ 个 MUX。用面积换延迟，是典型的硬件权衡。

例 6：用程序复算

#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);
}

/* 串行进位链 */
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 */
    }
}

/* 加法器通路：c0 为最低位进位输入 */
static int add_path(int a, int b, int n, int c0, int *carry_out) {
    int mask = (1 << n) - 1;
    int s = (a + b + c0) & mask;
    if (carry_out) *carry_out = ((a & mask) + (b & mask) + c0) >> n;
    return s;
}

/* 8 种运算的 ALU（真实硬件是 8 条通路并行算 + MUX 选；此处用 switch 等价表达） */
static int alu(int op, int a, int b, int n, int *cout_) {
    int mask = (1 << n) - 1;
    int r = 0, c4 = 0;
    switch (op) {
        case 0: r = add_path(a, b, n, 0, &c4); break;                 /* A + B   */
        case 1: r = add_path(a, (~b) & mask, n, 1, &c4); break;       /* A - B   */
        case 2: r = a & b; break;                                     /* A & B   */
        case 3: r = a | b; break;                                     /* A | B   */
        case 4: r = a ^ b; break;                                     /* A ^ B   */
        case 5: r = (~a) & mask; break;                               /* ~A      */
        case 6: r = add_path(a, 0, n, 1, &c4); break;                 /* A + 1   */
        case 7: r = a; break;                                         /* A       */
    }
    if (cout_) *cout_ = c4;
    return r;
}

int main(void) {
    int a = 0x6, b = 0x3, n = 4;
    const char *name[8] = {"A+B","A-B","A&B","A|B","A^B","~A","A+1","A"};
    printf("运算    结果   二进制\n");
    for (int op = 0; op < 8; op++) {
        int c4 = 0;
        int r = alu(op, a, b, n, &c4);
        printf("%-6s  %2d     ", name[op], r);
        for (int i = n - 1; i >= 0; i--) putchar('0' + ((r >> i) & 1));
        printf("\n");
    }

    /* 进位链一致性：串行 vs 先行展开 */
    int G = 0, P = 0;
    for (int i = 0; i < 4; i++) {
        int ai = (a >> i) & 1, bi = (b >> i) & 1;
        G |= (ai & bi) << i;
        P |= (ai ^ bi) << i;
    }
    printf("\nG=%d P=%d\n", G, P);
    int Cr[8];
    ripple(a, b, 4, Cr);
    printf("串行进位链 C1..C4 = %d%d%d%d\n", Cr[0], Cr[1], Cr[2], Cr[3]);

    /* 标志位：OF = Cn ^ Cn-1 */
    int cases[4][2] = {{7,1},{5,3},{3,4},{5,5}};
    printf("\nA+B    结果   C4 C3  OF  ZF  SF\n");
    for (int k = 0; k < 4; k++) {
        int Ca[8];
        ripple(cases[k][0], cases[k][1], 4, Ca);
        int s = (cases[k][0] + cases[k][1]) & 0xF;
        int C4 = (cases[k][0] + cases[k][1]) >> 4;
        int C3 = Ca[2];
        printf("%d+%d   %d    %d  %d   %d   %d   %d\n",
               cases[k][0], cases[k][1], s, C4, C3, C4 ^ C3,
               s == 0 ? 1 : 0, (s >> 3) & 1);
    }
    return 0;
}

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

预期输出：

运算    结果   二进制
A+B      9     1001
A-B      3     0011
A&B      2     0010
A|B      7     0111
A^B      5     0101
~A       9     1001
A+1      7     0111
A        6     0110

G=2 P=5
串行进位链 C1..C4 = 0110

A+B    结果   C4 C3  OF  ZF  SF
7+1    8    0  1   1   0   1
5+3    8    0  1   1   0   1
3+4    7    0  0   0   0   0
5+5    10   0  1   1   0   1

结果与例 1、例 3、例 4 逐项吻合。

# ---------- 例1/例2：加法器与延迟模型 ----------
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

a, b = 0b0110, 0b0011
G, P, C = cla(a, b)
print(f"例1 A={a:04b} B={b:04b}  G={G[::-1]} P={P[::-1]}  先行进位链={C}")
print(f"     串行进位链={ripple(a, b, 4)}  一致={ripple(a, b, 4) == C}")

print("\n例2 16 位加法器延迟（与/或=1t，异或=2t）")
TA = 2 * 16 + 2
TB = 2 + 2 + 4 * 2 + 2
TC = 2 + 1 + 1 + 2 + 2
print(f"  A 纯串行          = {TA}t")
print(f"  B 组内先行组间串行 = {TB}t  提速 {TA/TB:.2f}x")
print(f"  C 两级先行        = {TC}t  提速 {TA/TC:.2f}x")

# ---------- 例3：8 种运算的 ALU ----------
print("\n例3 ALU 8 种运算（A=0110, B=0011, 4 位）")
A, B, n = 6, 3, 4
mask = (1 << n) - 1
ops = [("A+B", (A + B) & mask), ("A-B", (A - B) & mask), ("A&B", A & B),
       ("A|B", A | B), ("A^B", A ^ B), ("~A", (~A) & mask),
       ("A+1", (A + 1) & mask), ("A", A)]
for i, (nm, v) in enumerate(ops):
    print(f"  OP={i:03b}  {nm:4s} -> {v:2d}  {v:04b}")

# ---------- 例4：标志位 ----------
print("\n例4 标志位（OF = C4 ^ C3）")
for x, y in [(7, 1), (5, 3), (3, 4), (5, 5)]:
    car = ripple(x, y, 4)
    s = (x + y) & 0xF
    C4, C3 = (x + y) >> 4, car[2]
    print(f"  {x}+{y}: 结果={s:2d} C4={C4} C3={C3} OF={C4 ^ C3} "
          f"ZF={1 if s == 0 else 0} SF={s >> 3}")
print("  减法 6-3 = 3（A + ~B + 1）:")
nb = (~B) & mask
car = ripple(A, nb, 4)
s = (A + nb + 1) & mask
print(f"    ~B={nb:04b} 结果={s:04b}={s} C4={(A + nb + 1) >> 4} "
      f"C3={car[2]} OF={((A + nb + 1) >> 4) ^ car[2]}")

# ---------- 例5：桶形移位器 ----------
print("\n例5 4 位桶形左移移位器（b=1001）")
def barrel_lshift(b, shamt, n=4):
    for k in range(n.bit_length() - 1):
        if (shamt >> k) & 1:
            b = (b << (1 << k)) & (1 << n) - 1
    return b
for shamt in range(4):
    print(f"  shamt={shamt} ({shamt:02b}) -> {barrel_lshift(0b1001, shamt):04b}"
          f"   (期望 {0b1001 << shamt & 0xF:04b})")
print(f"  级数 = log2(4) = {(4).bit_length() - 1} ; MUX 数 = 4*log2(4) = "
      f"{4 * ((4).bit_length() - 1)}")
print(f"  64 位: 级数 {64.bit_length() - 1} ; MUX 数 "
      f"{64 * (64.bit_length() - 1)}")

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

考点

考点

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$）
• 溢出：$OF=C_n\oplus C_{n-1}$
• 桶形移位器级数：${\log }_{2}n$；MUX 数：$n{\log }_{2}n$

2. ALU 的核心结构（判断/简答必考）

$$\boxed{{\displaystyle \text{ALU}=\text{所有运算并行算出}+\text{MUX 按操作码选一个}}}$$

• 不是"按需造电路"，而是"算全部再挑"——所以延迟等于最慢那条路（加法器）。
• 操作码直接接 MUX 的选择端，不需要额外译码。

3. 高频陷阱

陷阱	正解
"最高位有进位 = 溢出"	错。$5+5$ 在 4 位下 $C_4=0$ 却溢出。必须 $OF=C_n\oplus C_{n-1}$
减法里 "$C_4=1$ 表示借位"	反了。$C_4=1$ 是无借位（够减），$C_4=0$ 才是有借位
"CF 和 OF 都是溢出标志"	CF 管无符号（往外的进位），OF 管有符号（符号位被推翻）
"74181 的 S 管算术还是逻辑"	$M$ 管算术/逻辑，$S$ 管具体哪一种，$C_n$ 管加不加 1
"串行进位延迟是 $O(\log n)$"	是 $O(n)$，线性。这正是要先行进位的原因
"先行进位能无限展开"	不能，项数按 $2^i$ 增长，受扇入限制必须分组
"ALU 一次只能算一种运算"	内部全部并行算，只是输出被 MUX 选中一条
"减法器是另一个电路"	共用加法器，只改 B 端取反和 $C_0$
减法忘了 "+1"	只对 $B$ 取反而忘了 $C_0=1$，结果差 1，最典型失分点

4. 延迟计算模板（"算 $n$ 位加法器延迟"）

① 先确认题目假设：与/或门几 t，异或门几 t（不给定就说明你的假设）
② 串行：进位链 = 2nt，再加末级求和 2t
③ 组内先行、组间串行：算 G/P + 组内两级 + 组间穿过 m 组 × 2t + 末级
④ 两级先行：算 G/P + 组进位 G*/P* + 第二级进位 + 组内展开 + 末级
⑤ 提速比 = 串行延迟 ÷ 新方案延迟，报告时写清"假设"

5. 与后续章节的接口

• 加法器是 L2 组成原理数据通路的核心：PC 加 1、访存地址计算都靠它。
• 标志位 ZF/SF/CF/OF 直接对应 L2 指令系统里的条件转移指令（JZ/JS/JC/JO）。
• 加法器延迟直接决定 L2 流水线中 ALU 类指令的时钟周期下界（见 circuit/16-timing.md）。
• 移位器是 L3 lang 中 shl/shr 类指令的硬件本体。
• 本站 arch/04-alu.md 会从组成原理视角把这一篇的结论提升到数据通路层面，两处的公式与延迟口径完全一致，可互为对照。

小结

• 半加器 → 全加器 → 多位加法器，是"用门搭功能块"的第一课；全加器的两条式子 $S=A\oplus B\oplus C$、$C_{out}=AB+(A\oplus B)C$ 必须能秒推。
• 加法器的瓶颈全在进位链：串行 $2nt$ 线性增长；先行进位把进位写成只依赖 $C_0$ 的布尔式，用两级门并行算出，代价是项数指数增长 → 必须分组 + 多级。
• 减法不进新电路：$A+\overline{B}+1$，一个 SUB 信号同时完成取反和加一。
• ALU = 并行算 + MUX 选，所以它的速度由**最慢通路（加法器）**决定；标志位是副产品，其中 $OF=C_n\oplus C_{n-1}$、CF 管无符号 / OF 管有符号是最高频考点。
• 74181 + 74182 是"组内先行 + 组间先行"的器件版；桶形移位器用 ${\log }_{2}n$ 级 MUX 换掉了 $n$ 级串行延迟——用面积换速度是硬件设计的永恒主题。

回到主线：到这里，L1 的组合逻辑部分就完整了——我们能用门、译码器、MUX、加法器拼出一个会算 32 位加减与逻辑运算的 ALU。

但 ALU 有个致命缺陷：它记不住任何东西。算完就忘。而 CPU 需要保存 PC（下一条指令地址）、需要保存运算的中间结果、还需要"数到 10 就停"这样的计数能力。"记住一位"这件事，电路要怎么实现？ 这就是下一篇的主题。

下一篇：锁存器与触发器：如何"记住"一位