用乘法执行整数除法 [英] 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 ，等等。

开拓了 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"?

推荐答案

这方法被称为，由司乘不变。

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

这是你看到的常量实际上接近倒数的。

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

因此​​，而不是计算：

So rather than computing:

N / D = Q

您做这样的事情，而不是：

you do something like this instead:

N * (1/D) = Q

其中， 1 / D 是可以$ P $互惠pcomputed。

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

从根本上说，是倒数IM precise除非 D 是一个电源的两种。于是就有一些涉及舍入误差。在 +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屋！