10進数→2進数変換のアルゴリズムで出力を逆に読む理由

概要

手計算で10進数を2進数に手計算で変換するアルゴリズムとして，筆算を連鎖したあと，剰余を逆順に並べて出力とするものがありますが，なぜ逆順でうまくいくのか考えたことがなかったので，メモがてらまとめてみます．

概要としては，

  • ビットマスクとビットシフト
  • 数式

の両面から納得することができました．

アルゴリズム

10進数表記の数 aを2進数表記するとして，この記事で対象にするアルゴリズムは以下のとおりです．

  1. aを2で割り，剰余と商a'を記録する
  2. aに a' を代入し， aが2を下回るまで，これを繰り返す
  3. 剰余を逆順に左から並べる

a=29 の場合を例に図解すると以下のようになります．

f:id:je6bmq:20190507204803p:plain
2進数変換の例（29の場合）

Python（3.6.2）のコード例は次のようになります．（実行例）

bits_list = []
while a > 0:
    bits_list.append(a % 2)
    a = a // 2

bits_list.reverse()

この記事では，割り算の方向に対して出力の読み上げが逆方向に行われる理由について考えていきます．

準備

2進数で n桁の数は，式のように表されます．

\sum_{i=0}^{n-1} d_i \times 2^i

d_i は， i番目の桁の値を表し， d_i=0または d_i=1です． 例えば， a=29の場合は d_0=1， d_1=0， d_2=1， d_3=1， d_4=1となります．

もちろん，2進数，10進数は同じ数の違う表現というだけなので，

2 \times 10^1 + 9 \times 10^0 = 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0

が成り立ちます．
（左辺：10進数表現，右辺：2進数表現）

ビットマスクとビットシフト

このアルゴリズムの要点は，2で割った場合の商と剰余を使い続けることにあります．ここで，2で割ることと2で割った場合の剰余をビット演算で表現することを考えます． このとき，2で割ることは 右に1bitシフトすること に，2で割った場合の剰余は 0b1との論理積 に対応します．

2で割った場合の剰余について

右シフトで商が得られることを用いると，ある数bについて2で割った剰余は a - (a>>1)<<1で求められます．
（正の数において，シフト時に足りないbitは0が補われるため）
ここで，最下桁以外の各桁の値はaと(a>>1)<<1の間で必ず等しくなるので，結果として0b1との論理積と同義です．

剰余を求めて記録し，2で割る操作は，まるで だるま落としのように，最下層の桁を取り出し，桁を落とす操作に対応します． したがって，最下桁が最初に取り出され，最上位桁が最後まで残るため，逆順に出力されます．

f:id:je6bmq:20190507215330p:plain
最下桁から順番に取り出される

ビット演算を用いて前述のコードを書き直すと，次のようになります．（実行例）

bits_list = []
while a > 0:
    bits_list.append(a & 0x1)
    a = a >> 1

bits_list.reverse()

数式

2で割った場合の商と剰余を求めることは，数式から2をくくりだして，2 \times 商 + 剰余 の形式にすることと同義です． そこで，

\sum_{i=0}^{n-1} d_i \times 2^i

を変形すると，

=d_{n-1} \times 2^{n-1} + d_{n-2} \times 2^{n-2} + \cdots + d_1 \times 2^1 + d_0 \times 2^0 =2 \times \left(d_{n-1} \times 2^{n-2} + d_{n-2} \times 2^{n-3} + \cdots + d_1 \times 2^0 \right) + d_0 \times 2^0

となります．ここで，剰余 d_0 \times 2^0を無視して（アルゴリズム上は記録することになりますが）， この商の部分に着目すると，再び2でくくることができます． したがって， =2 \times \left( 2 \times \left (d_{n-1} \times 2^{n-3} + d_{n-2} \times 2^{n-4} + \cdots + d_2 \times 2^0 \right)+ d_1 \times 2^0 \right) + d_0 \times 2^0

となります．

このように，剰余の項を無視して2でくくりだす，を繰り返すことができ，これが 最下桁の値から 剰余として分離することに相当するため，出力を逆順に読むことになります．

まとめ

10進数→2進数変換アルゴリズムの出力を逆順に読み上げる理由について，

意味付けを行いました．

補足

個人的には再帰で書くほうが好みです．（実行例）

# start
def convert_to_bin(n, acc_list=[]):
    return reversed(acc_list) if n == 0 else convert_to_bin(n // 2, acc_list + [n % 2]) 
# end

a = 29 
result = "".join([str(b) for b in convert_to_bin(a)])

print(result)