为什么 0x55555556 除以 3 hack 有效？

Question

有一个（相对）众所周知的技巧，可以将 32 位数字除以三。不用实际昂贵的除法，可以将数字乘以幻数 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 位中，因此截断将其消除。

为什么 0x55555556 除以 3 hack 有效？

Why does the 0x55555556 divide by 3 hack work?

algorithm

bit-manipulation

arithmetic-expressions