把编译器比下去：有符号 32 位除法的更优常量除法
来源：lemire.me — 2026-10-31
📋 概述
Daniel Lemire 展示如何在有符号 32 位除法上跑赢编译器。除数恒定时，编译器按 Granlund–Montgomery 的办法把除法换成乘法加移位；但对有符号 32 位、除数取 3 到 1000 之间的非 2 的幂时，约 38%（990 个里的 376 个）的理想乘数需要 33 位，塞不进有符号 32 位，编译器只好额外插入「把 x 加回来」和符号修正。在 64 位机器上其实可以改用无符号 32 位乘数配 64 位乘法：作者与 Bartlett、Kaser 的定理给出取 m=2^s ≥ d·2^31、c=⌈m/d⌉ 的构造，依赖链因此缩短。
🔑 核心要点
- 32 位除法很慢：Emerald Rapids 延迟约 12 周期、每 6 周期一条，Apple M4 延迟 7 周期、每 2 周期一条。
- 除数恒定则除法变乘法移位，但理想乘数常超过 32 位，编译器不得不加修正步骤。
- 3 到 1000 的非 2 的幂除数中 38%（990 个里的 376 个）会有这个问题。
- 64 位平台上不会溢出：|x| ≤ 2^31，而无符号 32 位乘数小于 2^32，乘积绝对值 < 2^63。
- 取 s = 31 + ⌈log2 d⌉、c = ⌊2^s/d⌋ + 1，按定理即为最优常量，实现只有三行模板。
- GCC 14 编出的新版本把依赖链从 movsx/imul/shr/add/sar/sub 缩成 movsx/imul/sar/add。
- 作者也不知道编译器为什么不用这个更短的形式。
💡 金句
我们能比编译器做得更好吗？在 64 位系统上处理有符号 32 位整数时，答案常常是能。
👍 0
👎 0
← 返回 Lobsters 首页