へっぽこびんぼう野郎のnewbie日記

けろけーろ(´・ω・`)!

2進数小数を求めるときに2で掛けると求められるその理由について

地味にハマったので解説する。

 

まず2進数小数ではなくて、2進数整数を求めるときに、2で割って余りがどうとかするやつについて。

 

たとえば456という10進数の数字があって{→以下456(10)と書く}、

これを2進数に変換したいとき、

456 ÷ 2 = 228 … 0

228 ÷ 2 = 114 … 0

114 ÷ 2 = 57  … 0

57 ÷ 2 = 28 … 1

28 ÷ 2 = 14 … 0

14 ÷ 2 = 7 … 0

7 ÷ 2 = 3 … 1

3 ÷ 2 = 1 … 1

だから下から順にとって、456(10)は2進数では111001000(2)というやつだ。

 

やり方は書いてあっても、なんでそうなるのっていうのは本にはなかなか書かれていない。

情報系の話ではこういった「やり方」の話はよく出てくることだけど、

「なんでそうなるの?」とか証明の話は、割とないがしろにされている気がする。

 

自明だとでも言いたいのだろうが、

個人的に、「それ自明やから証明省くよ」って言われてもわかってる人って少なそうな気がしてならない。

 

そこで、これを証明してみた。

 

まず証明する前の前提知識として、剰余の計算について。

 

「3 ÷ 2 は 1 あまり 1」というのはみんなよく知っていると思うけれど、

それを普通の数式にするのは若干難しい。

3 ÷ 2 = 1 ・・・あれ?

となる。

この「あまり」というやつが結構曲者で、実際頭の中でやっていることは下のようなことである。

3 = 1 × 2 + 1

実のところ、ぼくたちは割り算なんてものはできない。

なんか割り算ができてる風に見えるのは、掛け算をして求めているだけのことである。

5 ÷ 3 = 1 … 2 

なんて計算できるのは、

「5か。3で割るのか、じゃあ3×1=3だから大丈夫そうだし、あまりは2だな。ほら、3越えなかった。だから5を3で割ったときは1あまり2だ」

というすごく速い思考か、

もしくは、

「5÷3は1あまり2だ」っていう長期記憶のおかげだ。

 

微分に対して積分がやたら難しいのも、これと殆ど似ている。

 

話を

3 = 1 × 2 + 1

のほうに戻すけれど、

この形、2進数の定義の文に似ているではないか。

これはまさにこう書き換えることができる。

 

3 = 1 × 2^1 + 1 × 2^0

2^1は、2の1乗という意味である。2^0は2の0乗で、2の0乗は当然だ。)

 

だから3(10)は、11(2)である。

 

では次に、7のときについて考えてみよう。

7を、2で割ると、このようになる。

7 = 3 × 2 + 1

では、3を先ほどと同じように2で割ってみよう。

3 = 1 × 2 + 1

これを組み合わせると、7は

7 = (1 × 2 + 1) × 2 + 1 

 と表現できる。次に括弧の中身を展開しよう。

展開すると、

7 = (1 × 2 × 2) + (1 × 2) + 1

となり、これを整理すると、

7 = 2 × 2 + 1 × 2 + 1

 

7 = 2^2 + 1 × 2^1 + 2^0

 

7 = 1 × 2^2 + 1 × 2^1 + 1 × 2^0 

 となる。区切りがわかりにくいので、赤と青をつけてみた。

したがって、7(10)111(2)である。

 

つまり、ある10進数の数nを、2で次々に割って、そのあまりを出すということは、

 2進数の定義に忠実に従って、10進数から2進数に変換しているということと、

 

全く意味が同じなのである。

 

ある数nについての例を示そう。

n2で割ると

 n = m × 2 + rest[m]

となる。restは「mで割ったときのあまり」という意味だ。restは当然、1、もしくは、0である。(2で割っているんだから!)

ここで、mが2以上ならば、mを更に2で割ることができる。

n = ( l × 2 + rest[l]) × 2 + rest[m]

(ちなみにlは1ではなくてエルだ)

で、これは

n = l × 2^2 + rest[l] × 2^1 + rest[m] × 2^0

と書き換えることができる。

ここで、lが2よりも大きければ、またさらに

n = k × 2^3 + rest[k] × 2^2 + rest[l] × 2^1 + rest[m] × 2^0

となっていくことがわかるだろう。

 

あとはこれを繰り返していくだけだ。

 

α進数のときは、この「2進数」の部分を「α進数」に置き換えて考えればいいわけだから、

n = k × α^3 + rest[k] × α^2 + rest[l] × α^1 + rest[m] × α^0

となる。

従って8進数を求めたい場合には、8で割りまくればいい。

 

では、次に、小数の2進数を求める際には、どうすればよいかと言う話だ。

10進数の0.48を2進数にしたいときは、

0.48 × 2 = 0.96 → 0

0.96 × 2 = 1.92 → 1

0.92 × 2 = 1.84 → 1

0.84 × 2 → 1.68 → 1

0.68 × 2 → 1.36 → 1 

だから、0.01111…

ってやつだ。

 

「さっきは割ったんだから、今度は掛けたらいいんでしょ。1/2のあまりじゃん。楽勝すぎ」ではない。

1/2のあまりは、1/2進数だ。

 

逆から考えると、割と難しくて詰むので、別の概念で考えることにする。

 

まず、2進数の小数部分は次のように表せる。

勘違いしてほしくないのだが、次に書くものは、方程式ではなくて、恒等式である。

 

「10進数のfは、2進数小数ではこう表せますよ」

「2進数小数でこう表すものは10進数ではfですよ」

という両方の意味を示す文章を、恒等式にすると

 

f = 0 × 2^0 + a × 2^(-1) + b × 2^(-2) + c × 2^(-3) + …

 

となる。

 

それで、繰り返すが、これは恒等式で、

ぼくたちが求めたいのは、a、b、c、…の部分である。

だからその後、左辺の値がどのようになろうと、知ったことではない。

 

方程式ではないので、「a = すごく複雑な式」の形にしなくても求められるのだ。

 

両辺に2を掛けてみると

2f = a + b × 2^(-1) + c × 2^(-2) + …

 となる。

すごく単純だが、ここでaが求まった。

当たり前だが、aは、10進数2fの2進数の整数部分のことである。

 

なぜならこの恒等式の意味は、

「10進数の2fは、2進数で次のように表せますよ」

「2進数でこのように表したものは10進数では2fですよ」という意味だからだ。

 

で、aは求まったので取り除いて考えよう。

 2f - a = b × 2^(-1) + c × 2^(-2) + …

 で、また両辺に2を掛けると、

 4f - 2a = b + c × 2^(-1) + … 

 となって、bが求まった。

 

とまぁ、

このようにして2をかけていくと求められることがおわかりいただけただろうか。

 

僕が理解に苦労した理由まとめ。

  • 剰余の理解不足
  • 恒等式の理解不足
  • 逆からトライしてたこと

あたらしい発見

  • 数学って、ひょっとして全部自明なものなのかもしれないね