Decimal to Binary
非負整数 n が与えられます。先頭にゼロを付けず、0 と 1 からなる文字列として、その2進表現を返してください。答えが 0 で始まる唯一の数はゼロ自体で、"0" と表記します。
関数
- ninteger
- 変換する数値
- 戻り値string
- n の 2 進数の桁を文字列として
制約
0 ≤ n ≤ 231-1- 組み込みの基数変換を呼び出すのではなく、自分で文字列を作成します。
例
- 入力
- n = 13
- 出力
- "1101"
- 説明
13 = 8 + 4 + 1です。8、4、2、1の位にはそれぞれ1、1、0、1が入り、1101と読みます。
- 入力
- n = 0
- 出力
- "0"
- 説明
- ゼロにはセットされたビットがありませんが、答えにはそれでも1桁必要なので、空文字列ではなく
"0"になります。
- 入力
- n = 64
- 出力
- "1000000"
- 説明
64は2^6です。64の位に1が1つあり、その後に32の位から1の位までの6つの0が続きます。
提出時に隠しテスト+16件
発展問題
同じループを使って、9より大きい桁に文字 a から f を使い、n を2から16までの任意の基数に変換できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ほかの桁を知らなくてもわかる、
nの2進数の桁はどれですか？ 奇数と偶数について考えてみましょう。最後の桁は
n % 2です。nを 2 で割り、余りを切り捨てると、その桁が取り除かれ、次の桁が最後の位置に移動します。繰り返し：
n % 2を記録し、次にnを半分にします。nが0になるまで続けます。桁は最下位から最上位の順に得られるため、最後に逆順にします。0には専用の答えが必要です。
解説
2進数は2の累乗の和であり、各桁はその累乗が和に含まれるかどうかを示します。上の位から2の累乗を引いて各桁を決めることも、2で繰り返し割った余りとして下の位から読み取ることもできます。除算ループは標準的な方法です。最初に最大の累乗を見つける必要はなく、どの基数でも同じように機能します。
上から2の累乗を引く
考え方
手作業で変換する方法は次のとおりです。n に収まる最大の2の累乗を見つけます。それが最初の桁である 1 です。次に、累乗を1つずつ小さくしていきます。その累乗が残りの値にまだ収まるなら 1 と書いてその値を引き、そうでなければ 0 と書きます。
13 の場合、最大の累乗は 8 です。1と書き、5 を残します。次に 4 は収まるので（1、1 を残す）、2 は収まらず（0）、1 は収まります（1）。桁を読むと 1101 になります。最初の桁は常に1なので、先頭に0が付くことはありません。
最大の累乗を見つけるには注意が必要です。power が n を超えるまで倍にすると、n ≥ 2^30 のとき次の累乗が 2^31 となるため、32ビット整数でオーバーフローします。power ≤ n / 2 の間だけ倍にすれば、n を超えることなく正しい累乗で止まります。31ビットの数値では31ステップかかり、これは O(log n) です。
アルゴリズム
- もし
nが0なら、"0"を返します。 powerを1に設定し、power ≤ n / 2である間、2倍にします。power > 0である間：n ≥ powerなら、1を追加してnからpowerを引きます。そうでなければ、0を追加します。powerを半分にして、繰り返します。- 追加した桁を返します。
def toBinary(n):
if n == 0:
return "0"
# Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
power = 1
while power <= n // 2:
power *= 2
bits = []
while power > 0:
if n >= power:
bits.append("1")
n -= power
else:
bits.append("0")
power //= 2
return "".join(bits)2による繰り返しの除算
考え方
nの最後の2進数の桁は、nが奇数かどうかを示します。これはn % 2です。2で割って余りを捨てると、すべての桁が1つ右に移動するため、次の桁が最後の桁になります。何も残らなくなるまで繰り返せば、最下位の桁から順にすべての桁を集められます。
13の場合：13の余りは1、6の余りは0、3の余りは1、1の余りは1で、その後、数は0になります。余りを順に並べると1, 0, 1, 1となり、逆順にすると1101です。数が0になるとループが停止するため、出力される最上位の桁は常に1で、先頭に0が付きません。0そのものはループに入らないため、個別に確認する必要があります。
各ステップで数は半分になるため、31ビットの値には31ステップかかり、時間計算量はO(log n)、桁の文字列に必要な空間はO(log n)です。
アルゴリズム
nが0の場合、"0"を返します。n > 0の間、n % 2を桁として追加し、nを切り捨てたn / 2に設定します。- 桁を逆順にします。最小位から順に得られたためです。
- それらを文字列として返します。
def toBinary(n):
if n == 0:
return "0"
bits = []
while n > 0:
# The remainder is the lowest bit that is left.
bits.append(str(n % 2))
n //= 2
# The bits came out lowest first, so turn them around.
bits.reverse()
return "".join(bits)
落とし穴と境界ケース
ループは短く、間違った回答のほとんどはその両端に起因します。
0に対して空文字列を返す。ゼロの場合、除算ループは実行されないため、最初に確認してください。- 逆順にするのを忘れる。余りは最下位の桁から順に得られるため、
6は110ではなく011になります。 - JavaScript、Lua、PHPなど、
/が小数を返す言語で/を使う。13 / 2は6になる必要があるため、切り捨てるか整数除算を使ってください。 nを超えて倍にし、最大の累乗を求める。n = 2^31-1の場合、次の累乗である2^31は32ビット整数に収まりません。- Cで確保する領域が少なすぎる。31ビットの数には31文字に加えて、終端文字
'\0'が必要です。
よくある質問4
10進数を2進数に変換するにはどうすればよいですか？
数を2で繰り返し割り、そのたびに余りを書き留めます。数が0になるまで続けます。余りを最後のものから最初のものへと読みます。13の場合、余りは1、0、1、1なので、13の2進数表記は1101です。
余りを逆順に読むのはなぜですか？
最初の2による割り算で、その数が奇数かどうかがわかります。これは2進数の最後の桁です。その後の各割り算で、左隣の桁が順に明らかになります。つまり、余りは最も下位の桁から順に得られるため、通常の表記で数を書くには、それらを逆順にします。
10進数を2進数に変換する時間計算量はどれくらいですか？
各ステップで数値が半分になるため、ループは2進数の各桁につき1回、つまり約log2(n)回実行されます。これは時間計算量がO(log n)であり、答えの文字列に必要な空間計算量もO(log n)です。32ビット整数の場合、ステップ数は最大31回です。
割り算ではなくビット演算を使って、2進数に変換できますか？
はい。n & 1は最下位ビットを取得し、n >> 1はそれを取り除きます。これは非負の数では、n % 2とn / 2と同じです。ループと反転処理はそのままです。除算のほうが説明しやすい一方、シフトを使う方法は低水準コードでよく使われます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def toBinary(n):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
n = 13
期待値
"1101"