令和4年度 I-2-5

解説

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

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

解き方

① 2進数は左から「2倍して次のビットを足す」をくり返せば10進数になる
② (11001011)₂: 1→3→6→12→25→50→101→203
③ ア12・イ25・ウ50・エ101(⑤)

正解が正しい理由

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

この問題で必要な基礎

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

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

各選択肢について

• ① アが「12」で正しいが、ウが「51」となっている点が誤り。i=4の時点でs=2×6+0=12であり、その後i=3でs=2×12+1=25となるため、ウ(i=2時点)は2×25+0=50が正しい。
• ② イが「26」となっている点が誤り。i=3の時点でs=2×12+a3=2×12+1=25であり、26にはならない。
• ③ イが「26」、ウが「52」となっている点が誤り。正しくはi=3でs=25、i=2でs=50である。
• ④ エが「102」となっている点が誤り。i=0の時点でs=2×50+a1=101(この時点ではi=1)、さらにi=0でs=2×101+1=203となるべきところ、102ではその後203に到達しない。
• ⑤ ホーナー法の手順に沿って計算したア=12、イ=25、ウ=50、エ=101という値が、2進数(11001011)₂=203への変換過程と一致しており、これが正答。

覚えるべきポイント

2進数から10進数への変換は、最上位ビットから順にs←2×s+a_iを繰り返す(ホーナー法)ことで効率的に計算できる。各ステップで「2倍してそのビットの値を足す」という操作を機械的に繰り返せば、桁ごとの重み(2のべき乗)を個別に計算する必要がない。