使用乘法执行整数除法 [英] Perform integer division using multiplication

问题描述

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

Looking at x86 assembly produced by a compiler, I noticed that (unsigned) integer divisions are sometimes implemented as integer multiplications. These optimizations seem to follow the form

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

例如，执行除以 9:

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

除以 3 将使用乘法与 0x55555555 + 1，依此类推.

A division by 3 would use multiplication with 0x55555555 + 1, and so on.

利用mul指令将结果的高位存储在edx寄存器中的事实，可以使用单次乘法得到除法的最终结果一个魔法值.(尽管这种优化有时会与最后的逐位移位结合使用.)

Exploiting the fact that the mul instruction stores the high part of the result in the edx register, the final result of the division can be obtained using a single multiplication with a magic value. (Though this optimization is sometimes used in conjunction with a bit-wise shift at the end.)

我想了解一下这实际上是如何工作的.这种方法什么时候有效?为什么必须在我们的幻数"中加 1?

I would like some insight on how this actually works. When is this approach valid? Why must 1 be added to our "magic number"?

推荐答案

那个方法叫做Division by Invariant Multiplication".

That method is called, "Division by Invariant Multiplication".

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

The constants that you're seeing are actually approximates of the reciprocal.

所以而不是计算:

N / D = Q

你改为这样做:

N * (1/D) = Q

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

where 1/D is a reciprocal that can be precomputed.

从根本上说，倒数是不精确的，除非 D 是 2 的幂.所以会涉及一些舍入误差.您看到的 +1 用于纠正舍入误差.

Fundamentally, reciprocals are imprecise unless D is a power-of-two. So there will some round-off error involved. The +1 that you see is there to correct for the round-off error.

最常见的例子是除以 3:

The most common example is division by 3:

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

其中0xaaaaaaab = 2^33/3 + 1.

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

This approach will generalize to other divisors.

这篇关于使用乘法执行整数除法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！