使用乘法执行整数除法[重复]

Question

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

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

例如，执行除以9：

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

除以3将使用与＜code＞0x55555555 1＜/code＞的乘法，依此类推。

利用< code>mul指令将结果的高部分存储在< code>edx寄存器中这一事实，可以使用与幻值的单次乘法来获得除法的最终结果。(尽管这种优化有时在最后与逐位移位结合使用。)

我想了解一下这实际上是如何工作的。这种方法什么时候有效？为什么必须将1添加到我们的“神奇数字”中？

Answer 1

该方法称为“除以不变乘法”。

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

因此，不是计算：

N / D = Q

你做这样的事情：

N * (1/D) = Q

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

从根本上说，倒数是不精确的，除非＜code＞D＜code＞是2的幂。所以会有一些舍入误差。您看到的＜code＞1

最常见的例子是除以3：

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

其中< code > 0x aaaaaaab = 2^33/3 ^ 1 。

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