補数表現

補数 (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$
 
このような補数を 減基数の補数 とよびます。補数の一般的な定義は以下のようになります。
 

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{3}\]
によって計算できます。計算結果は $(01100)_2$ となりますが、これは引くほうの数 $(10011)_2$ の各桁の $0$ と $1$ を反転させた形となっています。これは $2$ 進数ならではの特性です。コンピュータ内部では各ビットに記録されている $0$ と $1$ を入れ替える操作に当たるので、「ビット反転」とよばれます。
 
$c’$ に $(00001)_2$ を加えると、 $(10011)_2$ に対する $2$ の補数が得られます。
 \[c=c’+(00001)_2=(01101)_2\tag{4}\]
ビット演算で補数を使う利点は、引き算も足し算で処理できることです。一例として、引き算
 
\[28-19\tag{5}\]
を $2$ 進数で考えてみます。$28$ と $19$ をそれぞれ $2$ 進数で表すと、
 \[\begin{align*}(28)_{10}=(11100)_2\\[6pt](19)_{10}=(10011)_2\end{align*}\tag{6}\]
となります。計算結果を $x$ とおくと
 \[(11100)_2-(10011)_2=x\tag{7}\]
と表せます。左辺に補数をつくるために、両辺に $(100000)_2$ を加えます。
 \[(11100)_2+(100000)_2-(10011)_2=x+(100000)_2\tag{8}\]
$(100000)_2-(10011)_2$ は $(10011)_2$ に対する $2$ の補数です。さらに、この式は $1$ の補数 $(11111)_2-(10011)_2$ を使って
 \[(11100)_2+(11111)_2-(10011)_2+(00001)_2=x+(100000)_2\tag{9}\]
と書き直せます。$1$ の補数は $0$ と $1$ を反転させればよいので、
 \[(11100)_2+(01100)_2+(00001)_2=x+(100000)_2\tag{10}\]
となります。左辺の足し算を計算すると
 \[(101001)_2=x+(100000)_2\tag{11}\]
となります。両辺から $(100000)_2$ を落とせば（最上位の桁を削除すると）
 \[x=(01001)_2\tag{12}\]
が得られます。$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{13}\]
で表すことになります。