整数除以7

Question

来源我的回答:

这个表达式在C预处理器中是否正确

我有点不在这里,我试图了解这种特殊优化是如何工作的.

正如答案中提到的,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 ...约.因此,如果我们乘以它,然后leftshift 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位int而不会溢出64位int.

接下来,如果我们立即右移>> 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在这一点上无处接近.)

无论如何,对于最后一行,这是我们在以这种方式计算有符号整数除法之后进行的调整.我引用了Hacker对签名部门的喜悦部分:

代码最自然地计算分层结果,因此我们需要进行校正以使其计算传统截断为0的结果.如果被除数为负,则可以通过向被除数添加三个计算指令来完成.

在这种情况下(指你的另一篇文章),你似乎正在做一个有符号的班次,所以-1在负数的情况下它会减去; 给出结果+1.

这甚至都不能做到; 这里有一篇关于如何用一次乘法除以7的更疯狂的博客文章.