メモ書き程度に書いておく。
m (mod n)を計算するときにC言語では
m % n
と書く。しかし、nが2の累乗であるときはこれをAND演算子を用いて
m & (n-1)
でも同じ結果が得られる。
これはn=2kのとき、n-1は2進数でk-1桁の1で埋められたビット列となることによります。
たとえばn=25=32=(100000)2の場合、n-1=(11111)2 となります。
もちろんこの値と論理積をとれば、0〜25-1までの数値しか出てきません。
そして、2進数で6桁目以外が0で埋められているので、6桁目以降が0で埋められている2進数(たとえば(101100000)2)を割ったときは割り切れるということになります。
つまり、下位5ビットの値がそのまま剰余と一致するので、n-1とAND演算をするだけでモジュラ演算と同じ結果が出てきます。
うーん、理屈を言ってしまうと元も子もない感じですが、意外と知らないとぱっと思いつかないかなぁと・・・。
「この程度なら思いつく」と言われたら、「私の修行不足です。いえ、私のIQの問題です」と答えるほかないですね。
