为什么0x55555556除以3 hack工作？

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位中,因此截断将其擦除.