読者です 読者をやめる 読者になる 読者になる

モジュラ演算とAND演算子

プログラミング全般

メモ書き程度に書いておく。



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の問題です」と答えるほかないですね。

広告を非表示にする