编译器优化：用乘法取代除法

整数除法是昂贵的。在 x86-64 上，div 指令根据微架构不同，大约要 18 到近 100 个周期，而加法只要 1 个周期、乘法只要约 3 个周期。更糟的是，每个 CPU 核心通常只有一个除法单元，多个除法无法并行推进。

编译器知道这件事，为此它会下大功夫从生成的代码中消除除法。当除数是一个编译期常量时 —— 即便它不是 2 的幂 —— 现代编译器会把除法替换为乘法加移位序列，耗时只占原来的一小部分。

本文是 Matt Godbolt 的《Advent of Compiler Optimisations 2025》系列中的一篇。

引入场景：整数转 ASCII

把一个整数转换为十进制字符串表示需要反复除以 10：

do {
    digit = number % 10;
    *buf++ = '0' + digit;
    number /= 10;
} while (number);

10 不是 2 的幂，所以简单的移位技巧用不上。可编译器并不会发出一条 div 指令，它用的是一种完全不同的方法。

对于 unsigned int x / 10，GCC 和 Clang 在 x86-64 上生成大致这样的代码：

mov   esi, 3435973837       ; 加载魔数 0xcccccccd
imul  rdx, rsi              ; rdx = x * 0xcccccccd（64 位乘积）
shr   rdx, 35               ; rdx >>= 35

对于所有可能的 32 位无符号输入，rdx 中的结果都精确等于 x / 10。没有近似误差。

常数 0xcccccccd 是 1/10 的定点表示。更准确地说：

0xcccccccd / 2^35 ≈ 0.100000000005821 ≈ 1/10

把 x 乘以这个值再右移 35 位，在数学上等价于 x * (1/10) —— 也就是除以 10。编译器会构造出合适的常数和移位量，使得近似误差在有效范围内的任何输入下都不会影响结果。

这一技巧被称为”魔数除法”（magic number division），由 Henry S. Warren 在《Hacker’s Delight》中系统阐述。编译器并不使用魔数查找表 —— 它在编译期根据每个除数通过代数方法算出对应的常数。

一旦商 q = x / 10 已知，余数无需再做一次除法就能得到：

r = x - q * 10

编译器用 lea 指令高效计算 q * 10，因为 lea 可以在单个周期内计算 a + b * k（k 为小常数）：

lea   r8d, [rdx + rdx*4]   ; r8 = q + q*4 = q*5
add   r8d, r8d             ; r8 = q*10
sub   ecx, r8d             ; r = x - q*10

两条 lea/add 指令取代了本来需要的一次乘法或除法。

同样的技术适用于任何编译期常量的除数，不只是 10。

小的奇常数，如 3 或 7，会使用类似的魔数，但可能需要额外的加法或减法步骤来修正某些输入区间的取整行为。

有符号除法 更复杂。C 标准要求整数除法向零截断，即 -7 / 2 = -3，而不是 -4。对负的被除数，这和右移的取整方向相反。编译器必须插入修正逻辑 —— 通常是一条基于 cmov 的条件加法 —— 来维持正确的语义。

非常大或不规则的除数 可能导致编译器判断魔数序列过于复杂、不值得，此时它会退回到真正的 div 指令。实际中这很少发生。

所有这些序列 —— 甚至包含修正步骤的那些 —— 都只需要几个周期。对同样的操作数，硬件 div 指令要 18 个或更多周期。对于频繁做除法的代码（比如整数转字符串的循环），这是一个可量化的提升。

金融行业提供了一个具体的历史案例。FIX 协议用于电子交易中的订单传输，它把价格和数量表示为 ASCII 十进制字符串。高频交易系统需要尽快格式化和解析这些字符串，而编译器把 / 10 转换为乘法加移位的能力，在这类场景的吞吐量上起着直接作用。

写 x / 10。不要写 (x * 0xcccccccdULL) >> 35。后者更难读、更难验证正确性，而且会让编译器丧失选择”在目标架构上最优实现”的自由度。

编译器知道你的除数对应的正确魔数，它已经验证了近似在有效输入范围内是精确的，并且会为有符号类型生成合适的修正逻辑。你的工作是写清晰的代码，算术交给编译器。