2の補数

2の補数（にのほすう、（英: two's complement）は、 $2$ を位取り記数法の基数とした場合の基数の補数である^[1]^[2]^[3]^[4]^[5]^[6]^{[注 1]}。すなわち、整数 $x$ との和が基数 $2$ の冪 $2 n$ となる数 $x c = 2 n - x$ のことをいう^{[注 3]}（例： $24 = 16$ について、 $5$ に対応する2の補数は $11 = 16 - 5$ ）。

数 $x$ とその2の補数 $x c$ を二進法で表せば、2の補数 $x c$ は $x$ との和が $n + 1$ 桁に繰り上がる最小の数といえる（例： $24 = 10000 2 = (1111 + 1) 2$ について^{[注 2]}、 $510 = 0101 2$ に対応する2の補数は $1110 = 1011 2 = (1111 - 0101 + 1) 2$ ）。

2の補数を得る手順は、基数の補数および減基数の補数の定義から、1の補数に $1$ を足す操作となる。1の補数は二進表示された数の各位の値（ビット）を $0$ から $1$ 、また $1$ から $0$ に置き換える操作（ビット反転）によって得られるため（例： $0101 \to 1010$ ）、2の補数はしばしば元の数をビット反転して1を足したものとして定義される。

ある数の2の補数を反数と見なせば、二進法において決まった桁数を持った数をそれぞれ非負の数と負の数に対応づけられる（#負の数の表現）。特に $n$ 桁の二進数について $0$ から $2 n -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$ である。実際、これらを足し算は以下のようになる：

{\begin{array}{lrrrrr}&&0&0&1&0\\{}+{}&&1&1&1&0\\\hline &{\cancel {1}}&0&0&0&0\end{array}}

結果は $100002 = 2 4 = 16$ になっており、 $11102$ が $00102$ の $100002$ に対する補数になっていることが確かめられる。また5桁目以降を無視し下4桁だけ取り出せば、結果は $00002$ となる。つまり、 $00102$ にその2の補数 $11102$ を足すということは $0010$ から $0010$ 自身を引くということと同じ意味を持つ。言い換えれば、 $11102$ は負数 $-2$ を表している。

引き算と補数の足し算の比較[編集]

例えば、二進数 $01012 (= 5)$ から二進数 $00112 (= 3)$ を引く場合、以下のように計算できる：

{\begin{array}{lrrrrr}&&0&1&0&1\\{}-{}&&0&0&1&1\\\hline &&0&0&1&0\end{array}}

一方、二進数 $00112$ の2の補数 $11012$ を足す計算は、以下のようになる：

{\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)$ の足し算は以下のように計算できる：

{\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)$ の足し算は期待する結果を与えない：

{\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$ 桁^{[注 4]}の二進数 $x$ とその補数 $x c$ は以下の関係を満たす^[7]：

x+x_{\mathrm {c} }=2^{n}\quad (\iff x_{\mathrm {c} }=2^{n}-x)\,.

冪 $2 n$ の倍数を $0$ と同一視すれば、上記の補数の関係は $2 n$ を法とする合同式に置き換えられる^[8]：

x+x_{\mathrm {c} }\equiv 0{\pmod {2^{n}}}\,.

これは $x$ の補数 $x c$ を $x$ の反数 $- x$ と見なすことを意味する。すなわち、数 $y$ から $x$ を引く操作は、数 $y$ と補数 $x c$ のたし算に置き換えられる^[9]^[10]：

y-x\equiv y+2^{n}-x\equiv y+x_{\mathrm {c} }{\pmod {2^{n}}}\,.

同様に反数 $- x$ のかけ算は補数の積に置き換えられる^[10]：

y\cdot (-x)\equiv y\cdot 2^{n}+y\cdot (-x)\equiv y\cdot x_{\mathrm {c} }{\pmod {2^{n}}}\,.

2の補数表現[編集]

#負の数の表現節の方法で負の数の計算を行えるが、具体的な数値計算を行うには、どの二進数（ビット列）がどの数値を表すかという対応関係を定義しなければならない。 $0$ から $2 n -1 - 1$ までの非負整数をそのまま通常の位取り記数法における二進表示、

{\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の補数表現が得られる：

{\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$ 桁^{[注 4]}の二進数における対応表を示す：

$24$ についての2の補数表現における、二進数（ビット列）と対応する数値の一覧
対応する数値	二進数	対応する数値	二進数
$0$	$00002$	-	-
$1$	$00012$	$-1$	$11112$
$2$	$00102$	$-2$	$11102$
$3$	$00112$	$-3$	$11012$
$4$	$01002$	$-4$	$11002$
$5$	$01012$	$-5$	$10112$
$6$	$01102$	$-6$	$10102$
$7$	$01112$	$-7$	$10012$
-	-	$-8$	$10002$

結局、 $n$ 桁の二進数の $k + 1$ 桁目の値を $b k \in {0, 1}$ とすれば、2の補数表現は以下のように表せる^[11]：

{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}}\,.

最上位ビット $b n -1$ は符号ビット（ふごうビット、（英: sign bit）と呼ばれ、数値の正負を決定する。すなわち、符号ビットが $0$ なら非負の数値を表し、 $1$ なら負の数値を表す。

上記の数の補数は、以下のように表せる：

\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}}\,.

等比数列の和 ${\textstyle \sum _{k=0}^{n-2}2^{k}=2^{n-1}-1}$ を用いれば、上記の補数は以下のようにも表せる^[11]：

\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}}\,.

これは結局、元の数に負符号を付けた形となっている（ただし元の数が $-2 n -1$ の場合は算術オーバーフローが発生する。オーバーフローをチェックせずラップアラウンドする場合、 $-2 n -1$ 自身へ写る^{[注 5]}）。

2の補数表現の性質[編集]

符号なし整数との一致[編集]

2の補数表現は、符号ビットが $0$ なら符号なし整数表現（つまり通常の二進法）に一致する^[14]。この性質は符号・絶対値表現や1の補数表現も持っている。

最小値と最大値の非対称性[編集]

2の補数表現において、 $n$ 桁（ $n$ 個のビット）の二進数で表せる数値の範囲は $-2 n -1$ から $+(2 n -1 - 1)$ までである^[14]（例： $n = 8$ の場合、 $-2 7 = -128$ から $+(2 7 - 1) = +127$ ）。最小値と最大値の絶対値を比較すると、負の数の範囲は正の数の範囲に対して $1$ だけ大きく、非対称になっている。そのため、最小値の補数を求めようとすると算術オーバーフローが生じる（汎整数拡張によって型が格上げされる場合は除く）。この性質は符号・絶対値表現や1の補数表現にはなく、符号・絶対値表現および1の補数表現での数値の範囲は $-(2 n -1 - 1)$ から $+(2 n -1 - 1)$ までと対称的になっている。

偶奇性の判定[編集]

2の補数表現において、整数の偶奇性を判定するには最下位の桁（最下位ビット）が偶数か奇数かを判定すればよい。すなわち二進数表示の最下位の値 $b 0$ が $0$ なら偶数であり $1$ なら奇数であることが示せる^[14]。同じ性質は符号・絶対値表現も持つが、1の補数表現においては最上位の桁（最上位ビット）の検査が必要であり、最上位ビットが $1$ なら最下位ビットが $1$ 、最上位ビットが $0$ なら最下位ビットが $0$ の場合に偶数となる。

正負の判定[編集]

2の補数で表される数は、符号ビット（最上位ビット） $b n -1$ が $0$ なら非負の値を取り $1$ なら負の値を取る^[14]。すなわち、負値か非負値かの判定は符号ビットのみから判別できる。符号・絶対値表現や1の補数表現ではゼロを表す二進数が一意でなく、符号ビットが $0$ の $+0$ と符号ビットが $1$ の $-0$ があるため、 $-0$ が許容される限り、これらの表現では符号ビットのみから負数か非負数かを判定できない。

1の補数との関係[編集]

2の補数表現において、 $-1$ は常にすべての位の値が $1$ の二進数 $111...11 2$ に対応づけられる。従って、数をビット列とみなせば、ビット列 $x$ とそのビットを反転^{[注 6]}させたビット列 $f x$ は常に以下を満たす：

x+{}^{\mathrm {f} }x\equiv -1{\pmod {2^{n}}}\,.

上記より、 $x$ の2の補数は $x c = f x + 1$ と表せる。従って減法は、

y-x\equiv y+{}^{\mathrm {f} }x+1{\pmod {2^{n}}}

と書き換えられる。ビット反転はまた1の補数を得る操作でもある。

{}^{\mathrm {f} }x\equiv -1-x\equiv \left(2^{n}-1\right)-x{\pmod {2^{n}}}\,.

右辺の $(2 n - 1) - x$ は $x$ に対する1の補数そのものであるから、ビット反転は1の補数を得る操作になっている。

元の数とのビットの一致[編集]

$x$ の $n$ 桁の二進数表示の下位 $m - 1$ 桁目まで位の値が $0$ だった場合、2の補数 $f x + 1$ を求める際、ビット反転した値が桁上りによって再び反転するため、下位 $M = min(m, n)$ ^{[注 7]}桁まで元の数とその2の補数の値が一致する。また残りの上位 $n - M$ 桁は、ビット反転 $f x$ の上位 $n - M$ 桁に一致する。例えば、補数と元の数の位の値が一致する部分に下線を引けば、 $x = 0 100$ のビット反転は $f x = 1 011$ であり、2の補数は $f x + 1 = 1 100$ となる。同様に、 $1000$ および $0000$ のビット反転はそれぞれ $0111$ , $1111$ であり、2の補数はそれぞれ $1000$ , $0000$ となる（表も参照）。

$24$ についての2の補数表現における、補数と元の数との下位ビットの一致^{[注 8]}
元の数と一致する下位ビットの桁数（ $M$ ）	1	2	3	4	4
元の数（ $x$ ）	$B 3 B 2 B 11$	$B 3 B 210$	$B 3100$	$1000$	$0000$
ビット反転（ $f x$ ）	$B 3 B 2 B 10$	$B 3 B 201$	$B 3011$	$0111$	$1111$
2の補数（ $f x + 1$ ）	$B 3 B 2 B 11$	$B 3 B 210$	$B 3100$	$1000$	$0000$

脚注[編集]

[脚注の使い方]

注釈[編集]

^ 三進法における減基数の補数（基数マイナス1の補数）も「2の補数」と呼ばれるが（補数#呼称を参照）、本項では扱わない。
^ ^a ^b 下付きの添字は位取り記数法の基数を表す。基数自身の表記には十進法を用いる。
^ 本項では数 $x$ の補数を下付きの添字 c を用いて $x c$ と表す（例： $(0111 2) c = 1001 2$ ^{[注 2]}）。添字 c は complement の頭文字である。
^ ^a ^b ここでは $n$ 桁目の値が $0$ となるものも $n$ 桁の数と呼んでいる。例えば $0001$ は 4 桁の数である。
^ 実際、Javaの java.lang.Math.abs(int) などは符号付き整数型の最小値に対して引数の値をそのまま結果として与える^[12]。また、組み込みの整数演算は算術オーバーフローを検出しない^[13]。一方でC言語やC++において、2の補数表現による符号付き整数の最小値（例：INT_MIN）に単項マイナス演算子を作用させる（例：-INT_MIN）と、汎整数拡張により結果の型がオペランドの型より大きくなる場合を除き、算術オーバーフローが発生する。符号付き整数の算術オーバーフローは未定義動作を引き起こす。算術オーバーフローの例に関しては例えば INT32-C を参照。
^ ここでビット反転とは各ビットに対する否定演算を指す。すなわち入力が $0$ なら $1$ を出力し、入力が $1$ なら $0$ を出力する。
^ $min$ はここで、与えられた数の中で最小の数を表す。
^ 上位ビットの $B$ は任意の値を表す。また、 $B$ は $B$ のビット反転である。下線で示す部分は元の数と対応する2の補数で一致する下位ビットの範囲を示している。

出典[編集]

^ JIS X 0005:2002 2002, 05.08.04 2の補数.
^ ISO/IEC 2382:2015 2015, 2. Terms and definition. 2121100. twos complement.
^ JIS X 0005:2002 2002, 05.08.02 基数の補数.
^ ISO/IEC 2382:2015 2015, 2. Terms and definition. 2121098. radix complement.
^ JIS X 0005:2002 2002, 05.08.01 補数.
^ ISO/IEC 2382:2015 2015, 2. Terms and definition. 2121097. complement.
^ 水谷『数の補数表現』, pp. 2–3, 2.2 符号ビットと 2 の補数.
^ 西村『論理（スイッチング）回路と計算』, p. 14, 2の補数表現でなぜうまく行くのか？.
^ 水谷『数の補数表現』, p. 2, 2.1 補数.
^ ^a ^b 中野『代数入門』, p. 18, 5.1 合同式, 命題5.2.
^ ^a ^b 水谷『数の補数表現』, p. 3, 2.2 符号ビットと 2 の補数.
^ Java SE & JDK API Specification, java.lang.Math#abs(int).
^ Java Language Specification, 4.2.2. Integer Operations.
^ ^a ^b ^c ^d 西村『論理（スイッチング）回路と計算』, p. 18, 2の補数表現の性質.

参考文献[編集]

日本規格協会、情報処理学会編『JIS X 0005:2002 情報処理用語（データの表現）』日本規格協会、2002年8月31日。
ISO; IEC, eds (2015-05). ISO/IEC 2382:2015 Information technology — Vocabulary. ISO/IEC
IBM, ed (1964-01-01). IBM System/360 Principles of Operation. IBM. doi:10.5555/1102026
水谷, 正大. "数の補数表現 ― コンピュータは数値をどのように保持しているのか？" (PDF). www.edu.tuis.ac.jp/~mackin. 2023年5月11日閲覧。
西村, 進. "基礎情報処理 ― 論理（スイッチング）回路と計算" (PDF). www.math.kyoto-u.ac.jp/~susumu. 2023年5月11日閲覧。
中野, 伸 (1 April 2022). "代数入門" (PDF). pc1.math.gakushuin.ac.jp/~shin. 2023年5月11日閲覧。
Seacord, Robert. "CERT C Coding Standard: INT32-C. Ensure that operations on signed integers do not result in overflow". wiki.sei.cmu.edu. 2023年5月13日閲覧。
"CERT C コーディングスタンダード: INT32-C. 符号付き整数演算がオーバーフローを引き起こさないことを保証する". www.jpcert.or.jp/sc-rules/. JPCERT/CC. 16 June 2020. 2023年5月14日閲覧。
"Chapter 4. Types, Values, and Variables ― Java Language Specification". docs.oracle.com/javase/specs/jls/. Oracle. 3 March 2023. 2023年5月13日閲覧。
"Class Math ― Java SE 20 & JDK 20". docs.oracle.com/en/java/javase/20/docs/api/. Oracle. 2023年5月13日閲覧。