ITパスポート 2024年 問85

2進文字列を整数に変換する関数の穴埋め問題【ITパスポート 解説】

正解の理由

解法ステップ

1. 問題のループは「末尾から i 番目」を扱っている点を確認します。末尾は最下位ビット（2^0の位置）です。
2. したがって i = 1 のとき重みは $2^0$、i = 2 のとき $2^1$…となるので、重みは $2^{i-1}$（これが a に入る式）です。
3. 各ビットが持つ値は「ビット × 重み」です。合計はこれらを足し合わせて得られます。よって更新式は integerNum ← integerNum + digitNum × exponent（これが b に入る式）です。
4. 以上から a に $2^{i-1}$、b に integerNum + digitNum × exponent を入れる選択肢が正しいと分かります（エ）。

• 長さ3。i=1: 末尾ビット=0、exponent=$2^0=1$ → integerNum += 0×1 = 0
• i=2: 末尾から2番目=0、exponent=$2^1=2$ → integerNum += 0×2 = 0
• i=3: 末尾から3番目=1、exponent=$2^2=4$ → integerNum += 1×4 = 4
  結果は 4（期待通り）。

選択肢別の誤答解説

• ア：a が $(2^i)-1$（$2^i-1$）となっており、これは重みではありません。たとえば i=1 で $2^1-1=1$ だが i=2 で $2^2-1=3$ となり、正しい重み $2^{i-1}$ と一致しません。さらに b が integerNum × digitNum × exponent で、これは「累積値を次のステップでさらに掛ける」式になり誤りです。合計を求めるべきところを掛け算してしまいます。
• イ：a が $(2^i)-1$ で上と同じく重みがズレています。b は合計を足す形なので部分的には正しいが、exponent が間違っているため誤りです。
• ウ：a は正しく $2^{i-1}$ ですが、b が integerNum × digitNum × exponent になっており、これでは「これまでの合計に現在のビットの価値を足す」処理になりません。たとえば最初のビットで integerNum が 0 であれば常に 0 のままになりやすく、正しい変換になりません。

よくある誤解

1. 「指数（exponent）を $2^i$ にすればよい」と考える誤り
   • ループが i を 1 から始め、末尾（最下位ビット）を i=1 としている場合、重みは $2^{i-1}$ です。i を 0 から始めるなら $2^i$ でも良いですが、問題文の定義に合わせることが重要です（オフバイワン＝1ずれのミス）。
2. 「累積変数（integerNum）を掛け算で更新する」誤り
   • 新しいビットの寄与は「足し算」で累積します。掛け算にすると元の合計を歪めます。別の正しい方法として、左から処理する場合は integerNum ← integerNum × 2 + digitNum としても良い（後述）。

補足コラム

• 末尾（右端）から処理する方法と先頭（左端）から処理する方法の2通りあります。問題は末尾から処理していますが、左から順に処理する簡潔なアルゴリズムも覚えておくと便利です。
  左から処理する方法（例："1011" を左から）：
  • 初期 integerNum = 0
  • 各文字 digit（0か1）について： integerNum ← integerNum × 2 + digit
  • これを繰り返すと最終的に正しい10進整数が得られます。
    この方法は重みを明示的に計算しなくてよいので実装が楽です。
• 変換の一般原理は「桁ごとに（桁の値）×（基数の桁重み）を足す」です。2進数なら基数は 2、10進数なら基数は 10 です。

def binary_to_integer(binary_str):
    integer_num = 0
    n = len(binary_str)
    for i in range(1, n+1):  # i = 1..n
        digit = int(binary_str[-i])  # 末尾からi番目の文字を整数に
        exponent = 2**(i-1)
        integer_num += digit * exponent
    return integer_num

def binary_to_integer_left(binary_str):
    integer_num = 0
    for ch in binary_str:  # 先頭から順に
        digit = int(ch)
        integer_num = integer_num * 2 + digit
    return integer_num

FAQ