理系の理系による理系のためのブログ

理系以外の人も大歓迎です。

二進数 での 3の倍数判定法 を考えてみた。

昨夜、二進数での3の倍数判定法を考えながら寝ていたら、思いついたんです。
ということで、聞いてほしいです。

二進数については下の記事を見てください。

gakumonn-sugoi.hatenablog.jp

少し十進数と二進数の対比をしてみました。

01 00001
02 00010
03 00011
04 00100
05 00101
06 00110
07 00111
08 01000
09 01001
10 01010
11 01011
12 01100
13 01101
14 01110
15 01111
・・・
21 10101

じーっと見てみ、なにか気づきますか。
これだけでは難しいと思うので、十進数の3の倍数判定法について考えてみましょう。
十進数をざっくり言うと、1つ上の位(一の位に対する十の位)が10倍の価値を持っているという数字の記法です。

なので、123というのは、1×100+2×10+3×1ということです。
1×100+2×10+3×1=1×99+2×9+(1+2+3)
9は3の倍数で、1+2+3の部分が3の倍数なので123も3の倍数と言えます。

実際の数字で確かめましたが、一般化も容易にできますね。

それでは、二進数で考えてみましょう。
二進数は、下のような位になっていることがわかります。
・・・|16の位|8の位|4の位|2の位|1の位|・・・
さっきのざっくり説明だと、「1つ上の位(一の位に対する十の位)が2倍の価値を持っているという数字の記法」といったところでしょうか。
なので、10101₍₂₎は1×16 + 0×8 + 1×4 + 0×2 + 1×1(=21₍₁₀₎)ということです。
1の位、4の位、16の位、などは3で割って1余る数たちです。
一方、2の位、8の位、32の位、などの数たちは3で割ると2余ります。
2桁ずつ見れば「四進数」だからです。
そのため、以下のように「二進数における3の倍数判定法」を導出することができます。
「二進数で表されるある数において、一の位を含む一桁おきの各桁の和をA、十の位を含む一桁おきの各桁の和をBとおくと、A+2Bが3の倍数になれば、その数は3の倍数と言える」
「奇数桁目の各桁の和と偶数桁目の各桁の和の差が3の倍数」のほうがわかりやすいです。(by友人)

やっぱり、数学って楽しいですね。