查看编译器生成的 x86 程序集,我注意到(无符号)整数除法有时会实现为整数乘法。这些优化似乎遵循以下形式
value / n => (value * ((0xFFFFFFFF / n) + 1)) / 0x100000000
例如,除以 9:
12345678 / 9 = (12345678 * 0x1C71C71D) / 0x100000000
除以 3 将使用乘法0x55555555 + 1
, 等等。
利用这一事实mul
指令将结果的高位部分存储在edx
寄存器中,除法的最终结果可以使用与魔术值的单个乘法来获得。 (尽管这种优化有时与最后的按位移位结合使用。)
我想了解一下这实际上是如何运作的。这种方法什么时候有效?为什么我们的“神奇数字”必须加 1?
该方法称为“除以不变乘法”。
您看到的常数实际上是倒数的近似值。
因此,而不是计算:
N / D = Q
你可以这样做:
N * (1/D) = Q
where 1/D
是可以预先计算的倒数。
从根本上说,倒数是不精确的,除非D
是二的幂。因此会涉及一些舍入误差。这+1
您看到的就是纠正舍入误差的。
最常见的例子是除以 3:
N / 3 = (N * 0xaaaaaaab) >> 33
Where 0xaaaaaaab = 2^33 / 3 + 1
.
这种方法将推广到其他除数。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)