ミジンコでもわかる補数表現

2024年6月18日

補数を理解しよう

補数（complement）とは、ある数を別の数に足すことで、特定の基数（基準となる数）になる数のことを指します。逆にいえば、与えられた数を定められた数から引くことによって得られる数ともいえます。

一般にn進数には「nの補数」と「n-1の補数」があります。

IPAの資格の勉強でよく見かけるのは、2の補数でしょう。

10進数の場合の補数

9の補数

桁がぎりぎり変わらない数。4桁なら9999にするために必要な数。各桁の数字を9から引いた数。

例えば、10進数「1234」の9の補数は「8765」です。

10の補数

桁がちょうど増えたときの数にするために必要な数。ここでは10000。

例えば、10進数「1234」の10の補数は、「8765」（9の補数）に1を足して「8766」になります。

2進数の場合の補数

1の補数

各桁の数字を1…1bから引いた数。

例えば、1010bの1の補数は0101b。各桁をビット反転（NOT演算）するだけで得られます。

2の補数

ビット反転して最後に1を足す。

例えば、1010bの2の補数は、0101b（1の補数）に1を足して0110bになります。

補数の一般化

補数とは、与えられた数を定められた数から引くことによって得られる数のことでした。

「定められた数」には、基数のべき乗、あるいは基数のべき乗より1だけ少ない数を使います。

[1]基数の補数：基数のべき乗から得たられた数Aを引いた数

$$n^k – A$$

[2]「基数-1」の補数（減基数の補数）：基数のべき乗から1を引いてから、さらに与えられた数Aを引いた数

$$n^k -1 – A$$

2進数の場合

[1]2の補数

「nビット整数値a」の2の補数は、$2^n – a$です。

表現範囲が4ビットなら、n=4です。

[2]1の補数

「nビット整数値a」の1の補数は、$2^n – 1 – a$です。

表現できる整数の範囲

符号を考えないとき、2進数nビットで表現できる数Nは次のとおりです。

$$0 \leq N\leq 2^{n} -1$$

一方、2の補数を負の数として表現すると考えると、1つ分のビットは符号ビットとして確保されてしまいます。つまり、残りのn-1ビットで数が表されます。n-1ビットの総数は$2^{n-1}$個です。

[1]符号ビットが0のとき

正あるいはゼロなので、ゼロからカウントして$2^{n-1}$個なので、$0 ～ 2^{n-1} -1$まで表現できることになります。

[2]符号ビットが1のとき

-1からカウントし$2^{n-1}$個の負の数を表現できるので、$-2^{n-1} ～ -1$まで表現できることになります。

以上をまとめると、2の補数を用いて負の数を表現すると、2進数nビットで表現できる数Nは次のとおりです。

$$- 2^{n-1} \leq N \leq 2^{n-1} -1$$

表現できる数の最大の桁数は？

表現できる数の範囲がわかったので、最大値もわかります。後は、桁数を知りたければ、対数を取るだけです。

[問題]負数には2の補数を用いる整数表現において、64ビットで表現できる最大の数は10進数で何桁ですか？　ただし、log₁₀2=0.301とします。

[解答]nビットで2の補数を用いて表現できる範囲は、-2^n-1～2^n-1-1の範囲です。

これから、最大値は2^n-1-1になります。

問題はこれが何桁になるかということです。

n-1=64-1=63なので、2⁶³の値の桁数を調べればよいことになります。

桁数は対数を取って、次のように計算します。

$$\log_{10} 2^{63}$$

$$=63 \times \log_{10} 2$$

$$= 63 \times 0.301$$

$$=18.963$$

小数点を繰り上げて、19桁になります。

10進数値から2の補数と1の補数を一発で計算するには

2の補数

表現範囲が4ビットとします。

正の数は普通に2進数で表現すればよいので、たとえば3は0011bになります。

負の数は2の補数で表現するので、たとえば-3は次のように計算できます（$2^n – a$にn=4、a=3を代入）。

$$2^n – a=2^4 – 3=16 – 3=13=1101b$$

4ビットの範囲で扱える整数は、負の数を含めると$-(2^3)$から$2^3-1$までになります。

つまり、-8から7までであり、計16個の整数になります。

$$-8=-2^3=1000b$$

$$-7=1001b$$

$$-6=1010b$$

$$-5=1011b$$

$$-4=1100b$$

$$-3=1101b$$

※この-3は上記と一致。

$$-2=1110b$$

$$-1=1111b$$

$$0=0000b$$

$$1=0001b$$

$$2=0010b$$

$$3=0011b$$

$$4=0100b$$

$$5=0101b$$

$$6=0110b$$

$$7=0111b$$

最上位ビットが1なら負の数になるわけです。

1の補数

「nビット整数値a」の2の補数は、$2^n – a$です。

補数は負の数の表現や減算で役立つ

補数はコンピューターサイエンスの分野で重要な概念であり、特に負の数の表現、減算において役立ちます。コンピューターの世界では2進数で数を扱うため、（2進数における）1の補数と2の補数という概念での負の数の表現について触れておきます。

例えば、1の補数の世界で-3をどう表現できるのかを調べてみます。表現範囲を4ビットとすると、10進数「3」の2進数は0011bです。これをビット反転すると1100bになります。つまり、1の補数の世界では1100bが-3に相当します。

2の補数では、負の数を表すために、正数表現に対して、否定を取ってから1を足します。2の補数の世界で、-3は1101bと表現されます。否定してから1を足したためです。

同じ-3であっても、どちらの世界かによって、表現が変わってくるわけです。

補数和

補数表現を用いると、引き算を加算で実現できるという利点があります。

「1の補数和」「2の補数和」について解説します。

2の補数和

2の補数和の方が簡単なので、こちらから説明します。

2の補数和は、コンピューター内での加算や減算を行う際に使用される方法です。減算したい場合、減算用の回路を用意する代わりに、加算用の回路を流用し、補数を得る回路を用意すればよくなります。つまり、コンピューター内部では2の補数で負の数を扱うのです。

例えば、A＝6（0110b）、B＝-3（2の補数表現：1101b）の場合、A＋B＝3（0011b）を求めたいとします。

1：加算する数の2の補数表現を求めます。

すでに「Bの2の補数表現」が与えられている場合、このステップはスキップできます。

先の例では、A＝6⇒0110b（4ビット）、B＝-3⇒1101b（これは-3の2の補数表現）になります。

2：2進数で加算します。

A（0110b）とB（1101b）を2進数で加算すると、10011bになります。

3：桁上がりした分をカットします。

結果が5ビットになりましたが、もともと4ビットで計算していたので、最上位ビット（左端の1）を捨てて、残りの4ビットを取ります。結果は0011bになります。これは10進数で「3」となります。これは期待の結果です。

1の補数和

1の補数和の計算は次のようになります。同様のAとBを使ってA＋Bを求めたいもとのします。

1：加算する数の1の補数表現を求めます。

すでに「Bの1の補数表現」が与えられている場合、このステップはスキップできます。

A＝6⇒0110b（4ビット）、B＝-3⇒1100b（これは-3の1の補数表現）になります。

2：2進数で加算します。

A（0110b）とB（1100b）を2進数で加算すると、10010bになります。

3：桁上がりした分を足します。

結果が5ビットになりましたが、もともと4ビットで計算していたので、最上位ビット（左端の1）を足します。結果は0011になります。

以上のように、「2の補数和」と「1の補数和」の計算方法は異なりますが、どちらも同じ答えを得られます。