使用乘法实现整数除法

Question

我注意到由编译器生成的x86汇编，有时会将无符号整数除法实现为整数乘法。这些优化似乎遵循以下形式：

value / n => (value * ((0xFFFFFFFF / n) + 1)) / 0x100000000

例如，进行9的除法：

12345678 / 9 = (12345678 * 0x1C71C71D) / 0x100000000

除以 3 可以使用 0x55555555 + 1 进行乘法计算，其他数也同理。

由于 mul 指令会将结果的高位存储在 edx 寄存器中，因此可以通过一次乘法计算使用一个魔术数字得出最终的除法结果。（尽管有时候还需要在末尾进行位移。）

我想了解一下这是如何实现的。这种方法什么情况下适用？为什么必须加上 1 来使用我们的“魔数”？

- user1421750

---

你要乘以的常数是倒数的近似值。这里随机出现的正负1是为了确保它始终正确“四舍五入”。证明特定方法的正确性可以通过数学方法或对所有分子进行暴力测试来完成。（对于32位，这是完全可行的。） - Mysticial

@ScottHunter 或许等我下班后再回复你。我现在手头没有足够的工具来给出全面的答案。 - Mysticial

http://homepage.cs.uiowa.edu/~jones/bcd/divide.html - old_timer

@Mysticial：你写的评论看起来比我见过的很多答案（包括我自己写的）都要好。但我猜这就是一个人如何获得20万+声望值的方法。 - Scott Hunter

我非常确定它没有执行“/ 0xFFFFFFFF”... - Jester

Answer 1

那种方法被称为“不变乘法的除法”。

你看到的常数实际上是倒数的近似值。

因此，与其计算：

N / D = Q

相反，你应该这样做：

N * (1/D) = Q

其中1/D是一个可预先计算的倒数。

从根本上说，除非D是2的幂次方，否则倒数是不精确的。因此会涉及一些舍入误差。您看到的+1是为了纠正这种舍入误差。

---

最常见的例子就是除以3：

N / 3 = (N * 0xaaaaaaab) >> 33

当 0xaaaaaaab = 2^33 / 3 + 1 时。

这种方法可以推广到其他除数。

- Mysticial

---

经典参考文献为：T. Granlund和P.L. Montgomery, “使用乘法进行不变整数除法”，发表于1994年的SIGPLAN程序设计语言设计与实现会议论文集，页码为61-72。 - njuffa

更近期的参考资料：N. Möller 和 T. Granlund，"Improved division by invariant integers," IEEE Transactions on Computers，卷60，号2，页165-175，2011年2月。 - njuffa

你的概括和证明是错误的。此外，用于除以3的0x55555556仅适用于有符号范围，即最高可达2 ^ 31。 - Jester

@Jester 我猜我在数学方面很差。我已经删除了答案的那部分。 - Mysticial

@StéphaneGourichon - 除以7和其他一些值需要特殊处理。 "精确"的倒数比整数位数多1个位。这是使用32位值和5条指令序列（mul，sub，shift right 1，add，shift right ...）而不是2条指令序列（mul，shift right ...）来处理的。这在之前的问题中有解释。 - rcgldr