ITパスポート 2018年 春期 問75

文字を表現するのに必要な最小ビット数【ITパスポート 解説】

正解の理由

解法ステップ

1. 「ビット数 $n$ で表せる組み合わせ数」は $2^n$ であることを確認します。
   • 理由：各ビットが0か1の2通りだから、$n$ 個で $2\times 2\times \cdots =2^n$ 通り。
2. 必要な組み合わせ数（この場合は26）を満たす最小の $n$ を探します。
   • 試しに小さい $n$ を計算：
     • $2^4=16$（不足）
     • $2^5=32$（これで足りる）
3. したがって最小の $n$ は5。これが答えです。数学的には $n=\lceil {\log }_{2}26\rceil =5$ と表せます（$\lceil \rceil$ は切り上げ）。

選択肢別の誤答解説

• ア: 4
  • $2^4=16$ で、26種類を区別するには不十分です。4ビットでは足りません。
• イ: 5
  • $2^5=32$ により26種類を表現できます。かつ「最小」の条件を満たします。よって正解です。
• ウ: 6
  • $2^6=64$ と十分ですが、問題は「最小限必要なビット数」を問うています。6は過剰であり最小ではありません。
• エ: 7
  • $2^7=128$ ともっと過剰です。歴史的にASCII（アスキー。英語の基本文字と記号を表す規格）は7ビットで表していましたが、本問の条件（26文字のみ）では不要です。

よくある誤解

• 「26だからビットも26必要だ」と考える。
  • 誤りです。1ビットで2種類、2ビットで4種類…という倍々に増える性質を理解してください。
• 「5ビットでは余りがあるからダメ」と思う。
  • 問題は「最小限必要なビット数」を問うています。余り（未使用の組み合わせ）があっても構いません。重要なのは「26を表せる最小のビット数」です。
• 「バイト（8ビット）で考えなければ」と混同する。
  • 実務では1バイト = 8ビット単位で扱うことが多いですが、理論的な最小ビット数はビット単位で計算します。

補足コラム

• 大文字と小文字の両方（A～Z と a～z）を区別するなら合計52種類必要です。$2^5=32$ では足りず、$2^6=64$ で足ります。したがってその場合の最小ビット数は6です。
• 数字や記号も含めるとさらに多くの組み合わせが必要です。文字集合の総数をまず数えることが基本です。
• 計算機的には対数を使って簡潔に表せます：$n=\lceil {\log }_{2}N\rceil$ （Nは必要な種類数）。
  • 例：$N=26$ のとき ${\log }_{2}26\approx 4.7004$ を切り上げて $5$。

def min_bits(n):
    bits = 0
    while 2**bits < n:
        bits += 1
    return bits

print(min_bits(26))  # 出力: 5

FAQ