10進数から2進数への変換
逆向きは、当てずっぽうになりやすい
前回は 2 進数を 10 進数にしました。今回は逆で、13 から 1101 を作ります。ところが逆向きは、急にやりにくくなります。
重みを大きいほうから当てはめる方法だと、「13 に 8 は入る、残り 5、4 も入る、残り 1」と進みます。悪くはありませんが、まず何ビット必要かを先に決めないと始まりません。13 なら 4 桁だと分かっても、1000000 を渡された瞬間に手が止まります。
桁数を先に決めなくてよい、もっと機械的な手順があります。
基数で割ると、いちばん右の桁が余りに出てくる
10 進数の 253 を 10 で割ると、商が 25 で余りが 3 です。余りは一の位そのもので、商は「一の位を捨てた残り」です。
2 進数でも同じです。2 で割った余りは必ず 0 か 1 になり、それが最下位の桁になります。商は最下位を捨てた残りなので、同じことをもう一度やれば次の桁が出ます。商が 0 になったら、もう桁はありません。
13 を追いかけると次のようになります。
プレーンテキスト
13 / 2 -> 商 6 余り 1
6 / 2 -> 商 3 余り 0
3 / 2 -> 商 1 余り 1
1 / 2 -> 商 0 余り 1この「割って余りを拾う」形は、数の変換に限った話ではありません。秒数を時分秒に崩すときも、中身は同じ手順です。
Python
sec = 3725
print(sec % 60) # 5 秒
print(sec // 60 % 60) # 2 分
print(sec // 3600) # 1 時間余りは、出てきた順と逆に並ぶ
最初に出た余りは最下位の桁で、最後に出た余りが最上位の桁です。拾った順のまま並べると 1011 になり、正解の 1101 と食い違います。
集め終わってから向きをそろえる、という一手間が必ず要ります。逆にすることを前提に集めるか、集めるたびに前へ差し込むか、どちらでも構いません。この一手間を忘れると、13 と 11 のように、たまたま左右対称な数だけ正解して、それ以外が全部ずれます。
0 を渡すと、1 回も割れない
0 は割る前から商が 0 です。「商が 0 になるまで繰り返す」という手順だと、繰り返しに一度も入らないので、余りが 1 つも集まりません。
欲しいのは 0 という 1 文字なのに、返るのは何も無い状態です。テストで最初に落ちるのはたいていここなので、手順の外で面倒を見てください。
割り算のほうにも注意が要ります。整数どうしの割り算が小数になる言語では、商が 6.5 のまま次へ進み、いつまでも 0 にならないことがあります。商は必ず整数に落としてください。
要件
- n は 0 以上の整数であると仮定して良い
- 組み込みの基数変換関数 (bin / toString(2) / Integer.toBinaryString) は使わない
- n が 0 のときは '0' を返すこと
入出力例
decToBin(13) → "1101"
decToBin(0) → "0"
decToBin(1) → "1"
decToBin(10) → "1010"
decToBin(255) → "11111111"
decToBin(1024) → "10000000000"ヒント
