10進数を2進数に変換する
日常的に利用する10進数（decimal numbers）を、コンピュータが扱う2進数（binary numbers）に変換する方法を理解することは、コンピュータサイエンスの基礎として非常に重要です。2進数では、各桁の位置が2のある累乗を示しています。つまり、2進数は「与えられた数を表すために、どの2の累乗を足し合わせればよいか」を示す仕組みと言えます。
10進数表記 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 | 合計 |
114 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 114 = 64 + 32 + 16 + 2 |
12 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 12 = 8 + 4 |
13 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 13 = 8 + 4 + 1 |
2進数表記において、
1はその桁に対応する2の累乗が合計に含まれることを示し、0は含まれないことを示します。2進数が持つ大きな特徴は、簡潔でありながら表現が一意である点です。💡
どの数も、重複しない2の累乗の合計で表される唯一の2進数表現を持ちます。
右端のビットを見つける
まず、2進数で右端のビットを求める方法を考えましょう。10進数の最後の桁を取り出す方法としては、よく10で割った余り（% 10）を使いますが、2進数の右端ビットを取り出すには2で割った余り（% 2）を使います。したがって、奇数の場合は右端のビットが1に、偶数の場合は0になります。
例えば:
- 114の場合、右端のビットは0（114 % 2 = 0）です。
- 13の場合、右端のビットは1（13 % 2 = 1）です。
2進数を右にシフトする
右端のビットを取り出した後は、数全体を右に1桁シフトします。これは、整数の2による切り捨て除算（/ 2、またはPythonでは// 2）に相当します。これによって一番右のビットが取り除かれ、次のビットが新たな右端になります。
- 114（2進数表記では1110010₂）を右にシフトすると111001₂になります。これは10進数の57（114 / 2）に相当します。
- 13（2進数表記では1101₂）を右にシフトすると110₂になります。これは10進数の6（13 / 2）に相当します。
変換アルゴリズム
右端のビットを求める操作と、数を右にシフトする操作を組み合わせることで、10進数を2進数に変換するシンプルなアルゴリズムを作ることができます:
- 2進数表記を格納するための空の文字列を用意する。
- 数が0より大きい間、以下を行う:
- 2で割った余りを求めて右端ビットを取得する。
- そのビットを、構築中の2進数の文字列の先頭に追加する。
- 数を2で割って（切り捨て）右にシフトする。
- 最終的に2進数の文字列が空でなければそれを返し、空なら0を返す。
このアルゴリズムを使えば、どんな10進数でも重複のない2の累乗の合計で表される一意の2進数へ変換できます。
最小限の実装
b, d = '101001101', 0 # 2進数と10進数
power = 1 # 現在の2の累乗(1, 2, 4, 8, 16, ...)
for bi in b[::-1]: # 下位ビットから上位ビットへループ
d += int(bi) * power
power *= 2
print(d)b, d = '', 5234 # 2進数と10進数
while d > 0: # まだビットが残っている間
b = str(d % 2) + b # 求めたビットを文字列の左側に挿入
d //= 2 # 数を右にシフト(2で割る)
print(b if b != '' else 0)