整数除以7

  • Z时代
  • 2024-01-10
  • 分类：问答

我在这里有点不适应，并且试图了解这种特定的优化是如何工作的。

如答案中所述，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的最接近倍数。或者换句话说，

这个八进制数字是多少？

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

归类为什么近似失败的原因超出了我一点，为什么补丁也将其修复。有谁知道魔术的作用超出了我在这里所说的范围？

回答：

该算法的第一部分是乘以7的倒数的近似值。在这种情况下，我们正在近似地计算带有整数乘法和右移的倒数。

首先，我们将值-1840700269（八进制-015555555555）视为32位整数。如果将其读取为无符号的32位整数，则其值为2454267027（octal

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地方。）

无论如何，对于最后一行，这是我们在以这种方式计算有符号整数除法之后进行的调整。我引用了骇客对签名划分的高兴部分：

该代码最自然地计算下限分割结果，因此我们需要进行更正以使其计算常规的截断为0的结果。如果被除数为负，则可以通过将三个计算指令加到被除数上来完成此操作。

在这种情况下（请-1参阅您的其他帖子），您似乎正在执行带符号的班次，因此在负数的情况下它将减去。给出的结果+1。

这甚至不是您能做的。这是一个甚至更疯狂的博客文章，内容涉及如何只用一个乘法就将其除以7。

以上是 整数除以7 的全部内容， 来源链接： utcz.com/qa/413382.html

回到顶部