整数除以7 [英] Integer division by 7

问题描述

在源我的回答：

<一个href="http://stackoverflow.com/questions/15260644/is-this-ex$p$pssion-correct-in-c-$p$pprocessor/15261439#15261439">Is这当然pression在C preprocessor正确

我是有点出我的专长在这里，我试图理解这种特定的优化工作。

I'm a little bit out of my forte here, and I'm trying to understand how this particular optimization works.

正如答案，海湾合作委员会将由7优化的整数除法：

As mentioned in the answer, gcc will optimize integer division by 7 to:

mov edx, -1840700269
mov eax, edi
imul    edx
lea eax, [rdx+rdi]
sar eax, 2
sar edi, 31
sub eax, edi

这回转换成C为：

Which translates back into C as:

int32_t divideBySeven(int32_t num) {
    int32_t temp = ((int64_t)num * -015555555555) >> 32;
    temp = (temp + num) >> 2;
    return (temp - (num >> 31));
}

让我们来看看第一部分：

Let's take a look at the first part:

int32_t temp = ((int64_t)num * -015555555555) >> 32;

为什么这个数字？

Why this number?

好了，让我们先2 ^ 64和7分，看看会弹出。

Well, let's take 2^64 and divide it by 7 and see what pops out.

2^64 / 7 = 2635249153387078802.28571428571428571429

这看起来像一个烂摊子，如果我们把它转换成八进制？

That looks like a mess, what if we convert it into octal?

0222222222222222222222.22222222222222222222222

这是一个非常pretty的重复模式，当然这不可能是巧合。我的意思是，我们记得，7 0b111 ，我们知道，当我们除以99，我们往往会得到重复图案的底座10所以它是有道理的，我们会得到一个重复模式在基地8时，我们除以7。

That's a very pretty repeating pattern, surely that can't be a coincidence. I mean we remember that 7 is 0b111 and we know that when we divide by 99 we tend to get repeating patterns in base 10. So it makes sense that we'd get a repeating pattern in base 8 when we divide by 7.

那么，这是否我们的一些进来吗？

So where does our number come in?

（int32_t）-1840700269 是一样的（uint_32t）2454267027

* 7 = 17179869189

最后17179869184为 2 ^ 34

And finally 17179869184 is 2^34

这意味着17179869189为7 2 ^ 34最接近的倍数。或者换一种说法 2454267027是，将适合人数最多的一个 uint32_t的，当了7乘以非常接近的功率2

Which means that 17179869189 is the closest multiple of 7 2^34. Or to put it another way 2454267027 is the largest number that will fit in a uint32_t which when multiplied by 7 is very close to a power of 2

什么是八进制这个数字？

What's this number in octal?

0222222222223

为什么这很重要？好了，我们想通过7分这个数字是2 ^七分之三十四...约。因此，如果我们乘以它，然后leftshift 34倍，我们应该得到了一些非常接近的具体数量。

Why is this important? Well, we want to divide by 7. This number is 2^34/7... approximately. So if we multiply by it, and then leftshift 34 times, we should get a number very close to the exact number.

最后两行看起来像他们的目的是修补逼近误差。

The last two lines look like they were designed to patch up approximation errors.

也许有人在这一领域多一点知识和/或专门知识可以在此附和

Perhaps someone with a little more knowledge and/or expertise in this field can chime in on this.

>>> magic = 2454267027
>>> def div7(a):
...   if (int(magic * a >> 34) != a // 7):
...     return 0
...   return 1
... 
>>> for a in xrange(2**31, 2**32):
...   if (not div7(a)):
...     print "%s fails" % a
... 

故障开始在3435973841这是有趣的是0b11001100110011001100110011010001

Failures begin at 3435973841 which is, funnily enough 0b11001100110011001100110011010001

判断为何近似失败是有点出乎我的，为什么补丁修复它是为好。有谁知道如何变魔术超出我已经放下了吗？

Classifying why the approximation fails is a bit beyond me, and why the patches fix it up is as well. Does anyone know how the magic works beyond what I've put down here?

推荐答案

该算法的第一部分由一个近似7.倒数在这种情况下，我们近似计算一个整数乘法的倒数相乘和右位移动。

The first part of the algorithm is multiplying by an approximation to the reciprocal of 7. In this case, we're approximating computing the reciprocal with an integer multiplication and a right bit-shift.

首先，我们看到了值 -1840700269 （八进制 -015555555555 ）作为32位整数。如果你读这是一个32位无符号整数，它的价值 2454267027 （八进制 22222222223 ）。事实证明，2分之2454267027^ 34 是一款非常接近整数逼近 1/7 。

First, we see the value -1840700269 (octal -015555555555) as a 32-bit integer. If you read this as an unsigned 32 bit integer, it has value 2454267027 (octal 22222222223). It turns out that 2454267027 / 2^34 is a very close integer approximation to 1/7.

为什么我们选择这个号码的2这个特殊的权力？在我们使用整数越大，越接近近似。在这种情况下， 2454267027 似乎是最大的整数（满足上述属性），您可以乘有符号的32位int不会溢出64位整型。

Why do we pick this number and this particular power of 2? The larger the integers we use, the closer the approximation is. In this case, 2454267027 seems to be the largest integer (satisfying the above property) with which you can multiply a signed 32-bit int without overflowing a 64-bit int.

接下来，如果我们立即向右移＆GT;＆GT; 34 和结果存储在一个32位int，我们将失去两个最低阶位的精度。这些位是必要的，以确定正确的地板整数除法。

Next, if we immediately right shift with >> 34 and store the result in a 32-bit int, we're going to lose the accuracy in the two lowest-order bits. Those bits are necessary to determining the right floor for integer division.

我不知道，第二行是从86 code正确转换。在这一点上，<​​code>温度约 NUM * 4/7 ，所以 NUM * 4 / 7 + NUM 到和位移是想给你约 NUM * 1/7 + NUM * 1/4 ，一个相当大错误。

I'm not sure the second line was translated correctly from the x86 code. At that point, temp is approximately num * 4/7, so num * 4/7 + num to that and bit-shifting is going to give you approximately num * 1/7 + num * 1/4, a quite large error.

例如，作为输入57，其中 57 // 7 = 8 。我验证了低于code，以及：

For example, take as input 57, where 57 // 7 = 8. I verified the below in code as well:

• 57 * 2454267027 = 139893220539
• 139893220539＆GT;＆GT; 32 = 32 （约 57 * 4/7 = 32.5714 ... 在这一点）
• 32 + 57 = 89
• 89＆GT;＆GT; 2 = 22 （呵呵??无处接近 8 在这一点上。）

• 57 * 2454267027 = 139893220539
• 139893220539 >> 32 = 32 (approx 57 * 4/7 = 32.5714... at this point)
• 32 + 57 = 89
• 89 >> 2 = 22 (huh?? Nowhere close to 8 at this point.)

总之，在过去的路线，这是我们的计算有符号整数除法这种方式后进行调整。笔者从部分引用来自黑客的喜悦签署划分：

Anyway, for the last line, it is an adjustment we make after computing signed integer division this way. I quote from the section from Hacker's delight on signed division:

在code最自然的计算楼层分工的结果，所以我们需要   校正以使其计算常规朝向0截断   结果。这可以用由三个计算说明进行   增加了分红，如果被除数是负的。

The code most naturally computes the floor division result, so we need a correction to make it compute the conventional truncated toward 0 result. This can be done with three computational instructions by adding to the dividend if the dividend is negative.

在此情况下（指你的其他职位）看来你是做一个签名的转变，所以它会减去 1 在负数的情况;给出的结果 +1 。

In this case (referring to your other post) it seems you are doing a signed shift, so it will subtract -1 in the case of a negative number; giving the result of +1.

这甚至不是你能做的一切;这里有一个更疯狂博客文章只是一个单一的乘法。

This isn't even all you can do; here's an even crazier blog post about how to divide by 7 with just a single multiplication.

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