応用情報技術者 2022年秋期午前2 問01

問題文

a

を正の整数とし、

b = a^{2}

とする。

a

を2進数で表現するとnビットであるとき、

b

を2進数で表現すると最大で何ビットになるか。

🖊️ 解答を隠して解いてみる

選択肢

ア：

n + 1

イ：

2 n

（正解）

ウ：

n^{2}

エ：

2^{n}

🔒 解説は解答すると表示されます

二乗の2進ビット長【午前2解説】

正解の理由

a が n ビットで表されるとは

2^{n - 1} \leq a \leq 2^{n} - 1

を意味します。この範囲から

b = a^{2}

は常に

b < 2^{2 n}

であるため、2進表現の桁数は最大で

2 n

ビットになります。逆に、例えば

a = 2^{n} - 1

と取ると

b = (2^{n} - 1)^{2} = 2^{2 n} - 2^{n + 1} + 1 \geq 2^{2 n - 1}

（

n \geq 2

のとき）となり、この場合は確かに

b

が

2^{2 n - 1}

以上であるため、2進表現の桁数は

2 n

ビットを必要とします。以上により正答はイ（

2 n

）です。ただし

n = 1

のときは特例で

a = 1

のみ、

b = 1

となり必要ビット数は1ビットになります。

解法ステップ

a の範囲を確認する: $2^{n - 1} \leq a \leq 2^{n} - 1$ 。
上界を取る: $b = a^{2} \leq (2^{n} - 1)^{2} < (2^{n})^{2} = 2^{2 n}$ 。したがって $b < 2^{2 n}$ より桁数は最大 $2 n$ 。
下界（到達例）を示す: $a = 2^{n} - 1$ とすると $b = (2^{n} - 1)^{2} = 2^{2 n} - 2^{n + 1} + 1.$ これが $2^{2 n - 1}$ 以上であることを示せば、2進での桁数が実際に $2 n$ に達する例が存在する。
n=1 の特例確認: n=1 のとき $a = 1$ のみで $b = 1$ （1ビット）となる。

選択肢別の誤答解説

ア: $n + 1$
誤り。平方を取ると桁数は一般に増え、最大で2倍近くになるため $n + 1$ では不足する場合がある（例: $n = 3$ に対し $a = 7$ のとき $b = 49$ は6ビット）。
イ: $2 n$
正解。上界と到達例（下界）を両方示せるため最大桁数が $2 n$ であると結論できる。
ウ: $n^{2}$
次元が合っていない。 $n^{2}$ は桁数として急速に増えすぎる。例えば $n = 3$ なら $n^{2} = 9$ だが実際の最大桁数は6。
エ: $2^{n}$
桁数が指数関数的に増えるとするもので現実の挙動と合わない。 $2^{n}$ は非常に大きく過大評価である。

よくある誤解

上界を示すだけで解答したつもりになる：上界（ $b < 2^{2 n}$ ）だけでは「最大が $2 n$ ビットである」と断定できない。到達例（ある a で実際に $2 n$ ビットが必要になること）を示して初めて最大値であると示せる。
n=1 を見落とす：一般証明は n≥2 を前提に到達例を示すことが多いので、n=1 の特例（a=1）を確認しないと混乱する。
ビット数の定義混同：数 x の2進ビット数は $⌊ lo g_{2} x ⌋ + 1$ （ $x \geq 1$ ）であることを忘れ、端点（ちょうど 2^k のとき）での扱いを誤る。

補足コラム

ビット数の記述を数学的にまとめると、 $b$ のビット長 $L (b)$ は $L (b) = ⌊ lo g_{2} b ⌋ + 1.$ $b < 2^{2 n}$ なら $⌊ lo g_{2} b ⌋ \leq 2 n - 1$ であり $L (b) \leq 2 n$ 。一方 $b \geq 2^{2 n - 1}$ となる例があるとき $L (b) \geq 2 n$ なので最大値は 2n。
具体例（小さい n）:
- n=1: a=1 → b=1 (1 ビット)
- n=2: a=3 → b=9 (1001₂, 4 ビット = 2n)
- n=3: a=7 → b=49 (110001₂, 6 ビット = 2n)
簡単な検算用 Python スニペット:

def max_bits(n):
    max_b = (2**n - 1)**2
    return max_b.bit_length()

for n in range(1,6):
    print(n, max_bits(n))

FAQ

Q: 「なぜ上界だけでなく到達例が必要なのですか？」
A: 上界は「それ以上にはならない」ことを示すのみ。最大値を断定するには「ある値でその上界に等しい（またはその桁数に達する）」ことを示す下界の例が必要です。

Q: 「もし a が 0 を許すとどう変わりますか？」
A: 問題は正の整数とあるため無関係ですが、a=0 を許すと b=0 でビット数の定義が特殊（通常は0は0ビットまたは1ビット扱いの議論が必要）になります。

Q: 「負の数や符号付き表現は？」
A: 本問は正の整数の標準的な2進表現の桁数を問うているため、符号付き表現（2の補数など）は考慮しません。

関連キーワード: ビット長、二乗、桁数、不等式、最大値、下界の示し方、到達例

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！