Loading article…
2進数の1の補数は、数値の2進表現のすべてのビットを反転（反転）して得られる値です。「1の補数」 [1]という名前は、このような反転した値を元の値に追加すると、常に「すべて1」の数値が生成されるという事実を指します（「補数」という用語は、0以外の基数に関して、相互に加算可能な逆数のペアを指します）。この数学的演算は主にコンピュータサイエンスの分野で関心を集めており、特定のコンピュータが数値を表現する方法に応じてさまざまな効果をもたらします。
1 の補数システムまたは1の補数演算は、負の数が対応する正の数の 2 進表現の逆数によって表されるシステムです。このようなシステムでは、1 の補数を計算することによって数が否定されます (正から負へ、またはその逆に変換されます)。N ビットの 1 の補数数値システムでは、-(2 N−1 -1) から 2 N−1 -1 までの範囲の整数のみを表すことができますが、2 の補数では -2 N−1から 2 N−1 -1 までを表すことができます。これは、 2 の補数と符号絶対値とともに、バイナリ コンピュータにおける負の整数の 3 つの一般的な表現の 1 つです。
1 の補数による 2 進数 表記システムは、任意の整数値のビット補数がその値の算術的負数になるという特徴があります。つまり、数値のすべてのビットを反転すると (論理補数)、0 から値を減算するのと同じ結果になります。
UNIVAC 1101、CDC 160、CDC 6600、LINC、PDP-1、UNIVAC 1107など、初期のコンピュータの多くは1 の補数演算を使用していました。 CDC 6600 の後継機種は 1980 年代後半まで 1 の補数演算を使用し続け、 UNIVAC 1107 の後継機種 ( UNIVAC 1100/2200 シリーズ) は現在でも1 の補数演算を使用していますが、現代のコンピュータの大部分は2 の補数演算を使用しています。
数値表現
正の数は、2 の補数や符号絶対値で使用されるのと同じ単純な 2 進数システムです。負の値は、対応する正の値のビット補数です。最大の正の値は、符号 (上位) ビットがオフ (0) で、他のすべてのビットがオン (1) であることによって特徴付けられます。最小の負の値は、符号ビットが 1 で、他のすべてのビットが 0 であることによって特徴付けられます。次の表は、-7 から +7 までの 4 ビット システムで可能なすべての値を示しています。
+ − 0 0000 1111 — +0と-0の両方がゼロかどうかテストするとTRUEを返すことに注意してください。 1 0001 1110 — ゼロ以外かどうかテストされた場合は FALSE になります。 2 0010 1101 3 0011 1100 4 0100 1011 5 0101 1010 6 0110 1001 7 0111 1000
基礎
2 つの値を加算するのは簡単です。最下位ビットに値を揃えて加算し、桁上がりを 1 つ左のビットに伝播するだけです。桁上がりがワードの末尾を超えると、「ラップアラウンド」したとされ、この状態は「エンドアラウンド キャリー」と呼ばれます。この状態が発生すると、ビットを右端のビットに戻して加算する必要があります。この現象は 2 の補数演算では発生しません。
0001 0110 22 + 0000 0011 3 ============ ==== 0001 1001 25
減算も同様ですが、繰り上がりではなく借用が左に伝播されます。借用がワードの末尾を超える場合、それは「ラップアラウンド」したと言われ、この状態は「エンドアラウンド借用」と呼ばれます。これが発生すると、ビットは右端のビットから減算される必要があります。この現象は、2 の補数演算では発生しません。
0000 0110 6 − 0001 0011 19 ============ ==== 1 1111 0011 −12 — エンドアラウンド借用が生成され、中間結果の符号ビットは 1 になります。 − 0000 0001 1 —結果からエンドアラウンド借用を減算します。 ============ ==== 1111 0010 −13 —正しい結果（6 − 19 = −13）
正の値のビット補数は正の値の負の値であることは簡単に証明できます。19 + 3 の計算は 19 − (−3) と同じ結果を生成します。
19に3を足します。
0001 0011 19 + 0000 0011 3 ============ ==== 0001 0110 22
19から-3を引きます。
0001 0011 19 − 1111 1100 −3 ============ ==== 1 0001 0111 23 —エンドアラウンド借用が生成されます。 − 0000 0001 1 —結果からエンドアラウンド借用を減算します。 ============ ==== 0001 0110 22 —正しい結果（19 − (−3) = 22）。
マイナスゼロ
負のゼロは、符号付きワードのすべてのビットが 1 である状態です。これは、左端のビットが 1 の場合に値が負であり、負の数は数の大きさのビット補数であるという 1 の補数の規則に従います。計算時にも値はゼロとして動作します。負のゼロを別の値に加算または減算すると、元の値が生成されます。
負のゼロを追加する:
0001 0110 22 + 1111 1111 −0 ============ ==== 1 0001 0101 21エンドアラウンドキャリーが生成されます。 + 0000 0001 1 ============ ==== 0001 0110 22 正しい結果 (22 + (-0) = 22)
負のゼロを減算する:
0001 0110 22 − 1111 1111 −0 ============ ==== 1 0001 0111 23エンドアラウンド借用が生成されます。 − 0000 0001 1 ============ ==== 0001 0110 22 正しい結果 (22 − (−0) = 22)
負のゼロは、1 の補数加算器で簡単に生成できます。同じ大きさの正と負の数を加算するだけです。
0001 0110 22 + 1110 1001 −22 ============ ==== 1111 1111 −0 負のゼロ。
数学的には常に正しい結果が生成されますが、負のゼロの副作用として、ソフトウェアは負のゼロをテストする必要があります。
マイナスゼロを避ける
加算が補数減算器で行われる場合、負のゼロの生成は問題になりません。最初のオペランドは変更されずに減算器に渡され、2 番目のオペランドは補数化され、減算によって正しい結果が生成され、負のゼロは回避されます。前の例では、22 と -22 を加算して -0 を生成しました。
0001 0110 22 0001 0110 22 1110 1001 −22 1110 1001 −22 + 1110 1001 −22 − 0001 0110 22 + 0001 0110 22 − 1110 1001 −22 =========== ==== ただし =========== ==== 同様に、 =========== === ただし ============ === 1111 1111 −0 0000 0000 0 1111 1111 −0 0000 0000 0
「コーナーケース」は、オペランドの 1 つまたは両方がゼロおよび/または負のゼロである場合に発生します。
0001 0010 18 0001 0010 18
− 0000 0000 0 − 1111 1111 −0
=========== ==== =========== ====
0001 0010 18 1 0001 0011 19
− 0000 0001 1
============ ====
0001 0010 18
+0 を減算するのは簡単です (上記のとおり)。2 番目のオペランドが負のゼロの場合は反転され、最初のオペランドの元の値が結果になります。-0 を減算するのも簡単です。結果は 2 つのケースのいずれかになります。ケース 1 では、オペランド 1 は -0 なので、結果は各ビット位置で 1 から 1 を減算するだけで生成されます。ケース 2 では、減算によりオペランド 1 より 1 大きい値と、エンドアラウンド借用が生成されます。借用を完了すると、オペランド 1 と同じ値が生成されます。
次の例は、両方のオペランドがプラスまたはマイナス 0 の場合に何が起こるかを示しています。
0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0
+ 0000 0000 0 + 1111 1111 −0 + 0000 0000 0 + 1111 1111 −0
=========== ==== =========== ==== =========== ==== ===== ====== ====
0000 0000 0 1111 1111 −0 1111 1111 −0 1 1111 1110 −1
+ 0000 0001 1
==================
1111 1111 −0
0000 0000 0 0000 0000 0 1111 1111 −0 1111 1111 −0 − 1111 1111 −0 − 0000 0000 0 − 1111 1111 −0 − 0000 0000 0 =========== ==== =========== ==== =========== ==== ===== ====== ==== 1 0000 0001 1 0000 0000 0 0000 0000 0 1111 1111 −0 − 0000 0001 1 ============ ==== 0000 0000 0
この例では、±0 のみを加算する場合の 4 つの可能な条件のうち、3 つの条件で加算器が −0 を生成することを示しています。補数減算器は、最初のオペランドが −0 で 2 番目のオペランドが 0 の場合にのみ −0 を生成します。
参照
参考文献
- ^ Knuth, Donald E. 「4.1. 位置番号システム」。『The Art of Computer Programming, Volume 2: Seminumerical Algorithms』 (第 3 版)。
細部にこだわる読者やコピー編集者は、「2 の補数」や「1 の補数」などの用語におけるアポストロフィの位置に注意する必要があります。2 の補数は 2 の単一の累乗に対して補数化されますが、1 の補数は 1 の長いシーケンスに対して補数化されます。
- ドナルド・クヌース：コンピュータプログラミングの技法、第 2 巻：半数値アルゴリズム、第 4.1 章