応用情報技術者 2013年春期午前2 問01

問題文

a

を正の整数とし、

b = a^{2}

とする。

a

を2進数で表現すると

n

ビットであるとき、

b

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

選択肢

ア：

n + 1

イ：

2 n

（正解）

ウ：

n^{2}

エ：

2^{n}

$a$ を正の整数とし、 $b = a^{2}$ とする。 $a$ を2進数で表現すると $n$ ビットであるとき、 $b$ を2進数で表現すると高々何ビットになるか。【午前2 解説】

要点まとめ

結論： $a$ が $n$ ビットの2進数ならば、 $b = a^{2}$ は高々 $2 n$ ビットで表現できる。
根拠： $a$ の最大値は $2^{n} - 1$ であり、その2乗は $(2^{n} - 1)^{2} < 2^{2 n}$ であるため。
差がつくポイント：ビット数の最大値を求める際に、単純にビット数の2乗や指数と誤解せず、最大値の2乗の範囲を正確に理解すること。

正解の理由

a

が

n

ビットの2進数で表される場合、

a

の最大値は

2^{n} - 1

です。
このとき、

b = a^{2}

の最大値は

(2^{n} - 1)^{2} = 2^{2 n} - 2^{n + 1} + 1

となり、

2^{2 n}

未満です。
したがって、

b

を表現するのに必要なビット数は

2 n

ビットが上限となります。
よって、正解はイ:

2 n

です。

よくある誤解

a

のビット数を単純に2乗して

n^{2}

ビットと考えたり、指数のように

2^{n}

ビットと誤解することがあります。
また、

a^{2}

のビット数は

a

のビット数の2倍であることを理解せず、

n + 1

ビット程度と見積もる誤りも多いです。

解法ステップ

$a$ の最大値を2進数の $n$ ビットで表すと $2^{n} - 1$ であることを確認する。
$b = a^{2}$ の最大値を $(2^{n} - 1)^{2}$ として計算する。
$(2^{n} - 1)^{2} = 2^{2 n} - 2^{n + 1} + 1$ であり、 $2^{2 n}$ 未満であることを理解する。
$b$ の最大値が $2^{2 n}$ 未満なので、 $b$ のビット数は $2 n$ ビットが上限であると結論づける。
選択肢の中から $2 n$ を選ぶ。

選択肢別の誤答解説

ア: $n + 1$
$a^{2}$ は $a$ のビット数の2倍近くになるため、 $n + 1$ ビットでは表現できない場合が多いです。
イ: $2 n$
正解。最大値の2乗のビット数の上限として正しい。
ウ: $n^{2}$
ビット数の2乗は桁数の増加を誤解したもので、実際のビット数とは無関係です。
エ: $2^{n}$
これは指数関数的にビット数が増えると誤解したもので、現実的なビット数の増加ではありません。

補足コラム

2進数のビット数は数値の最大値の対数に比例します。
一般に、

x

を2進数で表すときのビット数は

⌊ lo g_{2} x ⌋ + 1

です。
この問題では、

a

の最大値とその2乗の最大値の対数を比較することで、ビット数の上限を求めています。
この考え方は、数値の範囲や桁数を扱う際に非常に重要です。

FAQ

Q: なぜ

(2^{n} - 1)^{2}

のビット数は

2 n

ビットになるのですか？
A:

(2^{n} - 1)^{2}

は

2^{2 n}

未満の最大値であり、

2^{2 n}

は

2 n + 1

ビット目に1が立つ数なので、

2 n

ビットで表現可能です。

a

が

1

ビットのとき、

b

のビット数はどうなりますか？
A:

a = 1

のとき、

b = 1

で1ビットです。

2 n = 2

ですが、これは上限なので実際は1ビットでも問題ありません。

関連キーワード: 2進数、ビット数、最大値、桁数計算、数値の範囲

← 前の問題へ次の問題へ →

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2013年 春期 午前2 問01

問題文

選択肢

aを正の整数とし、b=a2とする。aを2進数で表現するとnビットであるとき、bを2進数で表現すると高々何ビットになるか。【午前2 解説】