高校情報I ビットと情報量—表せる種類と必要な桁数を条件から求める｜武蔵野個別指導塾

必要な種類数を前後の桁数で比べ、記録を連結して整数バイトに収める計算まで、条件から判断する力を養います。

よくあるのは、識別したい種類が12個あるという問題を見て、12ビットと答える場面です。種類を1個増やすたびにビットを1桁増やす必要があるわけではありません。各桁に0と1を置くと、その組合せで複数の種類を区別できます。何通り作れるか、求める答えは種類数か桁数かを先に確認しましょう。ここでは固定された長さのビット列と容量の換算を扱います。自分の範囲表と授業ノートの表記も照らし合わせてください。

問われる向きはどちらか

定期テストでは、まず「何ビットで何種類を区別できるか」が問われます。桁数から出発し、各桁の選択肢を掛け合わせる型です。同じ列を2つの対象に割り当てると区別できないため、異なる種類には異なる列を割り当てます。0で始まる列も、固定長の列として数えます。

次に「必要な種類を区別するには最低何ビットか」があります。こちらは種類数から出発し、足りる桁数と、その1桁前が足りないことを比べます。ちょうど収まる場合と、1種類でも超える場合を区別することが大切です。

もう1つはビットとバイトの換算です。単位の倍率と端数の扱いを問題から読み、途中の量をビットでそろえます。実際の保存では付加情報や割当ての単位があることもあるため、計算した量が何を数えているかも答えに添えます。

0と1の組合せを増やす

ビットは0か1のどちらかをとる桁です。1ビットなら0と1の2通り、2ビットなら00、01、10、11の4通りです。2桁目には、それぞれ0と1の選択があるので、1桁目の2通りそれぞれが2通りに分かれます。桁を1つ増やすたびに、作れる列の数は2倍になります。

図1のように、1ビットから始めて桁を増やすと、種類数は2、4、8、16と増えます。ここで数えているのは列そのものの種類です。例えば3ビットの000と001は、先頭の0も含めた別の列です。番号として読んだときの値と、作れる列の個数を混ぜないようにします。

種類数が列の数以下なら、列を重複せず割り当てられます。余った列があっても構いません。反対に、列の数より種類数が多ければ、どのように割り当てても同じ列を共有する種類が出るため、識別できません。必要な桁数を求めるときは、この足りる・足りないの境界を探します。

この先の例では1バイトを8ビットとします。1 kBを1000バイト、1 KiBを1024バイトと定めた場合には、それぞれの倍率で換算します。記号が似ていても同じ倍率とは限らないので、問題の指定を先に書き留めます。ビット数とバイト数は同じ対象の量を違う単位で表したもので、種類数そのものとは別の量です。

基本例題：ラベルに必要な桁

自作の整理用ラベルを10種類作り、各種類に異なる固定長のビット列を1つずつ割り当てます。最低何ビット必要ですか。答えは整数で、足りることと1桁少ない場合が足りないことも示してください。

図2のように、候補の桁数ごとに列の数を調べます。必要な10種類に初めて届くところを選びます。

1行ずつ計算すると、次のようになります。

1ビットでは2通りなので、10種類には足りません。

2ビットでは2×2で4通りなので、まだ足りません。

3ビットでは2×2×2で8通りなので、これも足りません。

4ビットでは2×2×2×2で16通りになり、10種類を区別できます。

したがって答えは4ビットです。16通りのうち10通りを別々のラベルに割り当てると、6通りが余ります。余りがあることは失敗ではありません。3ビットに戻すと8通りしかなく、少なくとも2種類分が足りないので、4ビットが最低であることも確かめられます。

たとえば0000から1001までを別々に使えば、10個の列を用意できます。先頭の0を消して長さを変えず、4桁の列として扱ってください。16通りという答えは「4ビットで作れる列の数」であり、使うラベルが16種類でなければならないという意味ではありません。

境界を見落とさないための確認

列の数が必要な種類数と同じなら、その桁数で足ります。余りが0でも、各種類に別の列を1つずつ割り当てられるからです。一方、種類がそこから1つ増えれば、同じ桁数では足りず、次の桁数を調べます。「以上」と「より大きい」の読み間違いが、ここでは1桁の差につながります。

最小を求める問題では、表を順に書くほか、候補を先に選んで前後を調べる方法もあります。ただし候補を思いついた理由が曖昧なときは、2倍ずつ増やす表に戻ってください。桁数と種類数の見出しを分ければ、途中でどちらを答えるかを取り違えにくくなります。

固定長という条件も重要です。すべての対象に同じ桁数を使うので、先頭が0の列も桁を削らず数えます。途中に使わない列があっても、割当てが重ならなければ識別できます。割当ての順序自体は最低桁数を変えませんが、同じ列を2種類に与えた場合は区別という目的を満たしません。

少し難しい例題：まとめて保存する

自作の記録で、35種類の状態をそれぞれ異なる固定長の列で表します。各記録に同じ最小のビット数を使い、記録は全部で1500個です。列を途中で区切らず連結し、最後に不足するビットを0で補って、整数個のバイトにします。1バイトは8ビット、1 kBは1000バイトです。圧縮せず、付加情報も付けません。必要な桁数と、補いを含む容量を整数のバイトと小数のkBで求めてください。

5ビットでは32通りなので35種類には不足します。6ビットでは64通りなので足ります。よって1記録は最低6ビットです。使わない列は64から35を引いた29通りです。列を全部使う必要はなく、各状態に異なる列が割り当てられることが条件です。

1500個の列を連結すると、6×1500で9000ビットです。9000を8で割ると1125で、余りは0です。この条件では最後に補うビットはありません。したがって1125バイト、1000で割って1.125 kBです。答えを元に戻すと1125バイトは9000ビットで、6ビットの記録1500個分に一致します。

記録ごとに整数バイトへ切り上げる条件なら結果は変わります。6ビットの各記録を1バイトずつ使うため1500バイトです。今回の条件は列を連結してから最後に補うので、この切り上げを各記録には行いません。問題文に保存方法の指定がなければ、どちらの量を求めるかを確認する必要があります。

誤答をほどく

基本例題で「10種類だから10ビット」と答えた場合を考えます。10ビットあれば十分ですが、最小とは限りません。種類数と桁数は異なる量であり、1種類につき1桁を用意する方法しかないと考えたことが原因です。図3のように4ビットの16通りと3ビットの8通りを比べ、最低4ビットに直します。

別の誤りは、必要な種類数に足りる列の数を見つけて終わることです。たとえば5ビットも10種類には足りますが、より少ない桁数でも足りるため最低ではありません。候補が足りるという確認と、1桁少ない候補が不足するという確認の両方を書きます。

容量換算では、ビットをバイトにする際に8を掛ける誤りもあります。1バイトに8ビットが入るので、ビット数からバイト数へは8で割ります。割り切れないときは端数をそのまま表すのか、最後に補って整数バイトにするのかを条件から判断します。逆に戻したとき、補いを含めたビット数が元の列を収めるかも見てください。

単位を戻して確かめる

割り算の答えをそのまま書く前に、何をまとめてから補うかを読み直します。連結した全体の末尾を補う場合、最後に生じる余りに対して一度だけ補います。記録ごとに補う場合は、各記録の余りを個別に埋めるので、同じ元のビット数でも保存に使うバイト数が異なることがあります。

また、種類を区別するための最低桁数は、記録の個数では決まりません。記録が何個あっても、各記録に表す種類が同じなら、1記録に必要な桁数は同じです。記録数を掛けるのは、1記録の桁数を求めてから全体の量を出す段階です。この順番を逆にすると、種類と記録の個数を混同しやすくなります。

計算の最後には、答えに単位を付けます。ビットからバイトに直した場合は、バイト数を8倍して元のビット数と補いの合計に戻します。kBやKiBまで直した場合は、指定された倍率を掛けてバイトに戻します。戻した値が合わなければ、倍率、割る向き、端数のいずれかを調べ直します。

解答欄に残す理由

桁数の問題で答えだけを書くと、足りることを確かめたのか、最低であることまで調べたのかが読み手に伝わりません。候補の列数と1桁前の列数を並べ、それぞれ必要な種類数と比較すると、短い記述でも判断の筋道が見えます。余った列の数を問われたときは、作れる列数から実際に割り当てる種類数を引きます。

容量の問題では、計算結果が整数であっても端数処理の条件を省かないようにします。今回の発展例のように割り切れる場合は、補いが0ビットであることも確認できます。割り切れない場合は、余りのビット数と、次のバイトを満たすために必要な補いを区別します。余りそのものが補いではありません。単位を添えて記録すると、後から計算を追えます。

練習：条件を拾ってから計算する

次の問題はすべて自作です。各種類に異なる固定長の列を割り当て、使わない列があってもよいものとします。問題を解いてから、後の答えと比べてください。

1. 展示の区画を識別するため、5ビットの列を使います。区別できる区画は最大何種類ですか。整数で答えてください。
2. 道具の分類が17種類あります。最低何ビット必要ですか。整数で答え、1桁少ない場合と比較してください。
3. 9ビットの記録を25個、隙間なく連結します。1バイトは8ビットとし、最後に0を補って整数バイトにします。付加情報と圧縮はありません。補うビット数と容量をそれぞれ整数で答えてください。
4. 1 KiBを1024バイト、1バイトを8ビットとします。付加情報のない2 KiBの領域には何ビット入りますか。整数で答えてください。

答えと解き方

1. 32種類です。2を5回掛けると32通りです。5桁の列を重複なく32種類に割り当てられ、33種類目には別の列が残りません。最大という条件まで確かめます。

2. 5ビットです。4ビットでは16通りで1種類不足し、5ビットでは32通りで17種類を収められます。32通りから17通りを割り当てても15通り残るので、余りを理由に6ビットへ増やす必要はありません。

3. 追加は7ビット、容量は29バイトです。9×25で225ビット、8で割ると28バイトと1ビットです。最後の1ビットを入れるバイトには残り7ビットが必要です。29バイトを8倍すると232ビットで、225ビットと補い7ビットの合計に戻ります。各記録を個別に2バイトにする計算は、連結する条件に合いません。

4. 16384ビットです。2 KiBは2048バイトで、8を掛けます。逆に16384ビットを8で割ると2048バイト、さらに1024で割ると2 KiBです。kBと取り違えず、問題が指定した倍率を使います。

要点を手元に残す

桁を1つ増やすと、作れる列の数は2倍です。
最低の桁数は、足りる候補と1桁前の不足を比べます。
容量は倍率と端数の扱いを条件に合わせて換算します。

どこで止まったかを見分ける

答えが合わないときは、最初に種類数と桁数のどちらを問われたか、問題文に印を付けてみましょう。種類数をそのまま桁数にしたなら、2桁の列を実際に並べるところから組合せを確かめます。列の数は合っていても最低を説明できないなら、1桁前の候補を記録に加えます。

個別指導では、計算途中の単位と端数の処理を本人のノートで確認し、なぜその演算を選んだかを言葉にしてもらいます。最後に答えを元の種類数や記録数に戻せれば、式の意味まで点検できます。境界を挟む2つの列数が、必要な桁数を決めます。