2 乗した数のビット数
出典: 令和4年度 秋期 応用情報技術者試験 午前 問1 (IPA)
a を正の整数とし，b ＝ a² とする。a を 2 進数で表現すると n ビットであるとき，b を 2 進数で表現すると最大で何ビットになるか。
- ア n＋1
- イ 2n
- ウ n²
- エ 2ⁿ
正解と解説を見る
正解: イ
- ア: n ＝ 2 のとき a ＝ 3、b ＝ 9 ＝ 1001₂ で 4 ビットになり、n ＋ 1 ＝ 3 ビットには収まりません。
- イ: a ＜ 2ⁿ なので a² ＜ 2²ⁿ となり、最大で 2n ビットなので正しい答えです。
- ウ: n² は、例えば n ＝ 3 のとき 9 ビットになりますが、7² ＝ 49 は 6 ビットで表せるので多すぎます。
- エ: 2ⁿ は、例えば n ＝ 3 のとき 8 ビットになりますが、実際には 6 ビットで足ります。
ポイント
- n ビットで表せる最大の数は 2ⁿ − 1 なので、a ＜ 2ⁿ です。
- よって b ＝ a² ＜ 2ⁿ × 2ⁿ ＝ 2²ⁿ となり、b は最大で 2n ビット で表せます。
- 確認: n ＝ 2 (a の最大は 3 ＝ 11₂) のとき、b ＝ 9 ＝ 1001₂ で 4 ビット ＝ 2n。