为什么0x55555556除以3个黑客？

Question

有一种(相对的)众所周知的将32位数除以3的黑客.而不是使用实际昂贵的除法，数字可以乘以幻数0x55555556，结果的上32位才是我们要找的。例如，以下C代码：

int32_t div3(int32_t x)
{
    return x / 3;
}

由GCC和-O2编译，结果如下：

08048460 <div3>:
 8048460:   8b 4c 24 04             mov    ecx,DWORD PTR [esp+0x4]
 8048464:   ba 56 55 55 55          mov    edx,0x55555556
 8048469:   89 c8                   mov    eax,ecx
 804846b:   c1 f9 1f                sar    ecx,0x1f
 804846e:   f7 ea                   imul   edx
 8048470:   89 d0                   mov    eax,edx
 8048472:   29 c8                   sub    eax,ecx
 8048474:   c3                      ret 

我猜sub指令负责修正负数，因为如果参数为负数，它实际上是添加1，否则它就是一个NOP。

但是为什么会这样做呢？我一直试图用一个1字节版本的掩码来手工乘以较小的数字，但是我没有看到一个模式，我在任何地方都找不到任何解释。这似乎是一个神秘的魔术数字，其来源不明确的人，就像0x5f3759df一样。

有人能解释一下这背后的算法吗？

Answer 1

这是因为0x55555556真的是0x100000000 / 3，收起来了。

四舍五入很重要。由于0x100000000没有被3均分，所以在整个64位结果中会出现一个错误。如果该错误为负值，则在截断下32位后的结果将太低。通过舍入，误差是正数，所有的误差都在较低的32位，所以截断消除了它。