昔、あるプログラムのソースを読んでいて、ハッシュの大きさとして 128 が使われていました。「2 の累乗を使うとは何事か！」と思い、二度とその人の書いたコードは読まなくなりました。
2 の累乗で割って余りを取ると、ほとんど計算しないことは明らかですね。上のビットをマスクして、全部 0 にしているだけですから。たとえば、0x01020304 を 256 で割った余りは 0x04 です。
一方、「2 の累乗 - 1」で割って余りを取る計算も、実はほとんど計算になってないのを知っている人は、あまりいないでしょう。たとえば、0x01020304 を 255 で割った余りは、0x0a とすぐ計算できない人がほとんどでしょうね。
この問題は、実は「3で割り切れるか」という日常的によく使う計算と本質的には同じことです。
3で割り切れるか
以下、10進数の話です。
2 で割り切れるか判断するときは、下一桁が偶数か奇数かで判断します。当たり前ですね。
5 で割り切れるか判断するときも、下一桁が 0 あるいは 5 か、それ以外かで判断します。ええ、当たり前です。
3 で割り切れるか判断するときは、どうしますか？ 最近の若い人は、数学が苦手らしいので、知らない人もいるかもしれませんが、次のようにやります。それぞれの桁を足した数が、3 で割り切れるか確かめるのです。
たとえば 123 だと、1 + 2 + 3 = 6 ですから、3 で割り切れます。256 は 2 + 5 + 6 = 13 ですから、割り切れません。13 が 3 で割り切れるか分らなければ、さらに 1 + 3 = 4 を計算し、割り切れないことを確かめましょう。
実は、これは 9 で割り切れるかという問題のサブセットになっています。各桁を足すと、9で割った余りになるのです。余りが 9 であれば、9 で割り切れ、それ以外では割り切れないと分ります。
たとえば、234 は、2 + 3 + 4 = 9 なので、9 で割り切れます。456 は、4 + 5 + 6 = 15 で、さらに 1 + 5 = 6 なので、9 では割り切れません。
9 で割り切れる部分は、3 でも割り切れるはずです。ですから、9 で割った余りの部分だけを見れば、3 で割り切れるか分る訳です。
9 で割ることが特殊であるのは、9 が進数である 10 から 1 を引いた数だからです。
2^n - 1 で割った余り
2^n - 1 で割った余りを計算する方法を考えましょう。分りやすくするために、n = 8 とし、2^n - 1 = 255 で話を進めていきます。
256 を x と置くと、任意のバイト列は、以下のように表現できます。
F(x) = c0 × x^0 + c1 × x^1 + c2 × x^2 + c3 × x^3 ....
F は適当に付けた名前なので、気にしないで下さい。
抽象化されるとよく分らない人のために、例として 0x01020304 を挙げておきます。
0x01020304 = 0x01 × 256^3 + 0x02 × 256^2 + 0x03 × 256^1 + 0x04 × 256^0
= 0x01 × x^3 + 0x02 × x^2 + 0x04 × x + 0x04
さて、「剰余の定理」を覚えていますか？
P(x) を (x - a) で割ったときの商が Q(x)、余りが R だっとしましょう。つまりこうです。
P(x) = (x - a) × Q(x) + R
R を簡単に計算するには、x に a を代入すればよいことは明らかです。
P(a) = (a - a) × Q(x) + R = R
F(x) を x - 1 で割った余りを取るにはどうしますか？ そう、x = 1 を代入すればいいですね。
F(x) = c0 × x^0 + c1 × x^1 + c2 × x^2 + c3 × x^3 ....
F(1) = c0 × 1^0 + c1 × 1^1 + c2 × 1^2 + c3 × 1^3 ....
= c0 + c1 + c2 + c3 ....
我々が考えている例では、x は256 でした。(x - 1) は、255 です。つまり、ある数値を 255 で割って余りを取るには、それぞれのバイトを足すだけです。
だから、0x01020304 を 255 で割った余りは、0x01 + 0x02 + 0x03 + 0x04 = 0x0a のように、簡単に計算できる訳です。
一般解
進数の数や桁数は任意ですよ！
