補数法

数学や計算機科学において、補数法は、正負の整数の対称的な範囲を、その範囲全体で同じ加算アルゴリズム（またはメカニズム）を使用できるように符号化する手法です。与えられた桁数に対して、可能な数の表現の半分は正の数を符号化し、残りの半分はそれぞれの加法逆数を表します。互いに加法的な逆数のペアは補数と呼ばれます。したがって、任意の数の減算は、その補数を加えることによって実現されます。任意の数の符号の変更は、その補数を生成することによって符号化され、これは非常に単純で効率的なアルゴリズムで実行できます。この方法は機械式計算機で一般的に使用され、現代のコンピュータでもまだ使用されています。基数 補数の一般化された概念（以下で説明）は、ミディの定理など、数論においても価値があります。

10進数で表された数の9の補数は、各桁をその桁から9を引いた数に置き換えることによって得られます。10進数y（減数）から別の数x（被減数）を引くには、次の2つの方法があります。

最初の方法では、xの9の補数をyに加えます。そして、得られた結果の9の補数を生成することで、目的の結果を得ます。

2番目の方法では、 yの9の補数をxに加え、その合計に1を加えます。そして、結果の一番左の桁「1」を捨てます。一番左の「1」を捨てることは、固定桁数の電卓やコンピュータでは特に便利です。なぜなら、その「1」の格納場所がないため、計算中に単純に失われるからです。9の補数に1を加えたものは、10の補数と呼ばれます。

補数法は他の基数（基数）にも拡張できます。特に、ほとんどのデジタルコンピュータでは、減算の実行、負の数を基数2または2進数で表現すること、計算のオーバーフローをテストするために使用されます。^{[ 1 ]}

の 基数補数${\displaystyle n}$-桁の数字${\displaystyle y}$基数で${\displaystyle b}$は次のように定義される。${\displaystyle b^{n}-y}$実際には、基数補数は、減数補数に 1 を加えることで簡単に得られます。減数補数は、${\displaystyle \left(b^{n}-1\right)-y}$これは基数補数と同じくらい計算が難しいように見えるが、実際にはもっと簡単である。${\displaystyle \left(b^{n}-1\right)}$単に数字です${\displaystyle b-1}$繰り返し${\displaystyle n}$2進数で 1 回。これは、

（等比数列の公式も参照）。これを知ると、各桁を に関して補数にすることで、数の減数基数補数を求めることができます。${\displaystyle b-1}$つまり、各桁を減算する${\displaystyle y}$から${\displaystyle b-1}$。

の引き算${\displaystyle y}$から${\displaystyle x}$減数基数補数を用いた操作は、次のように実行できます。減数基数補数を加算します。${\displaystyle x}$に${\displaystyle y}$取得する${\displaystyle b^{n}-1-x+y}$または同等に${\displaystyle b^{n}-1-(xy)}$これは、の減数基数補数です。${\displaystyle xy}$さらに、減数補数を取ると、${\displaystyle b^{n}-1-(xy)}$結果として、望ましい答えが得られます。${\displaystyle xy}$。

あるいは基数補数を用いると、${\displaystyle xy}$は、の基数補数を加えることによって得られる。${\displaystyle y}$に${\displaystyle x}$取得する${\displaystyle x+b^{n}-y}$または${\displaystyle x-y+b^{n}}$と仮定すると${\displaystyle y\leq x}$結果は以下以上になります${\displaystyle b^{n}}$そして先頭部分を削除する${\displaystyle 1}$結果から引くことは、${\displaystyle b^{n}}$結果として${\displaystyle x-y+b^{n}-b^{n}}$または単に${\displaystyle xy}$望ましい結果。

10進数では、基数補数は10の補数、減数補数は9の補数と呼ばれます。2進数では、基数補数は2の補数、減数補数は1の補数と呼ばれます。他の基数における補数の命名法も同様です。ドナルド・クヌースをはじめとする一部の人々は、基数補数と減数補数を区別するためにアポストロフィの位置を使用することを推奨しています。この用法では、4の補数は基数4の数の基数補数を指し、4の補数は基数5の数の減数補数を指します。しかし、基数が明らかな場合（ほとんどの場合）、この区別は重要ではなく、アポストロフィの位置の微妙な違いは一般的な慣習ではありません。ほとんどの著者は1の補数と9の補数を使用し、多くのスタイルマニュアルではアポストロフィを省略して、1の補数と9の補数を推奨しています。

10進数の9の補数とは、その数に9を加えると9になる数のことです。例えば、3の9の補数は6、7の9の補数は2、といった具合です（表を参照）。より大きな数の9の補数を求めるには、各桁をその9の補数に置き換えます。

次の引き算の問題を考えてみましょう。

 873 [x、被減数] - 218 [y、減数]

999 - 873 = 126

 126 [xの9の補数 = 999 - x] + 218 [y、減数] ————— 344 [999 - x + y]

 344 [結果] 655 [344の9の補数 = 999 - (999 - x + y) = x - y、これが正解です]

 873 [x] + 781 [yの9の補数 = 999 - y] ————— 1654 [999 + x - y]

1654 -1000 [-(999 + 1)] ————— 654 [-(999 + 1) + 999 + x - y]

 654 + 1 ————— 655 [x - y]

 123410 [x、被減数] - 123401 [y、減数]

 876589 [xの9の補数] + 123401 [y] ———————— 999990

 48032 [x] - 391 [y]

 48032 [x] - 00391 [y 先頭にゼロが付く]

 48032 [x] + 99608 [yの9の補数] + 1 ——————— 147641

補数法は、特に2進数（基数2）において有用です。なぜなら、1の補数は各ビットを反転させること（「0」を「1」に、1を「0」に）することで非常に簡単に得られるからです。2の補数を得るには、最下位ビットへの桁上がりをシミュレートすることで1を加えることができます。例：

 0110 0100 [x、100に等しい] - 0001 0110 [y、10進数で22に相当]

合計は次のようになります。

 0110 0100 [x] + 1110 1001 [y の 1 の補数 = 1111 1111 - y] + 1 [2の補数を取得するには = 1 0000 0000 - y] ——————————— 10100 1110 [x + 1 0000 0000 - y]

最初の「1」を削除すると、答えは0100 1110（10進数で78）になります。

補数法は通常、オペランドが正であり、y ≤ xという論理制約があることを前提としています。任意の整数の加算と減算は通常、符号を比較し、2つを加算するか、大きい方から小さい方を減算し、結果に正しい符号を付けることによって行われます。

x < yの場合どうなるか見てみましょう。この場合、加算後に消去する「1」の数字はありません。${\displaystyle x-y+b^{n}}$より小さくなります${\displaystyle b^{n}}$例えば、（10進数で）：

 185 [x] - 329 [y]

yを補数にして加えると次のようになります。

 185 [x] + 670 [yの9の補数] + 1 ————— 856

この時点では、引き算によって計算を完了する簡単な方法はありません。${\displaystyle b^{n}}$（この場合は1000）先頭の1を無視することはできません。期待される答えは-144ですが、これは見た目ほどかけ離れていません。856は144の10の補数です。この問題は、いくつかの方法で解決できます。

• この問題を無視してください。これは、負の数をサポートしていない計算機を使用している場合には妥当です。なぜなら、計算前に2つの被演算数を比較して正しい順序で入力できるようにし、結果が妥当であることを確認することは、人間にとって容易だからです。
• 同じ方法で1000から856を引いて、結果にマイナス符号を付けます。
• 負の数は、対応する正の数の基数補数として表します。${\displaystyle b^{n}/2}$は正とみなされ、残りは負とみなされます（そして、その大きさは基数補数を取ることで得られます）。これは、最初の桁を見ることで符号を判断できるため、偶数基数の場合に最も効果的です。たとえば、10 の補数表記では、最初の桁が 0、1、2、3、または 4 の場合は正、5、6、7、8、または 9 の場合は負になります。また、最初のビットを符号ビットとみなせるため、2 進数でも非常に効果的です。符号ビットが 0 の場合は正、1 の場合は負になります。実際、2 の補数は、ほとんどの現代のコンピュータで符号付き数を表すために使用されています。
• 最上位桁に桁上がりがない場合（x がyより小さいことを示す）、結果を反転します。これは、オペランドを比較して交換するよりもデジタル回路で実装する方が簡単です。しかし、基数補数を取るには 1 を加える必要があるため、直接行うのは困難です。幸いなことに、この加算を回避するトリックがあります。減算時に常に最下位桁に桁上がりを設定する代わりに、最上位桁の桁上がりを最下位桁への桁上がり入力として使用します（エンドアラウンドキャリーと呼ばれる操作）。したがって、y ≤ xの場合、通常は無視される最上位桁からの桁上がりが加算され、正しい結果が得られます。そうでない場合は、1 は加算されず、結果は答えの基数補数より 1 小さい値、つまり減算基数補数になります。減算基数補数を取得するには加算は必要ありません。この方法は、符号付き数値を符号と絶対値で表現するコンピュータで使用されています。

補数法は、歯車を逆回転させる方法の代替として、多くの機械式計算機で使用されていました。例えば、次のようになります。

• パスカルの計算機には、結果を表示する桁が2組ありました。黒色の桁は通常の結果を表示し、赤色の桁はその9の補数を表示していました。水平のスラットを使って一方の桁を覆い隠し、もう一方の桁を表示させました。減算を行うには、赤色の桁を表示させて0に設定します。次に、被減数の9の補数を入力します。機種によっては、補数の内側ホイールを使って被減数をダイヤルすることで（つまり、被減数の9の補数を頭の中で計算することなく）入力できるものもありました。補数表示窓（赤色の桁）にそのデータを表示すると、被減数の9の補数の9の補数、つまり被減数を見ることができました。次にスラットを動かして黒色の桁（被減数の9の補数を表示）を表示させ、ダイヤルで減数を入力します。最後に、正しい答えを読み取るために、スラットをもう一度動かす必要がありました。
• コンプトメーターでは、各キーに通常の数字とともに、9の補数を表す数字が小さな文字で印刷されていました。減算を行うには、オペレーターは減数から1を暗算で引き、その結果を小さな文字で入力する必要がありました。補数化の前に1を引くことは、後に1を加えることと同じなので、オペレーターは実質的に減数の10の補数を加算することになります。また、オペレーターは答えの左端の桁に対応する「減算カットオフタブ」を押し続ける必要がありました。このタブは、繰り上がりがそれを超えて伝播するのを防ぎ、コンプトメーターが結果の最初の1を削除する方法でした。^{[ 2 ]}
• Curta計算機は、減算に補数法を用い、その仕組みをユーザーから隠すことに成功していた。数値は、装置側面の桁入力スライドを使って入力された。各スライドの数値は、回転する「階段ドラム」（別名「ステップドラム」）上のカムを噛み合わせる歯車機構によって、結果カウンターに加算された。ドラムは、装置上部のクランクを使って回転させた。クランクを回すと、各桁が遭遇するカムの数は、その桁の値によって決まる。例えば、スライドが「6」の位置に設定されていると、その位置に対応するドラムの周囲に6つのカムが並ぶ。減算の場合、ドラムは回転させる前にわずかにずらされ、別のカムの列が位置に移動した。この別の列には、桁の9の補数が含まれていた。したがって、加算のために位置していた6つのカムの列は、3つのカムの列に変わった。シフトされたドラムは、結果に1を加算する追加のカムも作動させた（補数法に必要な処理）。常に存在する10の補数の「オーバーフロー1」は、結果レジスタの最上位桁を超えて繰り上げられるため、事実上破棄された。

小学校では、暗算に役立つ近道として、補数法が教えられることがあります。^{[ 3 ]}減算は、減数 の 10 の補数（9 の補数に 1 を加えたもの）を加えることで行います。この加算の結果は、差が正になることが明らかな場合に使用され、そうでない場合は、加算結果の 10 の補数が使用され、負としてマークされます。同じテクニックは、加算機での減算にも有効です。

• クルタ