あどけない話

インターネットに関する技術的な話など

余り

昔、あるプログラムのソースを読んでいて、ハッシュの大きさとして 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 のように、簡単に計算できる訳です。

一般解

進数の数や桁数は任意ですよ!