使用乘法执行整数除法

Question

查看由编译器生成的x86程序集，我注意到（无符号）整数除法有时实现为整数乘法。这些优化似乎遵循形式

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

例如，通过9执行除法：

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

由3所述的分割将利用乘法0x55555555 + 1，等等。

利用mul指令将结果的高位部分存储在edx寄存器中的事实，最终的除法结果可以使用带有魔值的单乘法获得。 （虽然这种优化有时与最后按位移位结合使用）。

我想了解一下这个实际工作原理。这种方法何时有效？为什么必须将1添加到我们的“幻数”中？

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。

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