整数除以7

Question

请参考我的回答:

Is this expression correct in C preprocessor

我在这个领域有点不熟悉，正在尝试理解这种特定的优化方法。

正如答案中提到的那样，gcc将对除以7的整数除法进行优化：

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

转换回C语言的代码如下：

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

让我们来看一下第一部分：

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

为什么是这个数字？

好的，我们来计算一下2的64次方除以7得到的结果。

2^64 / 7 = 2635249153387078802.28571428571428571429

看起来很混乱，如果我们将它转换成八进制会怎么样？

0222222222222222222222.22222222222222222222222

这是一个非常漂亮的重复模式，肯定不是巧合。我们记得7是0b111，我们知道当我们除以99时，倾向于在十进制中获得重复模式。因此，当我们除以7时，我们得到一个八进制的重复模式是有道理的。

那么我们的数字从哪里来？

(int32_t)-1840700269与(uint_32t)2454267027相同

* 7 = 17179869189

最后，17179869184是2^34

这意味着17179869189是最接近7·2^34的倍数的数。换句话说，2454267027是最大的适合uint32_t的数，当它乘以7时，非常接近于2的幂次方

这个数字的八进制表示是什么？

0222222222223

为什么这很重要？我们想要除以7。 这个数字是2的34次方/ 7...大约如此。 因此，如果我们乘以它，然后左移34次，我们应该得到一个非常接近精确数字的数字。

最后两行看起来像是为弥补近似误差而设计的。

也许在这个领域有更多知识和/或专业知识的人可以发表意见。

>>> 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。

为什么近似会失败以及修补程序如何解决这个问题，我不太清楚。有人知道更多的魔法原理吗？

- OmnipotentEntity

---

http://www.hackersdelight.org/divcMore.pdf - Mitch Wheat

那份PDF对于确定最后一行的作用（符号修正）非常有帮助；然而，它似乎没有特别讨论这个算法，除非我错过了。 - OmnipotentEntity

明确的参考资料在这里（已实现于gcc编译器），以及后续的这里。实现可以在GMP库中找到（gmp-impl.h中的udiv_qrnnd_preinv）。 - Brett Hale

Answer 1

算法的第一部分是通过一个近似值来乘以7的倒数。在这种情况下，我们使用整数乘法和右位移来近似计算倒数。

首先，我们将值-1840700269（八进制-015555555555）作为32位整数进行查看。如果将其读取为无符号32位整数，则其值为2454267027（八进制22222222223）。事实证明，2454267027 / 2^34是1/7的一个非常接近的整数近似值。

为什么选择这个数字和这个特定的2次幂？我们使用的整数越大，近似值就越接近。在这种情况下，2454267027似乎是最大的整数（满足上述属性），可以将其与带符号的32位int相乘而不会溢出64位int。

接下来，如果我们立即向右移动>> 34并将结果存储在32位int中，我们将失去最低阶位的精度。这些位对于确定整数除法的正确floor很重要。

我不确定第二行是否从x86代码正确翻译过来。此时，temp大约是num*4/7，因此num*4/7+num和位移将给您大约num*1/7+num*1/4，误差非常大。

例如，以57为输入，其中57 // 7 = 8。我在代码中也进行了验证：

57 * 2454267027 = 139893220539 139893220539 >> 32 = 32（近似值为57 * 4/7 = 32.5714…） 32 + 57 = 89 89 >> 2 = 22（嗯？此时与8不太接近。）

无论如何，对于最后一行，这是我们在以这种方式计算带符号整数除法之后进行的调整。我从Hacker's delight的带符号除法部分引用：

代码最自然地计算floor除法结果，因此我们需要进行修正，使其计算常规截断为0结果。如果被除数为负，则可以通过三个计算指令将其添加到被除数中来完成此操作。

在这种情况下（参考您的其他帖子），似乎您正在进行有符号移位，因此在负数的情况下它将减去-1；从而得到+1 的结果。

这还不是全部；这里有一篇更疯狂的博客文章，介绍如何只用一次乘法除以7。

- Andrew Mao