整数除以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时，我们倾向于获得基数为10的重复模式。因此，当我们除以7时，我们将在基数8中得到重复模式。

那么我们的号码进来了吗？

(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

判断为什么逼近失败是有点超出我，为什么补丁修复它是为好。有谁知道魔法如何超越我在这里放下的东西？

Answer 1

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

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

为什么我们选择这个号码的2这个特殊的权力？我们使用的整数越大，近似值越接近。在这种情况下，2454267027似乎是最大的整数（满足上述属性），您可以使用该整数乘以带符号的32位整数，而不会溢出64位整数。接下来，如果我们立即右移>> 34并将结果存储在32位int中，我们将失去两个最低位的精度。这些位对于确定整数除法的正确底数是必需的。

我不知道第二行是从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在这一点上。）

反正最后一行，这是我们计算符号整数除法这种方式后进行调整。笔者从部分引用来自黑客的喜悦签署师：

代码最自然的计算楼层划分结果，所以我们需要 修正，使其计算传统的朝0 结果截断。如果股息为负数，则可以通过 三条计算指令加上股息来完成此操作。

在这种情况下（指你的其他文章）似乎是在做签署的转变，所以它会在负数的情况下，减去-1;给出+1的结果。

这甚至不是你所能做到的;这里有一个更疯狂的blog post about how to divide by 7 with just a single multiplication。