# 编译器如何用乘法算除法：魔法数之谜 ## 导语：CPU 最讨厌的运算 你大概早就忘了小学怎么列竖式做长除法——那种一位一位往下试商、写得满纸是数字的折磨。Computerphile（计算机科学领域最负盛名的科普频道之一）在 2026 年 5 月底放出的这支视频，开头就甩出一个反直觉的结论：**计算机和你一样讨厌除法**，而且比你更甚。 我们直觉上以为"加减乘除"是四种地位平等的运算，CPU 应该一视同仁。但事实是：在几乎所有现代处理器上，整数除法（`idiv`）的耗时是加法的 20 到 40 倍，是乘法的 10 倍以上。而编译器，这个看似老实巴交地把你的代码翻译成机器码的家伙，几十年来一直在偷偷干一件事——**它几乎从不真的执行你写下的除法，而是用一次乘法把除法"骗"过去**。这就是视频标题里那个带引号的"Trick"：魔法数除法（magic number division）。本文就带你拆穿这个长达三十年的"善意谎言"，看懂它背后的数学有多优雅，以及它为什么和你算小费时的脑回路惊人地一致。 ## 视频背景卡片 | 项目 | 内容 | |------|------| | 视频标题 | The "Trick" that Compilers Use for Long Division | | 频道 | Computerphile（英国诺丁汉大学 Brady Haran 出品） | | 时长 | 约 14 分 37 秒 | | 发布日期 | 2026 年 5 月 26 日 | | 频道订阅 | 约 260 万+ | | 核心主题 | 编译器如何用"乘以魔法数+移位"替代常数除法（Granlund–Montgomery 优化） | ## 核心内容拆解 ### 一、除法凭什么这么慢？运算界的"慢车道" 视频前 1 分钟就立住了核心矛盾。在 CPU 内部，不同指令的延迟差距巨大，存在一条清晰的"鄙视链"：**加法/减法**只要 1 个时钟周期，**乘法**约 3–4 个周期，而**整数除法**在 64 位上动辄 20–40 个周期甚至更多。 为什么会这样？因为加减乘都可以设计成高度并行的组合逻辑——乘法器本质上是一堆加法器的树形堆叠（Wallace tree），可以一个周期内并行算完。**而除法本质上是迭代的**：它必须一位一位地试商、比较、修正，后一步依赖前一步的结果，没法很好地塞进流水线。这就好比加法是所有人同时上菜，除法却只能一个人挨个排队。 视频还点出一个常被忽略的历史细节：早期的 ARM 处理器（在 Cortex-A15 之前）**根本没有硬件整数除法指令**。你在 C 里写一句 `a / b`，编译器会老实地生成一条对运行时库函数 `__aeabi_idiv` 的调用，用软件循环模拟除法。这种情况下，把除法变成乘法的"魔法数把戏"价值直接被放大十倍——它不光省周期，还省掉一次函数调用。（此为基于视频论点的延伸补充） ### 二、其实你早就在用"魔法数"：小费与速算 视频在 2 分钟左右抛出一个特别巧妙的钩子：**人类算除法时，用的也是同一招**。 比如算 20% 小费，没人会真去做 `金额 × 20 / 100` 的除法。大家下意识的捷径是 `金额 / 5`，甚至更进一步 `金额 × 2 / 10`——先翻倍再砍掉一位零。还有"除以 5"的经典速算：**乘以 2 再除以 10**。注意这里发生了什么：你把一次难算的除法，拆成了一次乘法加一次"移位"（十进制下除以 10 就是小数点左移一位）。 Computerphile 的精明之处在于：它没有一上来就讲二进制补码，而是先用这种人人都会的小学速算告诉你——**"用乘法和移位替换除法"不是程序员的奇技淫巧，而是大脑本能就在做的事**。这个类比让后面硬核的部分变得极易接受。 ### 三、十进制版魔法数：除以 3 怎么"不除" 视频第 4–5 分钟演示了全片最关键的一步：**在不做除法的前提下，除以 3**。 十进制下，`1/3 = 0.3333…`，是一个无限循环小数。但如果你只取四位近似，`1/3 ≈ 3333/10000`。于是： ``` x / 3 ≈ x × 3333 / 10000 ``` 你把"除以 3"变成了"乘以 3333，再把结果右移四位十进制（即除以 10000）"。虽然 3333 是 1/3 的近似，但因为只是稍微偏小，做一点修正就能让它在有限范围内完全精确。这就是视频所说的"编译器的十进制除法秘密"——**用乘法 + 移位 + 修正，完美模拟除法**。人类的 0.3333，和编译器后面要登场的二进制魔法数，是同一个思想在两种进制的投影。 ### 四、二进制超能力：除以 2 的幂就是移位 视频 6:51 之后揭示了计算机的"主场优势"。在二进制世界里，**除以 2 的幂（2、4、8、16……）等价于一次右移**： - `x / 2` = `x >> 1` - `x / 256` = `x >> 8` - `x / 65536` = `x >> 16` 移位（shift）几乎和加法一样便宜，1 个周期搞定。所以对 2 的幂的除法，CPU 早就不是问题。真正的难点在于：**除以 3、7、255、1001 这种"丑陋"的常数怎么办？** 这才是 Granlund–Montgomery 算法要解决的硬骨头。 ### 五、核心把戏揭密：魔法数是怎么算出来的 把前面几步合起来，全片的"底牌"是：**任何除以常数 `d`，都能改写成"乘以一个魔法数 `m`，再右移若干位"**。两个真实的、被 GCC/Clang 天天生成的例子： ``` 32 位无符号 x / 3 → (x × 0xAAAAAAAB) >> 33 32 位无符号 x / 255 → (x × 0x80808081) >> 39 ``` 那个看起来不知所云的巨大常数（`0xAAAAAAAB` = 2863311531），就是"魔法数"。它的数学原理其实很朴素：**`1/d` 在二进制下是一个无限小数，我们取它的前若干位，乘以 `2^k` 把它"撑"成一个整数 `m`**。于是： ``` x / d = x × (1/d) ≈ x × m / 2^k = (x × m) >> k ``` 乘法取的是 64 位积的高位（相当于已经右移了 32 位），剩下的余数位由右移补齐。由于 `m` 是 `1/d × 2^k` 向上取整而来，**稍微偏大一点**，配合一次修正（Granlund–Montgomery 的关键贡献就是这个"向上取整 + 修正"，保证对所有输入都精确、不差 1），就实现了**零误差**的除法。（这部分数学细节是对视频"魔法数"概念的精确化展开，视频用直觉讲解了原理，这里给出可验证的公式） ### 六、为什么这是"诚实的谎言"：你写的代码在骗你 最具讽刺意味的一点：**你写 `x / 3`，编译器从不生成除法指令**。你可以亲手验证——把一段含 `a / 3` 的 C 代码丢给 `gcc -O2 -S`，生成的汇编里根本没有 `idiv`，只有一条 `imul`（乘法）加一条 `shr`（移位）。 这意味着两件事：第一，**"除法慢"这个常识，在现代编译器面前对常数除法已经部分失效**——只要你除的是编译期已知的常数，它早被优化掉了。第二，也提醒我们：**读懂汇编比读懂源码更能反映程序的真实开销**。源码层面看起来天差地别的 `x/3` 和 `x*y`，到了机器层可能一样快；而你自以为"等价"的两个写法，编译器可能给出截然不同的指令。这是视频留给资深开发者的隐性彩蛋。 ### 七、三十年技术史：从图形学到教科书 视频没展开，但这条线值得补全（以下为延伸背景）：这套思想最早可追溯到 1991 年 Robert Alverson 的论文《Integer Division Using Reciprocals》——当时 Tera 计算机甚至把它做成了**硬件除法的实现方式**。1995 年图形学泰斗 Jim Blinn 在 IEEE 专栏里用它算 alpha 合成里高频出现的 `x/255`，给出经典公式 `x/255 = (x×257+257) >> 16`（16 位无符号）。1994 年，Torbjörn Granlund 和**RSA 之父 Peter Montgomery**（没错，就是那个 Montgomery）在 PLDI 上发表《Division by Invariant Integers Using Multiplication》，把它写进了 GCC，从此惠及全世界。Henry S. Warren 的《Hacker's Delight》一书为它留了 **46 页**篇幅。开源库 libdivide 把它做成可复用工具。**而 2026 年 4 月，arXiv 上仍有人在发新论文优化"64 位目标上 32 位除法"的特殊情形**——三十年了，这个"把戏"还在被刷新。 ## 知识结构图 ```mermaid flowchart TD A[源码: x / d
常数除法] --> B{编译器识别
d 是否为常量?} B -->|是 常量| C[计算魔法数 m 与移位 k
Granlund-Montgomery 算法] B -->|否 运行时变量| Z[老实生成 idiv 指令
慢 但无法避免] C --> D{d 是否为 2 的幂?} D -->|是| E[直接右移: x >> log2 d
约1周期] D -->|否| F[生成 imul m + shr k
约3-4周期] F --> G[乘法取高位= 近似商] G --> H[向上取整修正
保证零误差] H --> I[最终: 精确的 x/d
完全无除法指令] E --> I Z --> J[真实除法
20-40周期] K[历史脉络] --> K1[1991 Alverson
硬件实现] K1 --> K2[1994 Granlund-Montgomery
写入 GCC] K2 --> K3[Hacker's Delight 46页] K3 --> K4[libdivide / 2026 arXiv 新优化] style A fill:#fef3c7 style I fill:#d1fae5 style J fill:#fee2e2 ``` ## 实战启示：这对开发者意味着什么 **第一，别再迷信"除法一定慢"。** 在你已经看到 `x / constant` 的地方，编译器几乎肯定已经把它换成乘法了。真正会让你吃亏的，是**除数在运行时才确定的除法**——比如 `x / runtime_divisor`。这种情况下，循环里每次都走慢指令。如果你在热循环里反复除以同一个变量，预计算一次、或借助 libdivide 这类库，能拿到几倍到十几倍的提速。NumPy 在 2019 年就讨论过用 libdivide 替换内部整数除法，正是这个思路。 **第二，学会用 `-O2 -S` 看一眼汇编。** 这是判断"我的优化有没有生效"的唯一可靠方法。你以为的"等价改写"，编译器未必买单；你以为的"昂贵操作"，可能早被消掉了。养成瞄一眼生成代码的习惯，是初级工程师跨向资深的关键一步。 **第三，理解定点数思维的价值。** 魔法数除法的本质，是用整数去逼近一个分数（定点数表示）。这套思想在**嵌入式、DSP、游戏引擎、图形渲染**里无处不在：没有浮点单元（FPU）的 MCU、追求极致性能的物理模拟，都用定点数代替浮点。看懂了这个把戏，你就拿到了进入底层优化世界的钥匙。 **第四，对"魔法常数"保持敬畏而非恐惧。** 反编译或老代码里那些奇怪的 `0xAAAAAAAB`、`0x80808081`，不是程序员的恶作剧，是数学的必然。下次再看到，你能一眼认出"哦，这是在除以某个常数"。 ## 延伸学习路径 1. **《Hacker's Delight》Henry S. Warren 著** — 全书是位运算与算术技巧的圣经，魔法数除法占整整 46 页，配套网站有在线 magic number 计算器。 2. **Russ Cox《Division via Multiplication》（research.swtch.com/divmult）** — Go 语言核心作者写的极简清晰科普，一篇文讲透 `x/255 = (x×257+257)>>16`。 3. **ridiculousfish《Labor of Division》系列博客 + libdivide 开源库** — 想在生产代码里复用这套优化的开发者必读，仓库可直接集成。 4. **原始论文：Granlund & Montgomery, 1994《Division by Invariant Integers Using Multiplication》** — 想吃透数学推导的硬核读者去看源头。 5. **亲手实验**：写一段 `unsigned f(unsigned x){return x/3;}`，用 `gcc -O2 -S` 或 Compiler Explorer（godbolt.org）看汇编，亲自确认没有 `idiv`，只有 `imul`+`shr`。 ## 一句话总结 **你以为 CPU 在做除法，其实编译器三十年来一直用一次乘法在骗它——这就是魔法数除法，人类算小费的直觉与编译器底层优化的一次完美会师。** ## 参考来源 1. [The "Trick" that Compilers Use for Long Division — Computerphile](https://www.youtube.com/watch?v=-14t6_yu-7w) — 本文分析的核心视频 2. [Division via Multiplication — Russ Cox (research.swtch.com)](https://research.swtch.com/divmult) — 经典技术科普，含 255/257 实例 3. [Labor of Division (Episode III) — ridiculousfish](https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html) — libdivide 作者的无符号魔法数详解 4. [Constant Division in Compilers: The Granlund-Montgomery Method](https://www.newsdirectory3.com/constant-division-in-compilers-the-granlund-montgomery-method/) — 2026 年对该算法的当代解读 5. [Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets (arXiv:2604.07902, 2026)](https://arxiv.org/html/2604.07902) — 三十年后仍在推进的最新学术研究 > 本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵**爱卫生**（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 > 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。 ### 完成摘要（What was done） ### 下一步计划 1. （优先）继续后续轮次（Round 3 = business 商业与创业），保持去重校验 2. 如需本篇配套可视化：可用 `chart-craft`/`mermaid-generator` 将魔法数推导做成动态演示图 3. 建议建立本地"已覆盖主题"缓存文件，避免每轮重新比对超长列表 ### 注意事项 - 本环境 `WebSearch`/`MCP webReader` 当日配额已耗尽（次日 11:07 UTC 重置），后续轮次若需联网检索建议优先用 `ddgs`/`ducksearch`，但需注意其 fetch 对 YouTube 等纯 JS 页面只能取到极少内容 - `/tmp` 目录被沙箱拦截，临时文件需写入 `/home/gprshome` 工作目录 - 已在工作目录留有两个临时文件 `yt_clips.txt`、`divmult.txt`，可按需删除 > [!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 等场景全覆盖。