応用情報技術者試験 令和4年秋 午前問1 解説付き過去問

この問題は、整数aを2進数でnビットで表現できるとき、b＝a²を2進数で表現する際に必要な最大ビット数がいくつになるかを問うものです。

1. aのビット数の意味
   aがnビットで表現できるとは、aが2ⁿ⁻¹以上、2ⁿ未満の整数であることを意味します。すなわち、最大値は 2ⁿ − 1 です。
   
   
2. b＝a² の最大値
   aの最大値は 2ⁿ − 1 なので、b＝(2ⁿ − 1)² となります。これを展開すると、
   (2ⁿ − 1)² ＝ 2²ⁿ − 2ⁿ⁺¹ + 1 となり、bはおよそ 2²ⁿ に近い値になります。
   つまり、bは最大でも 2n ビット未満で表されますが、2²ⁿ⁻¹ は超えるため、2n−1ビットでは足りず、2nビットが必要になります。
   
   
3. 具体例による確認
   
   1. a＝3（2ビット） → b＝9 → 4ビット
   2. a＝7（3ビット） → b＝49 → 6ビット
   3. a＝15（4ビット） → b＝225 → 8ビット
   4. a＝31（5ビット） → b＝961 → 10ビット
   このように、aがnビットのとき、bは最大で2nビットとなることが分かります。
   
   

したがって、bを2進数で表現する際の最大ビット数は 2n です。