使用乘法执行整数除法

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是二次幂,否则倒数是不精确的.因此会涉及一些舍入错误.在+1你看到的是有纠正的舍入误差.

最常见的例子是除以3:

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

哪里0xaaaaaaab = 2^33 / 3 + 1.

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