0x55555556が3ハックで分割するのはなぜですか？

Question

32ビットの数値を3で割るための（比較的）よく知られたハックがあります。実際の高価な分割を使用する代わりに、数字にマジックナンバー0x55555556を掛けることができます。結果の上位32ビットは、私たちが探しているものです。たとえば、次のCコード：GCCと-O2でコンパイルさ

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

、この中の結果：それは何ので

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ビットにすべて含まれているので、切り捨てで切り捨てられます。