使用乘法执行整数除法
Perform integer division using multiplication
查看编译器生成的 x86 程序集，我注意到（无符号）整数除法有时会实现为整数乘法。这些优化似乎遵循
的形式
value / n => (value * ((0xFFFFFFFF / n) + 1)) / 0x100000000
例如除以9：
12345678 / 9 = (12345678 * 0x1C71C71D) / 0x100000000
除以 3 将使用 0x55555555 + 1 的乘法，依此类推。
利用mul指令将结果的高位部分存储在edx寄存器中这一事实，除法的最终结果可以使用具有幻数的单个乘法获得。 （尽管这种优化有时会与末尾的逐位移位结合使用。）
我想了解一下这实际上是如何工作的。这种方法何时有效？为什么我们的"magic number"一定要加1？
调用该方法，"Division by Invariant Multiplication"。
您看到的常数实际上是倒数的近似值。
所以不是计算：
N / D = Q
你改为这样做：
N * (1/D) = Q
其中 1/D 是可以预先计算的倒数。
从根本上说，倒数是不精确的，除非 D 是二次方。所以会有一些舍入误差。您看到的 +1 是为了纠正舍入误差。
最常见的例子是除以 3:
N / 3 = (N * 0xaaaaaaab) >> 33
其中 0xaaaaaaab = 2^33 / 3 + 1.
这种方法将推广到其他除数。
查看编译器生成的 x86 程序集，我注意到（无符号）整数除法有时会实现为整数乘法。这些优化似乎遵循
的形式value / n => (value * ((0xFFFFFFFF / n) + 1)) / 0x100000000
例如除以9：
12345678 / 9 = (12345678 * 0x1C71C71D) / 0x100000000
除以 3 将使用 0x55555555 + 1 的乘法，依此类推。
利用mul指令将结果的高位部分存储在edx寄存器中这一事实，除法的最终结果可以使用具有幻数的单个乘法获得。 （尽管这种优化有时会与末尾的逐位移位结合使用。）
我想了解一下这实际上是如何工作的。这种方法何时有效？为什么我们的"magic number"一定要加1？
调用该方法，"Division by Invariant Multiplication"。
您看到的常数实际上是倒数的近似值。
所以不是计算：
N / D = Q
你改为这样做：
N * (1/D) = Q
其中 1/D 是可以预先计算的倒数。
从根本上说，倒数是不精确的，除非 D 是二次方。所以会有一些舍入误差。您看到的 +1 是为了纠正舍入误差。
最常见的例子是除以 3:
N / 3 = (N * 0xaaaaaaab) >> 33
其中 0xaaaaaaab = 2^33 / 3 + 1.
这种方法将推广到其他除数。