2進法および16進法

コンピュータでもっともよく用いられる2進法および16進法について説明します。

<注意>
このページでは、数式を表示するためにMathJaxを使用しています。ブラウザの設定でスクリプト実行をブロックしている場合、ページ内の数式が正しく表示されません。

10進法と位取り記数法

普段、私たちはどのように数を数えているでしょうか。おそらくほとんどの人は0,1,2,3,…,9,10,11,…と数えるでしょう。いわゆる10進法(decimal)と呼ばれている数の表現です。
10進法では10数えると一つ繰り上がりますが(この10を底という)、数学的には別に底が10でならなければならない理由はなく(非実用的でよいならば底は小数でもよいし、極端な例では\(\ \pi\ \)進法なども考えることができる)、10進法が広く普及している理由は人の両手の指の合計が10であるからだとされています。
一般的に、\(\ n\ \)数えると繰り上がるような数え方を\(\ n\ \)進法といいます。

\(\ n\ \)進法では、異なる\(\ n\ \)個の数字と呼ばれる記号を使って数を表記します。普段使っている10進法なら、0,1,2,3,4,5,6,7,8,9という10個の数字を使って書けますね。これらの数字をいくつか並べることで任意の数を表現することができます。10進法を含む\(\ n\ \)進法では、次の規則が必ず満たされます。

定理
\(\ n\ \)進位取り記数表現は、常に次の条件を満たす。

1. \(\ n\ \)倍するたびに1つ桁が増える
2. 1桁で表すことができる数は、\(\ n-1\ \)までであり、(アラビア数字を使うのであれば)\(\ 10\ \)という数字は\(\ n\ \)を表す。

\(\ n\ \)進数において、もっとも下の桁を1の位と言います。そこから左に行くつれ、\(\ n\ \)の位、\(\ n^2\ \)の位、…と言います。\(\ n=10\ \)であればこれはすなわち10の位、100の位、…です。任意の\(\ n\ \)進数が表す数は、10進数で次のように表現できます。

定理
任意の\(\ n\ \)進数が表す数は、十進数では\( \sum a_in^i\ \)と書ける。
ここで、\(\ a_i\ \)は、\(\ n^i\ \)の位の数字である。

2進法と16進法

さて、コンピュータでは数の内部表現としてふつう2進法が使用されます。
前の節の定義に従えば、2進法(binary)とは、0と1だけを使って表す、2倍するごとに桁が1つ増えるような位取り記数法であると言えます。
ところで、2進数はそのまま読み書きするには長すぎて(人間にとって)不便なので、もう少しコンパクトにした16進法(hexadecimal)がよく使われます。16進法も前節の定義に従えば、16個の数字を使って表す、16倍するごとに桁が1つ増えるような位取り記数法だと言えます。16進法では普通の数字(0～9)にアルファベットのA～Fの6文字を加えた16個の「数字」を使います。

このとき、(別に2進法や16進法に限った話ではないですが)そのまま数字を書いたのでは何進法で表しているのか分からなくなってしまいます。このような混乱を避けるため、2進数と16進数には特殊な記号を付けて区別します。文脈上明らかな場合を除いて何も記号がついていない数は10進法とみなします。

表示規則
文脈上2進数であることが明らかな場合を除き、2進表記された数は、プレフィックス"0b"または"%“のいずれかをつけて明示する。
文脈上16進数であることが明らかな場合を除き、16進表記された数は、プレフィックス"0x"または”\(\$\)“のいずれか、あるいはサフィックス"h"をつけて明示する。

改造では、主に16進法を使うことになりますが、プレフィックスの使い分けを行うことがあります。16進プレフィックス"0x"は一般的な数値を表す場合によく使用されます。16進プレフィックス”\(\$\)“は、アセンブリソースコード内などでデータアドレスを示す際に使用されます。ただし、アセンブリ内では16進リテラル(定数)はプレフィックス”\(\#\$\)“を使用し、“0x"は使用しません。
なお、2進整数を16進整数に書き換える場合は、1の位から4桁ごとに区切っていき、そのまとまり1つを16進数の1桁に対応させていくことで簡単に書き換えられます。

2進数の各桁は、右から順に\(\ 2^0,\ 2^1,\ 2^2,\ \dots\ \)の重みを持ちます。
1の位から4桁ずつ区切ると、それぞれが16進数の1桁になります。

ビット・バイトと情報量

2進数の1桁、すなわち0か1で表される1桁をビット(bit)と言います。ビットは情報量の最小単位です。通常、0を電圧が低い状態(low)に対応させ、1を電圧が高い状態(high)に対応させます。そして、8ビット、すなわち2進数8桁をバイト(byte)といい、一般的にはコンピュータはバイトの整数倍単位でデータを取り扱うのが普通です。SNESのCPUである65C816は16ビットCPUであり、1バイトないし2バイトのデータを一度に取り扱うことができます。最近のパソコンで使用されているCPUは、32ビットや64ビットCPUであり、4バイトや8バイト単位のデータを一度に取り扱うことができます。

さて1バイトは8ビットです。したがって1バイトで表すことのできる情報は\(\ 2^8=256\ \)通りです。同様に2バイトでは\(\ 2^{16}=65536\ \)通り、…です。
どのようなデータもコンピュータから見ればただの数値に過ぎないため、これは単純に1バイトであれば0～255までの整数、2バイトであれば0～65535までの整数、…を表すことができると言っているのと同じです。複雑なデータほどよりたくさんの情報量を必要としますから、より多くのバイト数を消費することが分かると思います。

なお、このことと鳩の巣原理からわかるように、任意のデータを可逆圧縮することを考えたとき、どのような圧縮アルゴリズムを構築したとしても、全く圧縮できないデータが必ず存在することが分かります。以下にその証明を載せておきます。
ただし、不可逆圧縮に関してはこれは必ずしも当てはまりません。なぜなら入力と出力は必ずしも1対1対応しなくてよい(むしろ1対1対応しないから不可逆圧縮となるのである)からです。

証明
\(\ n\ \)ビットの情報量で表されるデータの総数は\(\ 2^n\ \)通りである。
このデータを圧縮するということは、元の入力よりも1ビット以上少ない出力を得るということである。したがって、出力は1ビットから\(\ n-1\ \)ビットまでのいずれかの情報量を持つ(0ビットでは情報が失われてしまうから圧縮できたことにならない)。
1ビット以上\(\ n-1\ \)ビット以下の情報量で表されるデータの総数は、\(\ \sum_{k=1}^{n-1} 2^k=2^n-2\ \)である。
これは\(\ n\ \)ビットの情報量で表すことのできるデータの総数よりも2少ない。
今考えている圧縮アルゴリズムは可逆圧縮であるから、入力と出力は必ず1対1対応していなければならない。
したがって、\(\ n\ \)ビットのデータのすべてを\(\ n-1\ \)ビット以下のデータに対応させることはできない。
よって、どのような可逆圧縮アルゴリズムを作ったとしても、少なくとも1つ以上は全く圧縮できないデータが存在する。

符号付数値表現

さて、このページの最初の節で述べた一般の\(\ n\ \)進数の定義は、非負整数、すなわち0以上の整数に対して規定されるものです。負の数をあらわすときにどうすればよいのかと言えば、もっとも単純には、普段使う数と同じように負号”\( - \)“をつければよいことになります。しかし、コンピュータの世界ではそのような表現はあまりしません。
ここでは、コンピュータの世界で用いられる4つの負の数の表し方を説明します。

まず1つ目の表現は、もっとも単純な表現である絶対値表現です。

定義 (絶対値表現)
非負2進整数の最上位に符号ビットを付けたし、これが0であれば正の数、1であれば絶対値が同じ負の数をあらわすものとする。

結局言っていることは、マイナス記号の代わりとして先頭に0/1をつけるよということだけです。普段私たちが行っている負の数の表現の方法と全く同じなので非常に分かりやすい反面、内部計算的にはあまり効率がよくないという欠点があり、ほとんど使用されません。

2つ目は、下駄履き表現と呼ばれる方法です。

定義 (下駄履き表現)
事前に決めておいた任意の整数Nを元の数値に足した非負整数を、エクセスNの下駄履き表現、あるいはバイアス表現という。

言葉だけでは分かりづらいですが、2進数の0～\(\ N\ \)に対応する値を、\(\ -N\ \)～0に対応させるような表現方法です。ちょうど数直線を右に\(\ N\ \)だけずらしたものと考えればよいでしょう。これも内部演算的にはあまり効率がよくないのですが、好きな範囲で負数の範囲を決められるため、稀に使用されます。
SDKシリーズではスプライトの配置座標がエクセス256の下駄履き表現で表されます。またIEEE浮動小数点標準において、単精度浮動小数点数の指数部は8ビット長のエクセス127下駄履き表現、倍精度浮動小数点数の指数部は11ビット長のエクセス1023下駄履き表現として規格化されています。

3つ目は、1の補数と呼ばれる方法です。

定義 (1の補数)
非負2進整数の最上位に1ビットを付けたし、この非負整数の各ビットを反転したものを、絶対値が同じ負の数とする。

一般的にこの1の補数を求める操作はビット反転と呼ばれます。古いコンピュータでは比較的一般的でしたが、内部演算がやはり少し非効率なため、今では過去のものとなっています。ただし、この方式の利点として、符号反転が非常に効率よく行えることがあげられます。なお、絶対値表現と同じく、0の表現が2通り生じるという欠点があります。

4つ目は、2の補数と呼ばれ、今日標準的な符号付数値表現としてもっぱら使用されているものです。

定義 (2の補数)
非負2進整数の1の補数に1を加えた値(2の補数)を絶対値が同じ負の数とする。

2の補数表現は今日標準的な方法として普及しており、SNESのCPUである65C816もこの2の補数表現で数値を解釈します。
2の補数表現の符号反転はまずビット反転して1の補数を求め、それから1を足します。正の数から負の数を求めるときも、その逆の場合も同じです。
2の補数表現の最大の利点は、符号が異なる数値同士、負の数同士の計算でも、正の数同士の計算と全く同じ方法で正確に行えることがあげられます。これは2の補数表現以外の3つの表現ではなしえなかったことで、この内部演算の効率化が可能な点が、今日2の補数表現が広く使われる理由です。
整数で小数を表す方法については、固定小数点数を参照してください。

4ビットのビット列が、4つの表現でそれぞれどの値を表すかを比べたものです。
絶対値表現と1の補数では、0が2通り(絶対値表現は0000と1000、1の補数は0000と1111)あります。
絶対値表現では、負の数の並ぶ向きもほかの表現と逆になります。

4ビットのビット列を円に並べると、2の補数の値は、符号なしの値と同じ向きに1ずつ増えていき、0111(+7)の次が1000(−8)になります。
符号なしと2の補数は、値が折り返す場所(破線)が違うだけなので、足し算や引き算を同じ回路で計算できます。

2進・16進対応表

簡単な値および主要な値の2進、10進16進の対応をまとめています。

符号なし整数

符号付き8ビット整数

符号付き16ビット整数

参照

論理代数
合同算術
固定小数点数