第 3 章 · 运算器与 ALU

先看一段让我愣了很久的汇编。有一道题要求「不使用乘除运算符计算一个数除以 10」,我写了一堆移位加减,交完卷随手让 gcc 编译 x / 10,得到的汇编里赫然是一条乘法:

; x / 10, x 是 32 位 int, gcc -O2 的输出(节选)
mov eax, edi
imul eax, eax, 1374389535    ; 乘一个奇怪的常数
shr eax, 37                  ; 右移 37 位

除法被编译成了「乘一个大常数再移位」。这个魔法本章末尾解密,它牵出的正题是:CPU 的运算器到底怎么造出来,为什么加法一个周期、乘法三四个周期、除法要几十个周期。答案层层往上长:一切从一个加一位的电路开始。

3.1 全加器:一位的加法

一位全加器吃三个输入:本位两个加数 a、b,加上低位来的进位 cin;吐两个输出:本位和 s,向上走的进位 cout。真值表画出来一眼能看出规律,s 是「三个输入里 1 的个数为奇数」,cout 是「1 的个数至少为 2」:

s    = a ⊕ b ⊕ cin
cout = ab ∨ cin(a ⊕ b)

半加器是它的残血版(没有 cin,只处理最低位)。把 n 个全加器串成糖葫芦,每级的 cout 接下一级的 cin,就是 n 位加法器。注意这里没提任何「补码」:加法器只管把两个位串加起来,补码(第 2 章)保证「按无符号规则相加,扔掉最高进位」,结果恰好就是有符号数的正确答案。硬件一层都不用改,减法是靠喂进 B 取反加一 白嫖出来的。

3.2 进位才是瓶颈

糖葫芦加法器学名「行波进位」(ripple-carry),它的问题是进位像波一样从最低位滚到最高位:算 1111 1111 + 0000 0001,最高位的和要等 7 级门传播才能定下来。加法延迟 O(n),而它通常是整个 ALU 的关键路径,主频(第 1 章提过)直接被这条路径掐住。

解法是超前进位(carry-lookahead)。把每位拆出两个信号:g(generate,两位都是 1,进位自己就能生出来)和 p(propagate,恰有一位是 1,低位来的进位能借道穿过去)。于是每位进位可以写成:

c₁ = g₀ ∨ (p₀ ∧ c₀)
c₂ = g₁ ∨ (p₁ ∧ g₀) ∨ (p₁ ∧ p₀ ∧ c₀)
c₃ = g₂ ∨ (p₂ ∧ g₁) ∨ (p₂ ∧ p₁ ∧ g₀) ∨ (p₂ ∧ p₁ ∧ p₀ ∧ c₀)

每个 c 都只依赖输入和 c₀,展开到位就能一层门同时算出,延迟从 O(n) 降到 O(log n)(分组树形展开)。代价是电路规模和门扇入暴涨,所以工程折中是分组:64 位加法器内部分成若干 8 位或 16 位的组,组内超前进位、组间再来一级。你买的 CPU 能跑几 GHz,这套电路的延迟是硬约束之一。

3.3 ALU:把加法器武装成多面手

ALU(算术逻辑单元)就是给加法器包一圈选择电路:两个操作数 A、B 进来,一根操作码决定这次干啥,结果和一组标志位出去。

      ┌─────────────┐
A ───▶│             │───▶ 结果 F
B ───▶│  加法器     │
      │  + 移位器   │───▶ ZF SF CF OF
op ──▶│  + 逻辑门   │
      └─────────────┘

支持的操作里最有意思的是减法:A + B 取反 + 1。B 取反由异或门阵列完成(控制线为 1 时把 B 每位翻转),那个「+1」就借最低位的进位输入 cin 塞进去,一分硬件不多花。比较操作(a < b)更省:做一次减法,结果不写回,只看标志位。

标志位是 ALU 的暗状态,条件跳转全靠它们:

标志	含义	服务的数制
ZF	结果为零	都算
SF	结果为负(最高位)	有符号
CF	无符号进位/借位	无符号
OF	有符号溢出	有符号

同一次减法,四个标志同时被置上,读哪个由指令决定:ja(unsigned 大于)读 CF 和 ZF,jg(signed 大于)读 ZF、SF 和 OF。这就是 C 里 int 和 unsigned 比较编译出不同指令的根源(第 2 章说过的「两个世界」,在这里落到了具体指令上)。

3.4 移位:被低估的运算

移位器是 ALU 里另一块主力。三种右移的区别必须刻进脑子:

逻辑右移:高位补 0。unsigned 的除 2。
算术右移:高位补符号位。signed 的除 2(向下取整,注意 -5 >> 1 = -3,是 -2.5 向下取整)。
循环移位:移出的位绕回另一头,密码学里常见。

左移只有一种,补 0。x << 1 等于乘 2,所以编译器看到 x * 10 会改成 (x << 3) + (x << 1);乘 2 的幂次直接变移位。反过来,-5 / 2 编译器也不会给你真除法,会算成 (x + 1) >> 1 之类的移位加减组合。

有个容易踩的 UB:移位位数超过或等于操作数位宽(比如把 32 位 int 移 32 位)是未定义行为,在 x86 上实际只移 count mod 32,不同平台答案不同,这种代码写出来就是定时炸弹。

3.5 乘除法:贵,以及有多贵

乘法的手算过程(逐位乘、错位加)直接翻译成硬件就是「移位加累加」,n 位乘法要 n 轮。有符号数用 Booth 算法统一处理,它有个顺手的红利:碰到连续 1 的串(比如 0111 = 1000 - 1)可以加减法各一次跳过整串。现代 CPU 走得更远,用华莱士树把所有部分积并行压缩,加法器深度 O(log n),所以乘法只要 3~4 个周期。

除法没这么好命:「试减、够减商 1、不够商 0」每一步都依赖上一步,天生的串行结构,主流实现是每周期出 1 到 4 位商。结果就是这组真实的量级:

运算	延迟(典型)
加/减/移位/逻辑	1 周期
乘法	3~4 周期
除法	20~90 周期(和操作数数值有关,`div` 是出了名的慢)

除以 10 慢 20 倍以上,编译器当然要动手脚。现在可以解开头那个悬案了:1374389535 = ⌈2³⁵ / 10⌉,所以 x / 10 ≈ (x × 1374389535) >> 35。乘法用移位修正舍入误差后,对全体 32 位整数都严格正确(数学证明不短,有兴趣搜「magic number division」)。你写下的每个 x % 10、每个 % 10 == 0 的判断,编译器都在替你做这笔买卖。这也是为什么第 10 章读汇编时,你会看到大量「对不上源码」的指令:它们都是这类优化的产物。

常见错误

拿 >> 1 代替 / 2 用在有符号负数上。-5 / 2 = -2(向零取整),-5 >> 1 = -3(向下取整),两者不相等,这是真实的语义差异,编译器替换时会补偿,你手写时不会。
以为乘法加法同价。在内层循环里做除法取模,是性能剖析里最常见的热点之一,把它们挪出循环或换成条件判断,常常立竿见影。
移位 32 位。上面说过,UB。需要移满 32 位的行为,老老实实写乘除或判断。

练习

手算:用 4 位全加器的思路,画 1001 + 0111 每一位的 s 和 cout,验证结果 1 0000,并指出哪些位在「等」进位。
手算:按 Booth 的思路,说明 0111(7) 乘任何数时为什么可以只用一次减法和一次加法。
动手:写一个 C 程序分别测「循环内整数加法」和「循环内整数取模」各跑一亿次的时间,算算差多少倍,和 3.5 节的延迟表对照。
思考:gcc 把 x / 10 编译成乘法,那 x / 3、x / 7 呢?用 gcc -O2 -S 试试,常数变了,结构没变。想想为什么对「除以变量」这招失效。