進数・ビット演算と符号化

情報処理では、数値を2進数や16進数など基数の異なる表記で扱い、ビット単位の論理演算で値を加工し、可変長の符号で情報を表現する。これらはいずれも2進数の桁ごとの計算として理解すると一貫して把握できる。試験では、基数変換の計算、ビット演算の結果、符号の復号可能性と平均符号長が中心に問われる。

基数変換と必要な桁数

基数 r の表記では、各桁の数字に r の累乗を掛けた値を合計して、ある数を表す。逆に、値を r で割った余りを下位の桁から順に求めると、その数の r 進数表記が得られる。たとえば、10進数の 123 を基数26で表す場合、26 で割った商 4 と余り 19 を用いて 4×26+19 と分解できる。英大文字を 0 から順に A、B と割り当てると、この値は E と T の並びになる。

必要な桁数の算定では、記号の種類数を底とする累乗で表せる通り数が、必要な個数以上であるかを確かめる。例えば、現在8,000件の対象が毎年2割ずつ増えるとき、3年後の件数は 8,000 × 1.2^3 で13,824件となる。英大文字26種類を使うと、2桁では 26^2 = 676 通りしか得られず不足するが、3桁では 26^3 = 17,576 通りとなり必要数を満たす。このように、増加を見込んだ件数から最小の桁数を求めることが、番号体系の設計で用いられる考え方である。

ビット演算とマスク

AND は、2つの値の同じ桁どうしがともに1のときだけ1を返す演算であり、OR は、どちらか一方が1であれば1を返す演算である。255 は2進数で 11111111 と表せるため、値と 255 の AND は下位8ビットだけを残す操作となり、256で割った余りと同じ結果になる。このため、8ビットの範囲で値が折り返される処理を表す式として用いられる。 256 は 100000000 と表せるため、256 との AND は9ビット目だけを取り出す。一方、255 との OR は下位8ビットをすべて1にする。