【応用情報 平成25年春期 午前問1】2進数の性質に関する問題

2進数の性質を問う問題。

「高々何ビット」というのは「最大で何ビット」と同じ意味である。

nビットの数字の最大値は2ⁿ-1であるから、aがnビットの時のbの最大値は(2ⁿ-1)²となる。

そこで、いくつかnの値を代入してbの最大値を確かめてみる。

• n = 1  ➡  b_max = (2¹-1)²= 1(1ビット)  ➡  ビット数n
• n = 2  ➡  b_max = (2²-1)²= 9(4ビット)  ➡  ビット数2n
• n = 3  ➡  b_max = (2³-1)²= 49(6ビット)  ➡  ビット数2n
• n = 4  ➡  b_max = (2⁴-1)²= 225(8ビット)  ➡  ビット数2n
• n = 5  ➡  b_max = (2⁵-1)²=961(10ビット)  ➡  ビット数2n

n=1からn=5まで代入してみたが、bは高々2nビットになりそうだとわかる。

b = (2ⁿ-1)² = 2²ⁿ – (2ⁿ⁺¹+1) < 2²ⁿ(2n+1ビットの最小値) であるから、2nより大きいビット数になることはない。

以上より、bは高々2nビットとなり、イが正解である。