平成25年度 春期 応用情報技術者試験 午前 問1

n ビットの正の整数 a の範囲は 2ⁿ⁻¹ ≦ a ≦ 2ⁿ − 1 です。

b ＝ a² ≦ (2ⁿ − 1)² ＝ 2²ⁿ − 2ⁿ⁺¹ ＋ 1 ＜ 2²ⁿ

2²ⁿ 未満の整数は 2n ビットで表現できるので，b は 高々 2n ビット になります。

• ア: n＋1
  誤り。例えば a ＝ 7（3ビット）のとき b ＝ 49 ＝ 110001₂ で6ビットになり，n＋1 ＝ 4ビットでは表せません。

• イ: 2n
  正しい。a が n ビットなら a ≦ 2ⁿ − 1 なので，b ＝ a² ≦ (2ⁿ − 1)² ＜ 2²ⁿ となります。2²ⁿ 未満の数は 2n ビットで表せるので，高々 2n ビットです。

• ウ: n²
  誤り。n² ビットは必要な桁数より大きすぎます。例えば n ＝ 3 のとき 9ビットですが，b は最大でも 49 で6ビットに収まります。

• エ: 2ⁿ
  誤り。2ⁿ は a の取り得る値の上限に相当する値で，ビット数ではありません。必要なビット数は 2n です。

答え

イ: 2n