補数 - 暇つぶしWikipedia

補数

補数（ほすう、complement）とは、ある基数法において、ある自然数 a に足したとき桁が1つ上がる（桁が1つ増える）数のうち最も小さい数をいう。応用の一例としては、計算機械において、「ある数から、xを引く」という操作を、加算する機械（加算器）で「ある数にxの補数を足す（ただし最も上の桁からの繰り上がりを無視する）」という操作でおこなうことができる、というものがある。目次

 1 定義

 2 補数を利用した減算

 3 計算法

 3.1 10進法での例

 3.2 2進法での例

 4 参考文献

 5 関連項目

 定義

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

b n − a {\displaystyle b^{n}-a} を「b 進法における a に対する基数の補数（b の補数）」

b n − a − 1 {\displaystyle b^{n}-a-1} を「b 進法における a に対する減基数の補数（b - 1 の補数）」

という。

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

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

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

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

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

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

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

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

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

y ′ ≡ ( 10 5 − 1 ) − y {\displaystyle {\begin{aligned}y'&\equiv (10^{5}-1)-y\end{aligned}}}

⟹ [ 9 9 9 9 9 − 3 8 9 1 7 6 1 0 8 2 ] {\displaystyle \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]}

減数 y の基数の補数を求める。これは減基数の補数 y ′ {\displaystyle y'} に 1 を加えるだけである。

y ″ ≡ 10 5 − y = y ′ + 1 {\displaystyle {\begin{aligned}y''&\equiv 10^{5}-y\\&=y'+1\\\end{aligned}}}

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

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

z ≡ x − y = x + y ″ − 10 5 {\displaystyle {\begin{aligned}z&\equiv x-y\\&=x+y''-10^{5}\\\end{aligned}}}

⟹ [ 5 2 9 3 4 + 6 1 0 8 3 ( 1 ) 1 4 0 1 7 ] {\displaystyle \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]}

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

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