2の補数

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

数 x とその2の補数 x_c を二進法で表せば、2の補数 x_c は x との和が n + 1 桁に繰り上がる最小の数といえる（例：2⁴ = 10000₂ = (1111 + 1)₂ について^{[注 2]}、5₁₀ = 0101₂ に対応する2の補数は 11₁₀ = 1011₂ = (1111 − 0101 + 1)₂）。

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

ある数の2の補数を反数と見なせば、二進法において決まった桁数を持った数をそれぞれ非負の数と負の数に対応づけられる（#負の数の表現）。 特に n 桁の二進数について 0 から 2ⁿ⁻¹ − 1（例：n = 8 なら 0 から 127）の範囲で符号なし表現と一致させたものは2の補数表現（にのほすうひょうげん）と呼ばれる（#2の補数表現）。

2の補数表現はコンピュータの分野において、(固定長)の符号付きの整数型や固定小数点数の表現に利用されている。

また2の補数表現は加算器で減算をするために使われる。

計算例

以下に#2の補数表現における計算例を示す。

補数であることの確認

例えば、4桁の二進数 0010₂ (= 2) に対する2の補数は 1110₂ である。実際、これらを足し算は以下のようになる：

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

 

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

引き算と補数の足し算の比較

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

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

 

一方、二進数 0011₂ の2の補数 1101₂ を足す計算は、以下のようになる：

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

 

5桁目以降を無視し下4桁を取り出せば、こちらも結果は 0010₂ (= 2) になり、引き算の場合と一致する。また、1101₂ は負数 −3 を表していることが分かる。

負の数の表現

2の補数を用いて、二進法で表された数（二進数）を負の整数に対応づけられる。2の補数の定義より、n 桁^{[注 4]}の二進数 x とその補数 x_c は以下の関係を満たす^[7]：

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

 

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

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

 

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

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

 

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

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

 

2の補数表現

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

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

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

2⁴ についての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 ∈ {0, 1} とすれば、2の補数表現は以下のように表せる^[11]：

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

 

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

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

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

 

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

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

 

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

2の補数表現の性質

2の補数で表される数は、対応する二進数表示の最上位の値 b_n−1 が 0 なら非負の値を取り、1 なら負の値を取る。すなわち、負値か非負値かの判定は二進数の最上位の桁を見るだけでできる。

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

${\displaystyle x+{}^{\mathrm {f} }x\equiv -1\,.}$ 

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

${\displaystyle y-x\equiv y+{}^{\mathrm {f} }x+1}$ 

と書き換えられる。

x の n 桁の二進数表示の下位 m 桁がすべて 0 だった場合、桁上りによって下位 m 桁が反転するため、その2の補数 ^fx + 1 の下位 m 桁も 0 となり、m + 1 桁目まで一致する。また2の補数の上位 n − (m + 1) 桁は、桁上りが生じないため、ビット反転 ^fx の上位 n − (m + 1) に一致する。例えば x = 0100₂ のビット反転は ^fx = 1011₂ であり、2の補数は ^fx + 1 = 1100₂ となる。同様に、1000₂ および 0000₂ のビット反転はそれぞれ 0111₂, 1111₂ であり、2の補数はそれぞれ 1000₂, 0000₂ となる。

脚注

[脚注の使い方]

注釈

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

出典

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

参考文献

• 日本規格協会、情報処理学会 編『JIS X 0005:2002 情報処理用語（データの表現）』日本規格協会、2002年8月31日。 
• ISO/IEC 2382:2015 Information technology — Vocabulary. ISO/IEC. (2015-05) 
• IBM System/360 Principles of Operation. IBM. (1964-01-01). doi:10.5555/1102026. https://dl.acm.org/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日閲覧。

関連項目

• 符号付数値表現
• コンピュータの数値表現
• 補数
• 1の補数