aを正の整数とし，b=a²とする。aを2進数で表現するとnビットであるとき，bを2進数で表現すると最大で何ビットになるか。
- n+1
- 2n
- n²
- 2ⁿ
解答
イ
解説
2進数の各桁での最大数を例に挙げていくと下表の通りになります。（添字は進数）
| a₂ | a₂の桁数 | a₁₀ | b₁₀ | b₂ | b₂の桁数 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 |
| 11 | 2 | 3 | 9 | 1001 | 4 |
| 111 | 3 | 7 | 49 | 110001 | 6 |
| 1111 | 4 | 15 | 225 | 11100001 | 8 |
| … | … | … | … | … | … |
| 11111111 | 8 | 255 | 65025 | 1111111000000001 | 16 |
このように、aがnビットの場合、bは最大2nビットになることがわかります。
参考情報
分野・分類
| 分野 | テクノロジ系 |
| 大分類 | 基礎理論 |
| 中分類 | 基礎理論 |
| 小分類 | 離散数学 |
出題歴
- AP 令和4年度秋期 問1
- AP 平成25年度春期 問1
