Binary to Decimal
0と1の文字だけを使って、0以上の数値を2進数で表した文字列sが与えられます。その数値を通常の整数として返してください。この文字列には先頭のゼロはありません。ただし、0の場合は例外で、1文字の0で表されます。
関数
- sstring
- 数の2進数の各桁
- 戻り値integer
- s の値を整数として
制約
1 ≤ s.length ≤ 31sは0と1のみを含みます。sは、sが"0"でない限り、1から始まります。- 組み込みの基数変換を呼び出すのではなく、自分で数字を読み取りましょう。
例
- 入力
- s = "1101"
- 出力
- 13
- 説明
- 右から読むと、各桁の値は1、2、4、8です。
1101では、8、4、1の位が1なので、8 + 4 + 1 = 13です。
- 入力
- s = "0"
- 出力
- 0
- 説明
- 単独の
0にはどの位にも1がないため、その値は0です。
- 入力
- s = "10000000"
- 出力
- 128
- 説明
- 唯一の 1 の右側には 0 が 7 個あるので、
2^7 = 128の位にあります。
提出時に隠しテスト+16件
発展問題
同じループを使って、2進数から16進数までの任意の基数で書かれた数を読み取れますか？その場合、文字 a から f は数字の 10 から 15 を表します。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
10進数では、
347の各桁の値は300、40、7です。2進数では、各桁の値はいくつでしょうか？最も右の2進数の桁の値は1で、左に1桁進むごとに位の値は2倍になります：1、2、4、8と続きます。この数は、1がある位の値を合計したものです。
累乗を計算せずに済みます。左から読み、各桁について、現在の値を2倍してその桁を加えます。最後の桁を処理した後の値が答えです。
解説
各2進数の桁は、右端からどれだけ離れているかによって決まる2の累乗を表します。右からそれらの累乗を足し合わせることも、文字列を左から読み取り、各ステップで値を2倍することもできます。2倍するループでは累乗を計算することはなく、10の代わりに2を使う点を除けば、10進数のテキストを読み取るときと同じループです。
右から位の値を加える
考え方
最も右の桁の値は1、その左隣は2、次は4、8というように、左へ進むごとに倍になります。この数は、1がある桁の重みを合計したものです。したがって、最後の文字から最初の文字へと進み、現在の桁の重みをpowerに保持し、桁が1のときに加算します。
1101の場合、1（1を加算）、0（2を飛ばす）、1（4を加算）、1（8を加算）の順に処理し、合計は13になります。各桁を一度ずつ処理するため、ループの実行時間はO(n)で、メモリは数値2つ分です。
powerの大きさに注意してください。31桁の文字列では、最後の桁で2^30に達し、その後さらに一度倍にして2^31になりますが、これは符号付き32ビット整数には収まりません。powerを64ビット変数に保持するか、最後の桁の後は倍にするのをやめてください。
アルゴリズム
total = 0とpower = 1を設定します。- 文字列を最後の文字から最初の文字までたどります。
- 文字が
1の場合、powerをtotalに加えます。 - 1つ左に移動する前に、
powerを2倍にします。 totalを返します。
def toDecimal(s):
total = 0
power = 1 # the place value of the rightmost digit
for i in range(len(s) - 1, -1, -1):
if s[i] == "1":
total += power
power *= 2
return total左から2倍して足す
考え方
文字列を左から読み、これまでに読んだ数字が表す数を保持するためにvalueを使います。2進数の桁をもう1つ追加すると、それ以前の各桁は左に1つ移動し、その値が2倍になり、新しい桁が加算されます。つまり、各ステップはvalue = value * 2 + digitです。
1101の場合、valueは1になり、次に1 * 2 + 1 = 3、次に3 * 2 + 0 = 6、最後に6 * 2 + 1 = 13となります。文字列の各接頭辞は、より小さな2進数であり、ループは常にその数を保持するので、最後の桁を読み終えると、全体の値が保持されています。
値が最終的な答えを超えることはないため、31桁の文字列なら2^31-1の範囲内に収まり、32ビット整数で十分です。桁の値は、文字コードから'0'のコードを引いたもので、これにより'1'は1に、'0'は0になります。これは、任意の基数でテキストから数値を解析する標準的な方法です。
アルゴリズム
value = 0に設定します。- 左から右へ各文字について、
'0'のコードを引いて数字に変換します。 value = value * 2 + digitに設定します。valueを返します。
def toDecimal(s):
value = 0
for ch in s:
# Shift the digits read so far one place left, then add the new one.
value = value * 2 + (ord(ch) - ord("0"))
return value
落とし穴と境界ケース
多くの誤答は、走査する方向や桁の型が原因です。
- 最も左の桁の位の値を1にしてしまう。位の値は右端から始まるため、最後の文字から走査するか、左から倍にしていくループを使います。
- 数字ではなく文字を加算してしまう。多くの言語では、
'1'は数値の49なので、value * 2 + '1'は大きくなりすぎます。まず'0'を引きます。 - 位の値がオーバーフローする。31桁目の後に
powerを2倍にすると、2^31になり、32ビット整数では値が折り返すか、クラッシュします。 - 浮動小数点のべき乗関数で各位の値を計算してしまう。C、C++、Javaでは、
pow(2, k)はdoubleを返すため、結果を整数に変換し直す必要があります。
よくある質問4
2進数を10進数に変換するにはどうすればよいですか？
各桁に位の値を割り当てます。右端は1、その左は2、4、8と続きます。1である桁の位の値を足します。1101の場合は、8 + 4 + 1 = 13です。
値を2倍にすると、なぜうまくいくのでしょうか？
2進数の末尾に数字をもう1桁書き加えると、それまでの各桁は1つ左に移動し、各桁の位の値は右隣の位の2倍になります。そのため、元の値は2倍になり、新しい桁の値として0または1が加わります。最初の桁から最後の桁までこれを繰り返すと、数全体が作られます。
2進数を10進数に変換する時間計算量はどれくらいですか？
どちらのループもn文字それぞれを1回ずつ処理するため、実行時間はO(n)です。保持する数値は1つか2つだけなので、追加の領域はO(1)です。31文字の文字列の場合、31ステップです。
ビットシフトを使って2進数を10進数に変換できますか？
はい。value << 1は値を2倍にし、| digitは最下位ビットを設定するため、value = (value << 1) | digitはvalue * 2 + digitと同じ処理をします。シフトを使う形式ではビットを移動していることが明確になりますが、算術演算を使う形式は2以外の基数でも機能します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def toDecimal(s):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "1101"
期待値
13