補数表現
最近、なんかプログラミング関係の資格でもとろうかと思い調べていたら、基本情報技術者試験というのがあるのをしりました。
国家資格なんですねこれ。ぜひ取りたいですね〜。しかしこの試験結構範囲が広くて勉強が大変です。
さて勉強しているなかで、「2の補数表現」という言葉がでてきました。
2進数でマイナスを表すための表現なのですが、恥ずかしながら、いままでちゃんと理解していませんでした。勉強を兼ねて、「２の補数表現」を自分なりにまとめてみました。
まず補数ってなんですか？
ウェキペディアより
補数（ほすう;complement）とは、ある基数法において、ある自然数 a に足したとき桁が1つ上がる（桁が1つ増える）数のうち最も小さい数をいう。
とあります。うん…わかるような,、わからないような。
まず１０進数で考えてみます。
３桁の10進数カウンターがあるとします。このカウンターは当たり前ですが０〜９９９までを表現できますよね。
もし999までいってもうひとつカウンタが上がると本当は1000になるのですが、カウンタとしては０に戻ります。
つまり999に１を足すと桁が上がるわけですね。このカウンタでは1000は表現できないので、桁溢れつまりオーバーフローを起こしたことになります。
この時999に対して1は補数と言えます。
桁上がりすればいいので、カウンタなど持ち出さず、単純には以下も補数の例です。
- ７に対しての３ 足したら10になる
- 11に対しての89 足したら100になる
- 256に対しての744 足したら1000になる
基数の補数と減基数の補数
実のところ補数には2つ種類があるそうで、先に紹介したウィキペディアの文よりももっと詳細にいうと以下の様になります。
補数とは、ある自然数をn進数（n進法）で表現した時に、足し合わせるとちょうど「nのべき乗」か「nのべき乗-1」になる自然数のうち、最小のもの。
http://e-words.jp/w/%E8%A3%9C%E6%95%B0.html
つまり、さっきの3桁カウンタでいうと999に対しての1は「nのべき乗」すなわち1000になるので基数の補数、998に対しての1は「nのべき乗-1」すなわち999になるので減基数の補数ということになります。
補数の呼び名に関して
「基数の補数」のことを10進数の場合では10の補数、「減基数の補数」のことを10進数では9の補数と呼びます。
10の補数という呼び方は桁があがった事を指す言い方なんだとおもいます。10進数ですから10で桁上がるので10の補数と。
9の補数の呼び名としては足したら必ずその数が9とか99とか999になるから9の補数なんだと思います。
つまり「基数の補数」はその基数の数字をそのまま使って、2進数なら２の補数、8進数なら8の補数、10進数なら10の補数、16進数なら16の補数という呼び方になります。
「減基数の補数」は桁上がり直前の数字を付けてあげればいいので、、2進数なら1の補数、8進数なら7の補数、10進数なら9の補数、16進数なら15の補数という呼び方になります。
補数をつかったら何が嬉しいの？
補数はコンピュータ内の引き算で使われるそうです。
コンピュータのカウンタというのは戻すことができないので、基本的に足すことしかできません。
しかし、補数を使うと足し算だけで引き算が出来ます。
10進数の場合の補数を使った引き算
例えば
130 - 23という計算があったとします（3桁までの計算として）。答えは107ですがコンピュータでは引き算ができません。
さて足し算だけで引き算を行ってみましょう。
まずは引く数の減基数の補数を求めます。10進数なので９の補数ですね。
23には976を足すと999になり、桁上がり直前になりますので976が23の減基数の補数ということになります。
999 = 23 + x
x = 976さらに23の基数の補数を求めます。10進数ですから10の補数ということですね。
これは減基数に1を足せば簡単に求まります。977ということになります。
976 + 1 = 977さて今度は引かれる数に先ほど求めた23の基数の補数である977を足します。
130 ＋ 977 ＝ 1107この場合1000は桁溢れになりますので、107が答えとして残ります。
130 ― 23 = 107ですから、たしかに足し算だけで引き算を行うことができましたね。
2進数の場合の補数を使った引き算
さて問題になるのは2進数の場合ですよね。これも10進数の時と考え方は同じです。
11110110 - 1101の計算をやってみます。10進数に直すと246 - 13ということですね。
2進数は桁数が多いので数え間違えないように…。この計算では8桁までの計算ということにします。
まずは引く数1101の減基数の補数を求めます。2進数なので１の補数ということですね。
2進数の8桁の場合桁溢れ寸前の数は
11111111になります。よって
11111111 = 1101 + x
x = 11110010となります。
さらに1101の基数の補数を求めます。2進数ですから2の補数ということですね。
これは先ほどと同じように減基数の補数に1を足せば求まりますので、11110011ということになります。
11110010 + 1 = 11110011さて今度は引かれる数に先ほど求めた1101の基数の補数である11110011を足します。
11110110 ＋ 11110011 ＝ 111101001この場合100000000は桁溢れになりますので、11101001が答えとして残ります。
11101001は10進数では233ですから、246 - 13の答えになっていますよね。
マイナス符号を表すのにも補数を使う
補数というとどちらかというと、マイナス符号を表現するという認識があるかと思いますが、上記で説明した補数による引き算を理解しているとこちらも簡単に理解できます。
コンピュータ内では符号付き数値と符号なし数値が表現できます。
符号付き数値はマイナスを表現することができますが、マイナスを表すために1bit使わないといけないので、同じ桁なら符号なし数値に比べて表現できる数の範囲は狭くなります。
マイナス数値を扱えるといろいろ便利なこともあるので、数の範囲を犠牲にしても使いたい場合がありますよね。
例えば8bitで表現できる2進数の符号付き数値は、1bitが符号用になるので、実質7bitで数値をあらわすことになります。7bitなので128種類の情報を扱えることになりますね。
1bit目が0の場合はプラス、1の場合はマイナスと決められているので、それぞれの場合において128が表現できますので、この場合の数の範囲は
-128〜127
-1111111〜1111111 となります。プラス側は0を含めることになるので127まで、マイナス側は-1からですので-128までを表現できます。
マイナスを表現する
さてそれでは2進数でのマイナス表現を試してみます。
とは言えこの表現は単に「マイナスには補数を使うね」という「取り決め」ですので深く考えてはいけません。そう決められているということです。
一応仕組みがどうなっているのか確かめてみます。
符号ありの場合、先頭の`1bit目が1の場合マイナスとみなすという取り決めがあると説明しました。
以下の4桁符号付き2進数をマイナスに変換したいと思います。桁数が少ない方がわかりやすいかと思いますので…。
0101先頭1bitは符号用で今はプラスを表す0です。10進数で言うと5ですね。
さてコンピュータ内では取り決めがあり、マイナス数値は絶対値の2の補数で表現するということになっています。
つまり0101の2の補数を算出すればいいのですね。
2の補数は基数の補数のことですから、足すと桁上がりしちゃう数のことですね。
0101を桁上がりさせるのは1011になります。この1011が-5を表現することになります。
4桁の場合の対応表を作ってみました。4bit符号無しの場合は0〜15まで、符号ありの場合は-8〜7までを表現することができます。
| 4桁2進数 | 符号無し | 符号あり |
|---|---|---|
| 1111 | 15 | -1 |
| 1110 | 14 | -2 |
| 1101 | 13 | -3 |
| 1100 | 12 | -4 |
| 1011 | 11 | -5 |
| 1010 | 10 | -6 |
| 1001 | 9 | -7 |
| 1000 | 8 | -8 |
| 0111 | 7 | 7 |
| 0110 | 6 | 6 |
| 0101 | 5 | 5 |
| 0100 | 4 | 4 |
| 0011 | 3 | 3 |
| 0010 | 2 | 2 |
| 0001 | 1 | 1 |
| 0000 | 0 | 0 |
マイナス数値に対応する数はそれぞれ絶対値の「2の補数」になっているのがわかるかと思います。
まとめ
意外とこんがらがりますよね、補数って。でもコンピュータの計算の元にもなっていますからしっかり理解したいものです。
とりあえず
- 足すと桁上がりする数 = 基数の補数 = 2の補数(2進数）= 10の補数（10進数）
- 足すと桁上がり寸前の数 = 減基数の補数 = 1の補数（2進数）= 9の補数（10進数）
という風に覚えておくと良いかもしれません。
