assembly - 使用乘法执行整数除法

assembly - 使用乘法执行整数除法,第1张

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

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

例如,按9进行除法:

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

除以3将使用乘法0x55555555 1,依此类推。

利用mul指令将结果的高部分存储在edx寄存器中的事实,可以使用具有魔术值的单个乘法获得除法的最终结果。 (虽然这种优化有时与最后的逐位移位一起使用。)

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

最佳答案:

1 个答案:

答案 0 :(得分:15)

该方法称为“由不变乘法划分”。

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

所以而不是计算:

N / D = Q

你做的是这样的事情:

N * (1/D) = Q

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

从根本上说,除非D是2的幂,否则倒数是不精确的。因此会涉及一些舍入错误。您看到的 1可用于更正舍入错误。

最常见的例子是除以3:

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

0xaaaaaaab = 2^33 / 3 1

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

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复