補数表現

補数表現

補数 (complement)

 この記事では 補数 (complement) について解説します。補数は計算機理論を学ぶ上で欠かせない概念です。基本情報技術者試験などにも頻繁に登場する用語なので、プログラマーを目指す皆さんもしっかり押さえておきたいところです。

補数の定義

 「補数」なんて初めて聞くと、いかにも技術的な雰囲気がして難しそうに思えますが、実はとても簡単です。厳密な定義から始めると、簡単なことまで不必要にややこしく感じてしまうので、具体例から始めます。ひとまずは $10$ 進数で考えることにします。

 $8$ に対する $10$ の補数は $2$
 $35$ に対する $10$ の補数は $65$
 $426$ に対する $10$ の補数は $574$

 これが補数の考え方です。勘の良い人であれば、これを見ただけで理解できると思います。言い換えるとこんなふうになります。

 $8$ に足して $10$ になる数は $2$
 $35$ に足して $100$ になる数は $65$
 $426$ に足して $1000$ になる数は $574$

 初学者にとって少々混乱のもとになるのが、「$8$ に対する $10$ の補数は $2$」を、簡略して「$8$ の補数は $2$」のように書くことがある点です。しかし、この表現だと明らかに情報が足りず、$2$ 進数における「$1$ の補数」と「$2$ の補数」の意味を考えるときに混乱します。多少面倒ですが、「$a$ に対する $b$ の補数」という表現を定着させたほうが良いと思います。$b$ は基数で、$10$ 進数ならば $b=10$ です。

 補数にはもう $1$ 種類あります。
 これも具体例で考えると難しくありません。

 $8$ に対する $9$ の補数は $1$
 $35$ に対する $9$ の補数は $64$
 $426$ に対する $9$ の補数は $573$

 言い換えると次のようになります。 

 $8$ に足して $9$ になる数は $1$
 $35$ に足して $99$ になる数は $64$
 $426$ に足して $999$ になる数は $573$

 このような補数を 減基数の補数 とよびます。
 補数の一般的な定義は以下のようになります。
 

 $b$ 進数で考えるとき、$n$ 桁の自然数 $a$ に対する基数 $b$ の補数 $c$ を
 
\[c=b^n-a\tag{1}\]
と定義し、減基数 $b-1$ の補数を
 
\[c'=c-1=b^n-1-a\tag{2}\]
と定義します。

 

2の補数と1の補数

 ここから $2$ 進数で考えます。
 $10$ 進数で基数 $10$ の補数と減基数 $9$ の補数を考えたのと同じように、$2$ 進数にも「基数 $2$ の補数」と「減基数 $1$ の補数」があります。

 例として、$(10011)_2$ の補数を求めてみましょう ($10$ 進数で表すと $(19)_{10}$ です) 。$(10011)_2$ に対する $1$ の補数は、$(10011)_2$ に足して $(111111)_2$ となるような数のことです。すなわち
 
\[c'=(11111)_2-(10011)_2\tag{1}\]
によって計算できます。計算結果は $(01100)_2$ となりますが、これは引くほうの数 $(10011)_2$ の各桁の $0$ と $1$ を反転させた形となっています。これは $2$ 進数ならではの特性です。コンピュータ内部では各ビットに記録されている $0$ と $1$ を入れ替える操作に当たるので、「ビット反転」とよばれます。

 $c'$ に $(00001)_2$ を加えると、 $(10011)_2$ に対する $2$ の補数が得られます。
 
\[c=c'+(00001)_2=(01101)_2\tag{2}\]
 ビット演算で補数を使う利点は、引き算も足し算で処理できることです。一例として、引き算
 
\[28-19\tag{3}\]
を $2$ 進数で考えてみます。$28$ と $19$ をそれぞれ $2$ 進数で表すと、
 
\[\begin{align*}(28)_{10}=(11100)_2\\[6pt]
(19)_{10}=(10011)_2\end{align*}\tag{4}\]
となります。計算結果を $x$ とおくと
 
\[(11100)_2-(10011)_2=x\tag{4}\]
と表せます。左辺に補数をつくるために、両辺に $(100000)_2$ を加えます。
 
\[(11100)_2+(100000)_2-(10011)_2=x+(100000)_2\tag{5}\]
 $(100000)_2-(10011)_2$ は $(10011)_2$ に対する $2$ の補数です。さらに、この式は $1$ の補数 $(11111)_2-(10011)_2$ を使って
 
\[(11100)_2+(11111)_2-(10011)_2+(00001)_2=x+(100000)_2\tag{6}\]
と書き直せます。$1$ の補数は $0$ と $1$ を反転させればよいので、
 
\[(11100)_2+(01100)_2+(00001)_2=x+(100000)_2\tag{7}\]
となります。左辺の足し算を計算すると
 
\[(101001)_2=x+(100000)_2\tag{8}\]
となります。両辺から $(100000)_2$ を落とせば(最上位の桁を削除すると)
 
\[x=(01001)_2\tag{9}\]
が得られます。$10$ 進数で表すと $9$ です。以上をまとめると、「$a$ から $b$ を引く操作」は、「$a$ に$b$ のビット反転と $1$ を加えて最上位の桁を落とす操作」に置き換えられます。

 実際のコンピュータの固定長整数や固定小数点数演算では、数値を格納するビット数が決まっているので、すべての数を同じ桁数の数として扱います。たとえば、$8$ ビットでは、$(101)_2$ のような数であっても、空白の桁に $0$ を入れて、$(00000101)_{2}$ のように $8$ 桁に揃えます。

 コンピュータでは、数値 $a$ の負数 $-a$ を数値 $a$ に対する $2$ の補数と決めることがあります。この定義を使うと、符号を表すビットが不要となり、上で説明したように減算を加算で表現できます。たとえば、$a=(00000101)_{2}$ のとき、$-a$ はビット反転して末尾に $1$ を加えることにより、

\[-a=(11111011)_{2}\tag{10}\]
で表すことになります。