補数

補数（ほすう;complement）とは、ある基数法において、ある自然数 a に足したとき桁が1つ上がる（桁が1つ増える）数のうち最も小さい数をいう。コンピュータが加算処理で正の数の減算（負の数の加算）を行う際に利点がある。

定義

b 進法において、自然数 a を表現するのに必要な最小の桁数を n としたとき、

• [math]b^n - a[/math] を      「b 進法における a に対する基数の補数（b の補数）」
• [math]b^n - a - 1[/math] を「b 進法における a に対する減基数の補数（b - 1 の補数）」

という。

例えば、10進法において、自然数 61 に対する基数 10 の補数は [math]10^2 - 61 = 39[/math] である。また、2進法において、自然数 [math]10010_2 (= 18_{10})[/math] に対する基数 2 の補数は [math]2^5 - 18 = 1110_2 (= 14_{10})[/math] である。

定義したように考えると、a の基数の補数と a とを足すと、桁数が1つ増える最小の自然数（[math]= b^n[/math]）となり、a の減基数の補数と a とを足すと、桁数が増えない最大の自然数（[math]= b^n - 1[/math]）となる。

基数 b が文脈上明らかなときには、「b 進法における」という表現はしばしば省略される。

しかし、基数が明らかでないときに省略すると、「[math]\beta[/math] の補数」と表現した場合、[math](\beta + 1)[/math] 進法における減基数の補数と [math]\beta[/math] 進法における基数の補数のいずれを指すのか曖昧になる（これらの値は必ずしも等しくない）。例えば、単純に「9の補数」と表現すると、「10進法における減基数（としての9）の補数」なのか「9進法における基数（である9）の補数」なのか判別できない。

一方、「基数の補数」や「減基数の補数」という用語を用いればこのような意味での曖昧さはない。

英語であれば、例えば nines' complement と nine's complement のように書き分けて一応の区別が可能（Knuth の文献を参照）である。

補数を利用した減算

補数を利用すると、正整数の減算を加算処理で行うことができる。

以下に、10 進 5 桁の減算 [math]52934 - 38917 = 14017[/math] を、補数を用いて加算処理に置き換えた例を説明する。被減数を x、減数を y とし、減算結果を [math]x - y \equiv z[/math] とする。

• 減数 y の減基数の補数を求める。この計算は、各桁について補数を求めればよいので桁借りが発生せず、簡単に行うことができる。

[math] \begin{align} y' & \equiv (10^5 - 1) - y \end{align} [/math]

[math] \Longrightarrow \left[\quad \begin{matrix} & 9 & 9 & 9 & 9 & 9 \\ - & 3 & 8 & 9 & 1 & 7 \\ \hline & 6 & 1 & 0 & 8 & 2 \\ \end{matrix} \quad\right] [/math]

• 減数 y の基数の補数を求める。これは減基数の補数 [math]y'[/math] に 1 を加えるだけである。

[math] \begin{align} y'' & \equiv 10^5 - y \\ & = y' + 1 \\ \end{align} [/math]

[math] \Longrightarrow \left[\quad \begin{matrix} & 6 & 1 & 0 & 8 & 2 \\ + & & & & & 1 \\ \hline & 6 & 1 & 0 & 8 & 3 \\ \end{matrix} \quad\right] [/math]

• 被減数 x と 減数 y の基数の補数とを足し合わせる。このとき、最上桁の桁上がりは無視する（つまり結果から [math]10^5[/math] を減ずる）。

[math] \begin{align} z & \equiv x - y \\ & = x + y'' - 10^5 \\ \end{align} [/math]

[math] \Longrightarrow \left[\quad \begin{matrix} & 5 & 2 & 9 & 3 & 4 \\ + & 6 & 1 & 0 & 8 & 3 \\ \hline (1)& 1 & 4 & 0 & 1 & 7 \\ \end{matrix} \quad\right] [/math]

このように、本来桁借りを考慮しなければならないような減算であっても、補数の概念を利用すれば加算処理に置き換えて計算することができる。

上に挙げたのは10進法の例であるが、これは任意の基数において成り立つ。

この性質により、負整数の表記法として基数の補数を採用すると、最上位桁からの桁上がり（桁あふれ・算術オーバーフロー）を無視すれば、通常の加算処理で負整数の加算（つまり正整数の減算）が行えることになる。この利点のため、2の補数は多くのコンピュータで負整数の内部表現に採用されている。

計算法

自然数 a の N 進法による表記の各桁が、1 の位から順に

a₀, a₁, ..., a_{r − 1}, a_r

であるとする（ただし、a_r は 0 でないものとする）。ここで、各 b_i を次のように定義する。

b_i = (N − 1) − a_i

このとき、N進法における各桁が

b₀, b₁, ..., b_{r − 1}, b_r

であるような数 b が 「 a に対する (N − 1) の補数」である。

また、このとき b + 1 が「 a に対する Nの補数」である。

10進法での例

10 進法で 2304671 と表される数に対する補数を求める。 9 − 2 = 7, 9 − 3 = 6, 9 − 0 = 9, 9 − 4 = 5, 9 − 6 = 3, 9 − 7 = 2, 9 − 1 = 8 より、N=9の際の自然数2304671に対する補数は 7695328 である。

7695328 + 1 = 7695329 だから、N=10の際の自然数2304671に対する補数は 7695329 である。

2進法での例

2進法の場合は 1 − 1 = 0, 1 − 0 = 1 であるから、1の補数を求めるには単純に 1 と 0 を入れ替える（ビット毎の否定演算）。

2の補数を求めるには、1の補数に1を加算する。

• 2 進法で 101010110 と表される数に対する1の補数は 010101001 である。
• 2 の補数は 010101001 + 1 = 010101010 である。

参考文献

JIS X 0005:2002 情報処理用語（データの表現） 05.08

Donald E. Knuth 『The Art of Computer Programming Vol. 2 Seminumerical Algorithms Third Ed. 日本語版』 アスキー、2004年、191頁。 (ISBN 4-7561-4543-4)

関連項目

• 加算器
• 2の補数
• 符号付数値表現