# 除法从不真正发生：拆解编译器的"魔数乘法"内核 ## 导语：你写的 `/7`，CPU 根本没"除" 写 C/C++/Rust 的人大概都有个错觉：源代码里写一个 `/`，机器最后就老老实实执行一条除法指令。**错。** 如果除号右边是一个编译期就能确定的常数——比如 `/7`、`/10`、`/255`——主流编译器（GCC、Clang/LLVM、MSVC）几乎永远不会生成真正的 `div`/`idiv` 指令。它会偷偷把你的除法，改写成**一次整数乘法 + 一次移位 + 最多一次加减修正**，用一串看起来像乱码的"魔数"（magic number）来糊弄出正确答案。 这就是 Computerphile 在 2026 年 5 月 26 日发布的那期《The "Trick" that Compilers Use for Long Division》讲的事。这期视频值得每一个想从"会写代码"跨到"懂代码在机器上怎么跑"的开发者认真看一遍：它把一个藏了三十年的编译优化，用"竖式长除法"这个每个人小学都学过的隐喻，讲得清清楚楚。它的核心洞察一句话就能说穿——**整数除法太贵，贵到 CPU "懒得"做，于是编译器用乘法把除法骗过去。** 而这个"骗"之所以安全，背后是一篇 1994 年的、漂亮得像数学竞赛题的论文。 ## 视频背景卡片 | 项目 | 内容 | |------|------| | 视频标题 | The "Trick" that Compilers Use for Long Division | | 频道 | Computerphile（诺丁汉大学出品，计算机科学科普头部频道） | | 发布日期 | 2026-05-26（截至本文写作 2026-06-29，发布约一个月） | | 时长 | 约 10–15 分钟（Computerphile 经典科普短讲形式） | | 频道订阅 | 约 260 万 | | 核心主题 | 编译器如何用"乘以魔数 + 移位"替代常数整数除法 | ## 核心内容拆解 ### 要点一：先戳破那个反直觉的事实 视频开场就抛出了一个会让很多人愣住的演示：你写下 `int y = x / 7;`，你以为汇编里会有一条除法。实际上 GCC `-O2` 给你的是大致这样的形态（结构而非逐字）——**一条 `imul`（整数乘）、一两条 `sar`/`shr`（算术/逻辑右移）、可能再加一条 `sub` 做符号修正**。从头到尾，`div` 这条指令根本不出现。 这是你日常代码里每天都在发生、却几乎没人留意的事。只要除数是常数，编译器就会动手脚；除数是变量（运行时才知道是几），它才老老实实留一条 `div`。**这个区分是整件事的地基：常数除法从不真正发生，变量除法才真的除。** 视频的价值就在于，它没有停留在"编译器很聪明"这种空话，而是追问：凭什么一个乘法能等价于一个除法？ ### 要点二：为什么除法贵得离谱——它本质是一个循环 要理解编译器为什么费这么大劲换掉除法，得先知道硬件除法有多慢。CPU 里做乘法，有专门的、深度流水线化的阵列乘法器，x86 上 32 位 `imul` 的延迟通常只有 **3 个时钟周期**，且每个周期能发射一条。而整数除法 `idiv` 完全是另一副面孔：32 位除法在 Skylake 这类架构上延迟约 **20–26 个周期**，64 位能到 **30 个周期以上甚至近百周期**，而且吞吐极差（很多核心每个周期最多吞吐 1/6 条 `div`），几乎不被流水线吃掉。 为什么这么贵？因为硬件除法器的算法骨子里就是**小学竖式除法的位级版本**——它要一位一位地"试商"，本质上是一个串行的、依赖上一步结果的循环。而乘法是并行的（Wallace 树把这些加法压成树状并行算完）。**一个天生并行、一个天生串行，这就是数量级的鸿沟。** 在 1990 年代初这篇论文诞生的年代，差距更夸张：486 上整数除法 40 多个周期，而当时的 ARM7 核**根本没有硬件除法指令**，一次除法要靠软件例程跑 70 多个周期。换句话说，当年把除法换成乘法，省下来的不是 10 倍，而是几十倍。 ### 要点三：思想根源——右移是"免费的除法"，那非 2 的幂怎么办？ 优化的起点是一个人人都知道的捷径：除以 2 的幂，就是**算术右移**。`x / 8` 直接变成 `x >> 3`，一条移位指令，1 个周期。这等于 CPU "白送"了一个除法。问题来了：除以 8 能白嫖，那除以 7、10、255 呢？这些不是 2 的幂的常数，能不能也"伪装"成乘法和移位？ 视频的精彩之处，是把这件事接到"倒数"这个小学概念上。除以 7，等价于乘以 1/7。但小数 1/7 = 0.142857… 是无限循环小数，计算机里只有整数，怎么办？答案是：**把 1/7 放大一个巨大的倍数，放大成"一个非常大的 2 的幂"份之七的分子**，让它落在一个整数里。具体说，找一个整数 `m`，让它约等于 `2^k / 7`。这样 `x * m ≈ x * 2^k / 7`，再把结果右移 `k` 位（除以 2^k），就近似得到了 `x / 7`。 **魔数，本质上就是一个被放大到 2 的幂量级的"整数化倒数"。** 理解了这一点，那些看起来像天书的十六进制常数就不再神秘。 ### 要点四：魔数的真相——0x92492493 就是 ⌈2³⁴ / 7⌉ 视频里最让人"哦——"的一刻，是把这个魔法常数还原成一道算术题。我在这里把它彻底验算给你看，这是本文我自己补的延伸分析，视频只点到为止： 以 32 位有符号除以 7 为例，编译器用到的那个著名魔数是 `0x92492493`。把它翻译成十进制是 **2,454,267,027**。而 `2^34 = 17,179,869,184`。17,179,869,184 ÷ 7 = 2,454,267,026.28…，向上取整正好等于 **2,454,267,027**。换句话说： ``` 0x92492493 == ⌈ 2^34 / 7 ⌉ == 2454267027 ``` **这个看似随机的十六进制常数，就是"2 的 34 次方除以 7、再向上取整"的结果。** 它不是魔法，是一道小学除法——只不过分子被放大了 2^34 倍，大到能用整数精确表示一个"近似倒数"。除以 10 同理：`0x66666667` = 1,717,986,919 = ⌈2^34 / 10⌉（我也验算了：2^34/10 = 1,717,986,918.4，上取整 = 1,717,986,919，正中）。**每一个魔数，背后都藏着一句"我其实是放大了好多倍的 1/d"。** ### 要点五：为什么是"上取整"⌈⌉而不是四舍五入——这是整个 trick 的安全阀 很多人到这一步会卡住：既然是近似，那 `x*m >> k` 和真正的 `x/7` 总会有误差吧？误差会不会在某些 `x` 上算出错的整数？这是整个技术最精妙、也最容易被科普视频略过的内核。 关键就在那个**向上取整**。我们用 `m = ⌈2^k / d⌉`，故意把魔数选得比精确倒数"略大一点点"。为什么偏大才安全？因为我们最后是**向下取整**（截断）的。如果魔数偏小，乘出来的积就会系统性偏小，最后截断时可能在边界处**少算一个整数**——对一个确定的输入 `x`，算出 `x/7 = 1` 而真值是 2，那就完全错了。而魔数略大，积系统性偏大一点点，但只要偏大得足够"克制"，最后的截断还是能落在正确的整数上。 1994 年那篇论文（Granlund & Montgomery）做的真正硬核的事，就是**证明：对给定字长和除数，总存在一个足够大的 `k` 和对应的 `m = ⌈2^k/d⌉`，使得这个近似对定义域内每一个整数输入都精确成立**。它给出了选择 `k` 的界，保证最大误差始终小于 1，从而截断后永不越界。**这一条精度定理，才是"乘法骗过除法"之所以合法的通行证。** 上取整不是随便选的，它是被证明出来的、保证全输入正确性的安全阀。 ### 要点六：实测验证——把 `/7` 喂进 Compiler Explorer，div 会消失 视频最有说服力的地方在于它把这件事变成了你可以亲手复现的实验。我强烈建议你照做：打开 [Compiler Explorer (godbolt.org)](https://godbolt.org)，左边写一行 `int div7(int x){ return x/7; }`，选 GCC 或 Clang、开 `-O2`，右边出来的汇编里，你会看到乘以那个 `0x92492493`（或编译器选的等价常数）的 `imul`、一两条 `sar`/`shr` 移位，以及一条针对负数的符号修正（因为 C 语言整数除法是"向零截断"，而算术右移是"向负无穷舍入"，两者对负数差一个 1，所以要补一次减法）。 然后把源码改成 `int divn(int x, int d){ return x/d; }`——除数变成变量——你会立刻看到一条货真价实的 `idiv` 指令冒出来。**同一个 `/`，常数变乘法、变量变除法，泾渭分明。** 这就是为什么这个优化叫 "division by invariant integers"（除以不变整数）：编译器必须在编译期"看见"那个常数，才有资格动手脚。这也是为什么函数里除以一个循环不变的量时，把除数提出来、用编译期常量替换运行期变量，有时能拿到肉眼可见的提速。 ### 要点七：2026 年，这个 trick 反而更值钱了 这个"古董级"优化，在今天不仅没过时，反而更重要。原因有三，这是我在视频基础上的延伸： **第一，向量/SIMD 场景里根本没有整数除法。** ARM 的 NEON、x86 的 AVX/AVX2、AArch64 的 SVE——这些让 CPU 一次算 4/8/16 个数据的 SIMD 指令集，**统统没有整数除法指令**（浮点除法都很少）。所以任何一个想用 SIMD 加速的整数循环，只要里面有 `/const`，唯一的出路就是魔数乘法。图形学里满地都是的 `/255`（把 0–255 的字节归一化）、哈希函数里的 `/ 31`、颜色空间转换里的常数除，全靠这套机制才跑得动。 **第二，64 位下除法更慢，魔数省得更多。** 64 位 `idiv` 延迟比 32 位又高一截，而 `imul` 64 位仍只要 3 周期，差距进一步拉大。 **第三，求余 `%` 也被同样改写。** 你以为 `% 7` 是除法的副产物？编译器一样会用魔数把 `x % 7` 算成 `x - (x/7)*7`，全程没有 `div`。CRC、哈希、环形缓冲取模这些高频操作，背后都是这个机制在托底。 **一句话：凡是有"除以常数"的整数热路径，魔数乘法都是它跑得快的前提。** ## 知识结构图 ```mermaid flowchart TD A["源码: x / d"] --> B{d 是编译期常数?} B -- 否（变量） --> C["生成真正的 div / idiv 指令\n20–95 周期，串行试商"] B -- 是（常数） --> D["编译器启动 '除以不变整数' 优化"] D --> E["算魔数 m = ⌈ 2^k / d ⌉\n放大版整数倒数"] E --> F["Granlund-Montgomery 定理\n证明: 存在 k 使全输入精确"] F --> G["生成: imul(乘m) → 取高位 → 移位 k"] G --> H{有符号 / 负数?} H -- 是 --> I["加一次符号修正 sub\n(向零截断 vs 向-∞舍入)"] H -- 否 --> J["直接截断"] I --> K["结果 = x / d\n全程 0 条 div 指令"] J --> K K --> L["典型 3–4 周期\n比硬件除法快约 10×"] ``` ## 实战启示：这套认知怎么变成你的生产力 **1. 永远优先用常数除，而不是变量除。** 写热路径（循环、哈希、编解码）时，如果能用编译期常量代替运行期变量做除数，就坚决用常量。`x / TABLE_SIZE`（`TABLE_SIZE` 是 `constexpr`/宏）会编译成乘法；`x / runtime_var` 会留下 `div`。一个习惯的差别，就是 10 倍。 **2. SIMD 化之前，先确认你的 `/` 能被魔数吃掉。** 想把一段整数代码用 NEON/AVX 向量化加速，先问自己：里面有没有除以非常数？如果有，要么提取成常量，要么手动改成"乘法+移位"，否则 SIMD 没法生成。**会算这个，是你 SIMD 调优的入门门槛。** **3. 看汇编、用 godbolt，是判断"优化到底生效没"的唯一靠谱手段。** 很多人写完"优化"自我感觉良好，其实编译器早把它干掉了或根本没动。养成习惯：关键函数丢进 [Compiler Explorer](https://godbolt.org)，看有没有意外的 `div`、有没有意外的内存访问。这次的主题就是最好的例子——你以为的 `/7` 早就不存在了。 **4. 求余 `%` 同理，别因为它"看起来便宜"就滥用。** 环形缓冲用 `i % size` 当 `size` 是 2 的幂时，编译器进一步降成位与 `i & (size-1)`，比魔数乘法还快——所以把环形缓冲/哈希表的容量强制设为 2 的幂，是一个零成本、跨语言通用的、立竿见影的提速手段（从一次乘法+移位，降到一条位与）。**这恐怕是本文最值钱的一句实战建议。** **5. 建立"成本直觉"：乘≈移位≈位与 ≪ 加载 ≪ 除法 ≪ 函数调用。** 高性能编程的本质是成本工程。知道一条 `idiv` 顶几十条 `imul`，你写代码时的每一个选择都会不一样。 ## 延伸学习路径 1. **Compiler Explorer（godbolt.org）** — 亲手验证本文一切的最好工具。把 `/7`、`/10`、`/255` 依次喂进去，对照看魔数的变化，比读十遍书都管用。 2. **《Hacker's Delight》Henry S. Warren 著，第 2 版，第 10 章 "Integer Division by Constants"** — 这个主题的圣经级参考书。想看懂"为什么上取整、`k` 怎么选、有符号怎么修正"的严格推导，直接读这章。 3. **Granlund & Montgomery (1994), "Division by Invariant Integers Using Multiplication", PLDI** — 这一切的源头论文。数学不复杂，但优雅，是少有的"读完会觉得电脑变聪明了"的论文。 4. **Agner Fog 的《Optimizing software in C++》手册 + 指令延迟表** — 查 `idiv`/`imul` 在各代 x86/ARM 上精确到周期的延迟，建立你的成本直觉。 5. **LLVM 的 `APInt::magic`/`magicu` 源码** — 想看现代编译器"在线"计算魔数的真实算法，去翻 LLVM 的实现，几行代码就把这篇论文落了地。 ## 一句话总结 **整数除法慢得 CPU 不愿意做，于是编译器用"放大版整数倒数"这个魔数乘法把它彻底替换掉——而你代码里那个 `/7`，其实从来没真正发生过。** ## 参考来源 1. [The "Trick" that Compilers Use for Long Division — Computerphile](https://www.youtube.com/watch?v=-14t6_yu-7w) — 本文分析的核心视频（2026-05-26 发布） 2. [Division by Invariant Integers using Multiplication — Granlund & Montgomery, PLDI 1994](https://dl.acm.org/doi/10.1145/178243.178249) — 魔数除法的奠基论文，全部精度定理的出处 3. [Hacker's Delight (2nd Edition), Henry S. Warren, Ch.10 "Integer Division by Constants"](https://www.hackersdelight.org/) — 该主题最权威的教科书级参考 4. [Compiler Explorer (godbolt.org)](https://godbolt.org/) — 亲手验证"常数除法被改写成乘法"的在线工具 5. [Agner Fog's Software Optimization Resources](https://www.agner.org/optimize/) — x86/ARM 指令延迟与吞吐的权威数据来源 --- > 本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵**爱卫生**（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 > 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。 > [!tip] 51学通信知识星球 > **星主：爱卫生**（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 > **星球定位**：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 > **当前规模**：5200 篇主题 / 990 个回答，198 元/年。 > **加入福利**：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 > **AI 加持**：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。