補語法

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

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]

桁の数が基数である場合、その基数補数は と定義されます。実際には、基数補数は、減基数補数に 1 を加えることで簡単に得られます。つまり です。これは基数補数と同じように計算が難しいように見えますが、 は単に数字を回繰り返しただけなので、実際にはより簡単です。これは、 によるものです(幾何級数公式も参照)。これを踏まえると、数の減基数補数は、 について各桁を補数化する、つまり の各桁をから減算することで求められます。 ${\displaystyle n}$${\displaystyle y}$ ${\displaystyle b}$${\displaystyle b^{n}-y}$${\displaystyle \left(b^{n}-1\right)-y}$${\displaystyle \left(b^{n}-1\right)}$${\displaystyle b-1}$${\displaystyle n}$${\displaystyle b^{n}-1=(b-1)\left(b^{n-1}+b^{n-2}+\cdots +b+1\right)=(b-1)b^{n-1}+\cdots +(b-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の補数と呼ばれます。他の基数における補数の命名も同様です。特にDonald Knuthは、基数補数と減基数補数を区別するためにアポストロフィの位置を使用することを推奨しています。この用法では、4の補数は基数4の数値の基数補数を指し、4の補数は基数5の数値の減基数補数を指します。ただし、基数が明らかな場合 (ほとんどの場合) は区別は重要ではなく、アポストロフィの位置の微妙な違いは一般的な方法ではありません。ほとんどの筆者は1の補数と9の補数を使用し、多くのスタイルマニュアルではアポストロフィを省略して 1の補数と 9の補数 を推奨しています。

10 進数の 9 の補数は、9 を生成するためにその数字に加える必要のある数です。3 の 9 の補数は 6、7 の 9 の補数は 2 などです (表を参照)。より大きな数の 9 の補数を形成するには、各数字をその 9 の補数に置き換えます。

次の減算問題を考えてみます。

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

被減数 873 の 9 の補数を計算します。それを減数 218 に加算し、結果の 9 の補数を計算します。

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

結果の9の補数を計算します

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

218 の 9 の補数を計算すると 781 になります。218 は 3 桁なので、これは 999 か​​ら 218 を引くことと同じです。

次に、 の和と の 9 の補数をとります。 ${\displaystyle x}$${\displaystyle y}$

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

先頭の数字「1」が削除され、654 になります。

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

これはまだ正しくありません。最初のステップで、方程式に 999 が追加されました。次に、先頭の 1 が削除されたときに 1000 が減算されました。したがって、得られた答え (654) は正しい答えよりも 1 少なくなります。これを修正するには、答えに 1 を追加します。 ${\displaystyle xy}$

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

1 を加えると 655 となり、元の減算問題の正解となります。1 を加える最後のステップは、最初のステップで y の 10 の補数を使用した場合は省略できます。

次の例では、減算の結果の桁数は より少なくなります。 ${\displaystyle x}$

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

最初の方法を用いると、の9の補数の合計は ${\displaystyle x}$${\displaystyle y}$

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

999990 の 9 の補数は 000009 です。先頭のゼロを削除すると、目的の結果である 9 が得られます。

減数 の桁数が減数 の桁数より少ない場合、2 番目の方法では先頭にゼロを追加する必要があります。これらのゼロは、補数を取るときに先頭の 9 になります。例: ${\displaystyle y}$${\displaystyle x}$

  48032 [x]
- 391 [年]

書き換えられる

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

00391 をその 9 の補数に置き換えて 1 を加えると、合計は次のようになります。

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

先頭の 1 を削除すると、正解は 47641 になります。

補数の方法は、各ビットを反転する (「0」を「1」に変更、またはその逆) ことで 1 の補数を簡単に取得できるため、2 進数 (基数 2) で特に便利です。1 を加算して 2 の補数を取得するには、最下位ビットへの繰り上がりをシミュレートします。例:

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

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

  0110 0100 [×]
+ 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」の数字はありません。たとえば、(10 進数で) ${\displaystyle x-y+b^{n}}$${\displaystyle b^{n}}$

  185 [x]
- 329 [年]

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

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

この時点では、減算 (この場合は 1000) によって計算を完了する簡単な方法はありません。先頭の 1 を単純に無視することはできません。予想される答えは -144 ですが、これはそれほど外れたものではありません。856 はたまたま 144 の 10 の補数です。この問題は、いくつかの方法で対処できます。 ${\displaystyle b^{n}}$

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

補数の方法は、ギアを逆方向に回す代わりに、多くの機械式計算機で使用されていました。例:

• パスカルの計算機には結果の数字が 2 セットあり、黒いセットは通常の結果を表示し、赤いセットはその 9 の補数を表示していました。水平のスラットを使用してこれらのセットの 1 つを覆い、もう 1 つを露出させました。減算を行うには、赤い数字を露出させて 0 に設定します。次に、被減数の 9 の補数を入力します。一部のマシンでは、補数の内部ホイールを使用して被減数をダイヤルインすることでこれを行うことができました (つまり、被減数の 9 の補数を頭の中で決定する必要はありません)。補数ウィンドウ (赤いセット) にそのデータを表示することで、オペレーターは被減数の 9 の補数の 9 の補数、つまり被減数を見ることができます。次に、スラットを動かして黒い数字 (被減数の 9 の補数を表示) を露出させ、ダイヤルインして減数を加算しました。最後に、オペレーターは正しい答えを読むためにスラットを再度動かさなければなりませんでした。
• コンプトメーターでは、各キーに通常の数字とともに、9 の補数の数字が小さい文字で印刷されていました。減算を行うには、オペレーターは減数から 1 を頭の中で減算し、小さい数字を使用して結果を入力する必要がありました。補数を計算する前に 1 を引くことは、後で 1 を加えることと同じなので、オペレーターは減数の 10 の補数を効果的に加算することになります。オペレーターは、答えの一番左の数字に対応する「減算カットオフ タブ」も押し続ける必要がありました。このタブは、結果から最初の 1 を削除するコンプトメーターの方法である、繰り上がりがタブを越えて伝播するのを防ぎます。^[2]
• Curta計算機は減算に補数法を採用し、これをユーザーから隠蔽することに成功しました。数値は、機器の側面にある数字入力スライドを使用して入力されました。各スライドの数値は、回転する「エシュロン ドラム」(別名「ステップ ドラム」) のカムと噛み合うギア機構によって結果カウンターに加算されました。ドラムは、機器上部のクランクを使用して回転しました。クランクを回すと各桁が遭遇するカムの数は、その桁の値によって決まりました。たとえば、スライドが「6」の位置に設定されている場合は、その位置に対応する 6 つのカムの列がドラムの周囲に出現します。減算の場合は、ドラムを回転する前に少しずらし、別のカムの列を所定の位置に配置します。この別の列には、桁の 9 の補数が含まれています。したがって、加算用にあった 6 つのカムの列には、3 つのカムの列ができました。シフトされたドラムは、結果に 1 を加える追加のカムも 1 つ噛み合わせました (補数法に必要なため)。結果レジスタの最上位桁を超えて実行される、常に存在する 10 の補数の「オーバーフロー 1」は、事実上破棄されました。

符号付き数値の表現方法に関係なく、デジタル コンピューターでは補数法がよく使用されます。ただし、必要な回路は表現方法によって異なります。

• 2 の補数表現を使用する場合、減算では減数のビットを反転し、右端のビットにキャリーを設定することだけが必要です。
• 1 の補数表現を使用するには、減数のビットを反転し、最上位ビットのキャリー出力を最下位ビットのキャリー入力に接続する必要があります (エンドアラウンドキャリー)。
• 符号絶対値表現を使用する場合は、減算された値の符号ビットを補数化して加算するだけで済みますが、加算/減算ロジックでは、符号ビットを比較し、入力が異なる場合はその 1 つを補数化し、エンドアラウンドキャリーを実装し、最上位ビットからのキャリーがない場合は結果を補数化する必要があります。

補数の方法は、会計帳簿が手書きで書かれていたときに、誤りを訂正するために使用されました。会計士は、数字の列からエントリを削除するために、減算する数字の 10 の補数を使用して新しいエントリを追加できます。このエントリの数字の上にバーが追加され、特別なステータスが示されます。その後、数字の列全体を加算して、修正された結果を得ることができます。

合計を補数にすると、1 をその通貨の基数の整数乗で累乗した単一の単位の通貨から購入してお釣りを出すレジ係にとって便利です。10 進法の通貨の場合、これは 10、100、1,000 などになります (例: 10 ドル紙幣)。

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

• クルタ