令和2年度 I-2-5

解説

この問題で問われていること

2進数を10進数に変換するアルゴリズム(s←a_n から始め、上位ビットから順にs←s×2+a_iを繰り返す方法)を用いて、2進数(11010101)₂を10進数に変換する過程でsがどのように更新されるかを求める問題。

解き方

① 2進数は左から「2倍して次のビットを足す」をくり返せば10進数になる
② (11010101)₂: 1→3→6→13→26→53→106→213
③ ア26・イ53・ウ106(⑤)

正解が正しい理由

(11010101)₂の各ビットはa7=1,a6=1,a5=0,a4=1,a3=0,a2=1,a1=0,a0=1である。s←a7=1から始め、s←s×2+a_iをi=6から0まで繰り返すと、i=6: s=2×1+1=3、i=5: s=2×3+0=6、i=4: s=2×6+1=13、i=3: s=2×13+0=26、i=2: s=2×26+1=53、i=1: s=2×53+0=106、i=0: s=2×106+1=213となる。したがってア=26、イ=53、ウ=106の組合せである⑤が正しい。

この問題で必要な基礎

■ 2進数の位取り
2進数では、右から順に1, 2, 4, 8, 16, …の位を表します。例えば(1101)₂=8+4+0+1=13です。

■ 「2倍して次のビットを足す」で変換できる理由
すでに読んだ部分を2倍すると、それぞれの桁が1つ上の位にずれます。そこに次のビットを足していくと、最後には全てのビットが正しい位の重みで足し合わされます。問題文の例(1101)₂では、1 → 1×2+1=3 → 3×2+0=6 → 6×2+1=13です。

各選択肢について

• ① アが「25」、イが「52」、ウが「105」となっており、3つとも誤り。正しくはi=3でs=2×13+0=26、i=2でs=2×26+1=53、i=1でs=2×53+0=106である。
• ② アが「25」、イが「52」となっている点が誤り。正しくはア=26、イ=53である(ウの106は正しい)。
• ③ アは正しいが、イが「52」、ウが「105」となっている点が誤り。正しくはイ=2×26+1=53、ウ=2×53+0=106である。
• ④ イが「53」で正しいが、ウが「105」となっている点が誤り。正しいウの値は106である。
• ⑤ ホーナー法の手順に沿って計算したア=26、イ=53、ウ=106という値が、2進数(11010101)₂=213への変換過程と一致しており、これが正答。

覚えるべきポイント

2進数から10進数への変換は、最上位ビットから順にs←s×2+a_iを繰り返すホーナー法で効率的に計算できる。各ステップの計算結果を1つずつ丁寧に確認することで、桁数が多い2進数でも間違いなく変換できる。