2^nの剰余をビット演算化します
恐らく速度差は10倍以上
y = x & 1; // x % 2
y = x & 3; // x % 4
y = x & 7; // x % 8
y = x & 15; // x % 16
どうしてこうなるかまず10進で考えてみましょう。
123456789 % 100
を計算してみましょう。
わざわざ割り算をする人はいませんよね？
下から二桁を取って89でおしまいです。
10進数において10のn乗の剰余を計算する時は、
下からn桁だけを取ればいいことになります。
コンピューターでも同じ事ができます。
コンピューターの場合は0と1の2進なので、
10が2に、100が4に該当します。
つまり2のn乗、
x % 2
x % 4
x % 8
...
x % 1024
などの時に同じテクニックが使えます。
では、下からn桁を取り出したいときにはどうすればいいでしょうか。
これも便利なものがあります。
& (アンド)演算子です。
この演算子を使うと、ビットにマスクをかけることができます。
例えば
00001111 & 00111100
は、1の重なった部分 00001100 を返します。
これを使うと下からn桁の部分を取り出すことができます。
下から3桁を取り出したい場合は 00000111 で
マスクをかけてやればいい事になります。
つまり、
00000100の剰余がほしい場合は、00000011でマスクをかける。
00001000の剰余がほしい場合は、00000111でマスクをかける。
00010000の剰余がほしい場合は、00001111でマスクをかける。
00100000の剰余がほしい場合は、00011111でマスクをかける。
これらを10進に直してみましょう。
4の剰余がほしい場合は、3でマスクをかける。
8の剰余がほしい場合は、7でマスクをかける。
16の剰余がほしい場合は、15でマスクをかける。
32の剰余がほしい場合は、31でマスクをかける。
もう気付いた方も多いのではないのでしょうか。
そう、 __2のn乗 の剰余がほしい場合は、2のn乗 - 1 でマスクをかけてやればいい__のです。
ですので、
x % 2 → x & 1
x % 4 → x & 3
x % 8 → x & 7
x % 16 → x & 15
と、書き直す事ができるのです。