编译器优化：除法的代价

在基本的算术运算中 —— 加、减、乘、除 —— 整数除法的代价独树一帜。在现代 x86 硬件上，一次整数除法根据操作数宽度和具体微架构，可能需要 18 到近 100 个时钟周期。加法只要 1 个周期，乘法大约 3 个周期。这个差距不小。

理解除法为什么慢、编译器如何绕开它，有助于建立对编写高效数值代码的更好直觉。

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

为什么除法昂贵

现代 CPU 是深度流水化的，会同时执行多条指令。大多数操作 —— 加载、加法、乘法 —— 都已被深度优化，每周期可以多次发射，使用多个并行执行单元。

除法的不同来自两个结构性原因：

算法复杂度。 除法不像乘法那样容易流水化。整数除法的硬件实现本质上是顺序的：每一步都依赖上一步的结果。除数和被除数必须同时完整可用，真正有意义的工作才能开始；商的每一位都是一位一位算出来的。

单一执行单元。 处理器通常每核心只有一个整数除法单元，而加法器和乘法器则有多个。这意味着当 CPU 正在做一次除法时，后续的任何除法都必须排队等待。多个独立的除法不能并行执行。

在 Intel Alder Lake 上，32 位无符号除法在最佳情况下大约需要 18 个周期。64 位除法的区间还要更长。在这些周期中，CPU 会尽量去做能做的其他工作，但除法本身是瓶颈。

除以 2 的幂：几乎免费，但要小心

开发者对除法最常见的优化是：把”除以 2 的幂”替换成右移。除以 512（即 2^9）等价于右移 9 位：

x / 512  →  x >> 9

这对无符号整数是正确的。无符号值的右移是逻辑右移，相当于按”向负无穷取整”的规则做除法 —— 而对非负值而言，它与”向零截断”是一回事。

但对有符号整数，行为就发生了分歧。

取整陷阱

C 和 C++ 标准规定整数除法向零截断。对正的被除数，向零截断和向负无穷取整是一样的。但对负的被除数就不同了：

-1 / 512   ==  0      // C：向零截断
-1 >> 9    == -1      // 算术右移：向下取整

如果你写 x >> 9 想表达 x / 512，那么一旦 x 是负数，你就会得到错误的答案。-1 右移 9 位仍然是 -1，但按 C 的截断语义，-1 / 512 应当是 0。

编译器是如何处理有符号除法的

当编译器看到 x / 512、其中 x 是有符号整数时，它会生成能产生正确 C 结果的代码：

test edi, edi          ; x 是否为负？
lea eax, [rdi + 511]   ; 计算 x + 511（即 x + 除数 - 1）
cmovns eax, edi        ; 若 x >= 0，直接用 x；若为负，用 x + 511
sar eax, 9             ; 算术右移 9 位

lea 把 x + 511 作为一个偏置值计算出来。如果 x 为负，在右移前加上 511 可以保证最终的移位结果是向零取整而不是向负无穷取整。cmovns 根据 x 的符号选择”偏置后”还是”未偏置”的值。最后的算术右移得到正确的结果。

整个序列是三条指令加一条条件移动，总共几个周期就能完成。相比 div 指令，这要快得多，但比单条 sar 要多一点开销。

想要单条移位？用无符号

如果你知道一个值是非负的，通过使用无符号类型来告诉编译器：

unsigned divide_by_512(unsigned x) {
    return x / 512;  // 编译为：shr eax, 9
}

有了无符号类型，编译器就知道没有负数要处理。它发出单条移位指令。那些修正逻辑也就消失了，因为不再需要。

这不仅仅是微优化。使用 unsigned 还向代码的读者传达了一个语义约束：这个值代表的数量不可能为负。类型系统承载着有意义的信息。

更广的模式

这种情况是可以推广的。每当你用有符号整数表示一个你知道总是非负的值时，你就是在让编译器为永远不会真正用到的正确性逻辑生成代码。编译器别无选择 —— 除非你通过类型或契约注解明确告知，它就不能假设这个值是非负的。

告诉编译器的几种方式：

对本质非负的数量使用 unsigned 或 size_t。
使用 __builtin_assume(x >= 0)（GCC/Clang）在不改变类型的前提下断言非负。编译器随后可以省略修正逻辑。
在模板中使用 std::make_unsigned_t<T>，当符号性依赖于模板参数时。

不要手动用移位替换除法

从这一切得出的结论不是”总是写移位而不是除法”，而是相反：表达除法意图时就写除法，让编译器根据它对类型的了解去生成最高效的实现。

当你手写 x >> 9 来表达 x / 512：

对有符号的负值是错的。
读者更难理解（9 是什么？为什么是移位？）。
阻碍编译器应用那些依赖”理解算术含义”的进一步变换。

写 x / 512。在合适的地方用无符号类型。相信编译器：它能发移位时就会发移位 —— 发不了时就会补上修正逻辑。