algorithm - 为什么0x55555556除以3 hack起作用？

有一种（相对来说）众所周知的方法是把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。
有人能解释一下这背后的算术吗？

最佳答案

因为0x55555556是真的0x100000000 / 3，四舍五入。
舍入很重要。因为0x100000000不能被3等分，所以在完整的64位结果中会有一个错误。如果该错误为负，则截断较低32位后的结果将过低。通过四舍五入，误差是正的，而且都在32位以下，所以截断会消除它。