私の答えは次の場所にあります。
私はここで少し得意ではないので、この特定の最適化がどのように機能するかを理解しようとしています。
回答で述べたように、gcc は整数除算を 7 で最適化して次のようにします。
mov edx, -1840700269
mov eax, edi
imul edx
lea eax, [rdx+rdi]
sar eax, 2
sar edi, 31
sub eax, edi
これは次のように C に変換されます。
int32_t divideBySeven(int32_t num) {
int32_t temp = ((int64_t)num * -015555555555) >> 32;
temp = (temp + num) >> 2;
return (temp - (num >> 31));
}
最初の部分を見てみましょう。
int32_t temp = ((int64_t)num * -015555555555) >> 32;
なぜこの数字？
では、2^64 を 7 で割り、何が飛び出すか見てみましょう。
2^64 / 7 = 2635249153387078802.28571428571428571429
ぐちゃぐちゃに見えますが、これを 8 進数に変換するとどうなるでしょうか。
0222222222222222222222.22222222222222222222222
これは非常によく繰り返されるパターンであり、偶然ではありません。つまり、7 は であることを覚えており0b111、99 で割ると底が 10 の繰り返しパターンが得られる傾向があることがわかっています。したがって、7 で割ると底が 8 の繰り返しパターンが得られることは理にかなっています。
では、私たちの番号はどこから来るのでしょうか?
(int32_t)-1840700269と同じです(uint_32t)2454267027
* 7 = 17179869189
そして最後に 17179869184 は2^34
つまり、17179869189 は 7 2^34 の最も近い倍数です。別の言い方をすれば、2454267027 は に収まる最大の数で、uint32_t7 を掛けると 2 の累乗に非常に近くなります。
この数字は 8 進数で何ですか?
0222222222223
何でこれが大切ですか？さて、7 で割りたいと思います。この数は 2^34/7 です... おおよそです。したがって、それを掛けてから 34 回左シフトすると、正確な数に非常に近い数が得られるはずです。
最後の 2 行は、近似誤差を修正するように設計されているように見えます。
おそらく、この分野でもう少し知識や専門知識を持っている人がこれに参加することができます.
>>> magic = 2454267027
>>> def div7(a):
... if (int(magic * a >> 34) != a // 7):
... return 0
... return 1
...
>>> for a in xrange(2**31, 2**32):
... if (not div7(a)):
... print "%s fails" % a
...
失敗は 3435973841 で始まります。これは、おかしなことに 0b11001100110011001100110011010001 です。
近似が失敗する理由を分類することは私には少し難しいことであり、パッチがそれを修正する理由も同様です。私がここに書いたこと以外に、魔法がどのように機能するか知っている人はいますか?