为什么0x5555556除以3的破解有效?

有一种(相对)众所周知的将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 .

有人能解释一下这背后的算术吗?