2の補数

2の補数（にのほすう、（英: two's complement）は、2 を位取り記数法の基数とした場合の基数の補数である。すなわち、整数 x との和が基数 2 の冪 2n となる数 xc = 2n − x のことをいう（例：24 = 16 について、5 に対応する2の補数は 11 = 16 − 5）。 数 x とその2の補数 xc を二進法で表せば、2の補数 xc は x との和が n + 1 桁に繰り上がる最小の数といえる（例：24 = 100002 = (1111 + 1)2 について、510 = 01012 に対応する2の補数は 1110 = 10112 = (1111 − 0101 + 1)2）。 2の補数を得る手順は、基数の補数および減基数の補数の定義から、1の補数に 1 を足す操作となる。1の補数は二進表示された数の各位の値（ビット）を 0 から 1、また 1 から 0 に置き換える操作（ビット反転）によって得られるため（例：0101 → 1010）、2の補数はしばしば元の数をビット反転して1を足したものとして定義される。 ある数の2の補数を反数と見なせば、二進法において決まった桁数を持った数をそれぞれ非負の数と負の数に対応づけられる（#負の数の表現）。 特に n 桁の二進数について 0 から 2n−1 − 1（例：n = 8 なら 0 から 127）の範囲で符号なし表現と一致させたものは2の補数表現（にのほすうひょうげん、（英: two's complement representation）または2の補数表記（にのほすうひょうき、（英: two's complement notation）と呼ばれる（#2の補数表現）。 2の補数表現はコンピュータの分野において、固定長の符号付きの整数型や固定小数点数の表現に利用されている。 また2の補数表現は加算器で減算をするために使われる。 以下に#2の補数表現における計算例を示す。 例えば、4桁の二進数 00102 (= 2) に対する2の補数は 11102 である。実際、これらを足し算は以下のようになる： 0 0 1 0 + 1 1 1 0 1 0 0 0 0 {\displaystyle {\begin{array}{lrrrrr}&&0&0&1&0\\{}+{}&&1&1&1&0\\\hline &{\cancel {1}}&0&0&0&0\end{array}}} 結果は 100002 = 24 = 16 になっており、11102 が 00102 の 100002 に対する補数になっていることが確かめられる。また5桁目以降を無視し下4桁だけ取り出せば、結果は 00002 となる。つまり、00102 にその2の補数 11102 を足すということは 0010 から 0010 自身を引くということと同じ意味を持つ。言い換えれば、 11102 は負数 −2 を表している。 例えば、二進数 01012 (= 5) から二進数 00112 (= 3) を引く場合、以下のように計算できる： 0 1 0 1 − 0 0 1 1 0 0 1 0 {\displaystyle {\begin{array}{lrrrrr}&&0&1&0&1\\{}-{}&&0&0&1&1\\\hline &&0&0&1&0\end{array}}} 一方、二進数 00112 の2の補数 11012 を足す計算は、以下のようになる： 0 1 0 1 + 1 1 0 1 1 0 0 1 0 {\displaystyle {\begin{array}{lrrrrr}&&0&1&0&1\\{}+{}&&1&1&0&1\\\hline &{\cancel {1}}&0&0&1&0\end{array}}} 5桁目以降を無視し下4桁を取り出せば、こちらも結果は 00102 (= 2) になり、引き算の場合と一致する。また、11012 は負数 −3 を表していることが分かる。 足し算の結果、算術オーバーフローが起きることがある。 例えば、二進数 01012 (= 5) と二進数 00112 (= 3) の足し算は以下のように計算できる： 0 1 0 1 + 0 0 1 1 1 0 0 0 {\displaystyle {\begin{array}{lrrrrr}&&0&1&0&1\\{}+{}&&0&0&1&1\\\hline &&1&0&0&0\end{array}}} 結果は 10002 となるが、これは2の補数表現において負の整数 −8 に対応し、通常の足し算で期待される結果 5 + 3 = 8 と一致しない。 同様に、二進数 11012 (= −3) と二進数 10102 (= −6) の足し算は期待する結果を与えない： 1 1 0 1 + 1 0 1 0 1 0 1 1 1 {\displaystyle {\begin{array}{lrrrrr}&&1&1&0&1\\{}+{}&&1&0&1&0\\\hline &{\cancel {1}}&0&1&1&1\end{array}}} 結果は 01112 (= 7) となり、通常の足し算で期待される結果 (−3) + (−6) = −9 と一致しない。 2の補数を用いて、二進法で表された数（二進数）を負の整数に対応づけられる。2の補数の定義より、n 桁の二進数 x とその補数 xc は以下の関係を満たす： x + x c = 2 n ( ⟺ x c = 2 n − x ) . {\displaystyle x+x_{\mathrm {c} }=2^{n}\quad (\iff x_{\mathrm {c} }=2^{n}-x)\,.} 冪 2n の倍数を 0 と同一視すれば、上記の補数の関係は 2n を法とする合同式に置き換えられる： x + x c ≡ 0 ( mod 2 n ) . {\displaystyle x+x_{\mathrm {c} }\equiv 0{\pmod {2^{n}}}\,.} これは x の補数 xc を x の反数 −x と見なすことを意味する。すなわち、数 y から x を引く操作は、数 y と補数 xc のたし算に置き換えられる： y − x ≡ y + 2 n − x ≡ y + x c ( mod 2 n ) . {\displaystyle y-x\equiv y+2^{n}-x\equiv y+x_{\mathrm {c} }{\pmod {2^{n}}}\,.} 同様に反数 −x のかけ算は補数の積に置き換えられる： y ⋅ ( − x ) ≡ y ⋅ 2 n + y ⋅ ( − x ) ≡ y ⋅ x c ( mod 2 n ) . {\displaystyle y\cdot (-x)\equiv y\cdot 2^{n}+y\cdot (-x)\equiv y\cdot x_{\mathrm {c} }{\pmod {2^{n}}}\,.} #負の数の表現節の方法で負の数の計算を行えるが、具体的な数値計算を行うには、どの二進数（ビット列）がどの数値を表すかという対応関係を定義しなければならない。0 から 2n−1 − 1 までの非負整数をそのまま通常の位取り記数法における二進表示、 0 ↦ 0 2 , 1 ↦ 1 2 , 2 ↦ 10 2 , ⋮ 2 n − 1 − 2 ↦ 011 ⋯ 10 2 , 2 n − 1 − 1 ↦ 011 ⋯ 11 ⏟ n 桁 2 {\displaystyle {\begin{aligned}0&\mapsto 0_{2},\\1&\mapsto 1_{2},\\2&\mapsto {10}_{2},\\&\;\;\vdots \\2^{n-1}-2&\mapsto {011\cdots 10}_{2},\\2^{n-1}-1&\mapsto \underbrace {011\cdots 11} _{n{\text{桁}}}{}_{2}\end{aligned}}} に対応づければ、これらの数の補数として負の整数に対する2の補数表現が得られる： 2 n − 1 ≡ − 2 n − 1 ↦ 100 ⋯ 00 2 , 2 n − 1 + 1 ≡ 1 − 2 n − 1 ↦ 100 ⋯ 01 2 , ⋮ ⋮ 2 n − 2 ≡ − 2 ↦ 111 ⋯ 10 2 , 2 n − 1 ≡ − 1 ↦ 111 ⋯ 11 2 . {\displaystyle {\begin{alignedat}{2}2^{n-1}&\equiv -2^{n-1}&&\mapsto {100\cdots 00}_{2},\\2^{n-1}+1&\equiv 1-2^{n-1}&&\mapsto {100\cdots 01}_{2},\\&\;\;\vdots &&\;\;\vdots \\2^{n}-2&\equiv -2&&\mapsto {111\cdots 10}_{2},\\2^{n}-1&\equiv -1&&\mapsto {111\cdots 11}_{2}\,.\end{alignedat}}} 具体例として、n = 4 桁の二進数における対応表を示す： 結局、n 桁の二進数の k + 1 桁目の値を bk ∈ {0, 1} とすれば、2の補数表現は以下のように表せる： b n − 1 b n − 2 ⋯ b 1 b 0 ( 2 ) ↦ − b n − 1 ⋅ 2 n − 1 + ∑ k = 0 n − 2 b k ⋅ 2 k . {\displaystyle {b_{n-1}b_{n-2}\cdots b_{1}b_{0}}_{(2)}\mapsto -b_{n-1}\cdot 2^{n-1}+\sum _{k=0}^{n-2}{b_{k}\cdot 2^{k}}\,.} 最上位ビット bn−1 は符号ビット（ふごうビット、（英: sign bit）と呼ばれ、数値の正負を決定する。すなわち、符号ビットが 0 なら非負の数値を表し、1 なら負の数値を表す。 上記の数の補数は、以下のように表せる： ( b n − 1 b n − 2 ⋯ b 1 b 0 ( 2 ) ) c ↦ 1 − ( 1 − b n − 1 ) ⋅ 2 n − 1 + ∑ k = 0 n − 2 ( 1 − b k ) ⋅ 2 k . {\displaystyle \left({b_{n-1}b_{n-2}\cdots b_{1}b_{0}}_{(2)}\right)_{\mathrm {c} }\mapsto 1-(1-b_{n-1})\cdot 2^{n-1}+\sum _{k=0}^{n-2}{(1-b_{k})\cdot 2^{k}}\,.} 等比数列の和 ∑ k = 0 n − 2 2 k = 2 n − 1 − 1 {\textstyle \sum _{k=0}^{n-2}2^{k}=2^{n-1}-1} を用いれば、上記の補数は以下のようにも表せる： ( b n − 1 b n − 2 ⋯ b 1 b 0 ( 2 ) ) c ↦ b n − 1 ⋅ 2 n − 1 − ∑ k = 0 n − 2 b k ⋅ 2 k . {\displaystyle \left({b_{n-1}b_{n-2}\cdots b_{1}b_{0}}_{(2)}\right)_{\mathrm {c} }\mapsto b_{n-1}\cdot 2^{n-1}-\sum _{k=0}^{n-2}{b_{k}\cdot 2^{k}}\,.} これは結局、元の数に負符号を付けた形となっている（ただし元の数が −2n−1 の場合は算術オーバーフローが発生する。オーバーフローをチェックせずラップアラウンドする場合、−2n−1 自身へ写る）。 2の補数表現は、符号ビットが 0 なら符号なし整数表現（つまり通常の二進法）に一致する。この性質は符号・絶対値表現や1の補数表現も持っている。 2の補数表現において、n 桁（n 個のビット）の二進数で表せる数値の範囲は −2n−1 から +(2n−1 − 1) までである（例： n = 8 の場合、−27 = −128 から +(27 − 1) = +127）。最小値と最大値の絶対値を比較すると、負の数の範囲は正の数の範囲に対して 1 だけ大きく、非対称になっている。そのため、最小値の補数を求めようとすると算術オーバーフローが生じる（汎整数拡張によって型が格上げされる場合は除く）。この性質は符号・絶対値表現や1の補数表現にはなく、符号・絶対値表現および1の補数表現での数値の範囲は −(2n−1 − 1) から +(2n−1 − 1) までと対称的になっている。 2の補数表現において、整数の偶奇性を判定するには最下位の桁（最下位ビット）が偶数か奇数かを判定すればよい。すなわち二進数表示の最下位の値 b0 が 0 なら偶数であり 1 なら奇数であることが示せる。同じ性質は符号・絶対値表現も持つが、1の補数表現においては最上位の桁（最上位ビット）の検査が必要であり、最上位ビットが 1 なら最下位ビットが 1、最上位ビットが 0 なら最下位ビットが 0 の場合に偶数となる。 2の補数で表される数は、符号ビット（最上位ビット） bn−1 が 0 なら非負の値を取り 1 なら負の値を取る。すなわち、負値か非負値かの判定は符号ビットのみから判別できる。符号・絶対値表現や1の補数表現ではゼロを表す二進数が一意でなく、符号ビットが 0 の +0 と符号ビットが 1 の −0 があるため、−0 が許容される限り、これらの表現では符号ビットのみから負数か非負数かを判定できない。 2の補数表現において、−1 は常にすべての位の値が 1 の二進数 111...112 に対応づけられる。従って、数をビット列とみなせば、ビット列 x とそのビットを反転させたビット列 fx は常に以下を満たす： x + f x ≡ − 1 ( mod 2 n ) . {\displaystyle x+{}^{\mathrm {f} }x\equiv -1{\pmod {2^{n}}}\,.} 上記より、x の2の補数は xc = fx + 1 と表せる。従って減法は、 y − x ≡ y + f x + 1 ( mod 2 n ) {\displaystyle y-x\equiv y+{}^{\mathrm {f} }x+1{\pmod {2^{n}}}} と書き換えられる。ビット反転はまた1の補数を得る操作でもある。 f x ≡ − 1 − x ≡ ( 2 n − 1 ) − x ( mod 2 n ) . {\displaystyle {}^{\mathrm {f} }x\equiv -1-x\equiv \left(2^{n}-1\right)-x{\pmod {2^{n}}}\,.} 右辺の (2n − 1) − x は x に対する1の補数そのものであるから、ビット反転は1の補数を得る操作になっている。 x の n 桁の二進数表示の下位 m − 1 桁目まで位の値が 0 だった場合、2の補数 fx + 1 を求める際、ビット反転した値が桁上りによって再び反転するため、下位 M = min(m, n)桁まで元の数とその2の補数の値が一致する。また残りの上位 n − M 桁は、ビット反転 fx の上位 n − M 桁に一致する。例えば、補数と元の数の位の値が一致する部分に下線を引けば、x = 0100 のビット反転は fx = 1011 であり、2の補数は fx + 1 = 1100 となる。同様に、1000 および 0000 のビット反転はそれぞれ 0111, 1111 であり、2の補数はそれぞれ 1000, 0000 となる（表も参照）。