2の補数

ウィキペディア

2の補数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/20 08:17 UTC 版)

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の補数表現（にのほすうひょうげん、（英: two's complement representation）または2の補数表記（にのほすうひょうき、（英: two's complement notation）と呼ばれる（#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 を表していることが分かる。

算術オーバーフローの例

足し算の結果、算術オーバーフローが起きることがある。

例えば、二進数 0101₂ (= 5) と二進数 0011₂ (= 3) の足し算は以下のように計算できる：

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

結果は 1000₂ となるが、これは2の補数表現において負の整数 −8 に対応し、通常の足し算で期待される結果 5 + 3 = 8 と一致しない。

同様に、二進数 1101₂ (= −3) と二進数 1010₂ (= −6) の足し算は期待する結果を与えない：

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

結果は 0111₂ (= 7) となり、通常の足し算で期待される結果 (−3) + (−6) = −9 と一致しない。

負の数の表現

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

最小値と最大値の非対称性

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

偶奇性の判定

2の補数表現において、整数の偶奇性を判定するには最下位の桁（最下位ビット）が偶数か奇数かを判定すればよい。すなわち二進数表示の最下位の値 b₀ が 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₂ に対応づけられる。従って、数をビット列とみなせば、ビット列 x とそのビットを反転^{[注 6]}させたビット列 ^fx は常に以下を満たす：

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

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

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

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

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

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

元の数とのビットの一致

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

2⁴ についての2の補数表現における、補数と元の数との下位ビットの一致^{[注 8]}

元の数と一致する下位ビットの桁数（M）	1	2	3	4	4
元の数（x）	B3B2B11	B3B210	B3100	1000	0000
ビット反転（fx）	B3B2B10	B3B201	B3011	0111	1111
2の補数（fx + 1）	B3B2B11	B3B210	B3100	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言語やC++において、2の補数表現による符号付き整数の最小値（例：INT_MIN）に単項マイナス演算子を作用させる（例：-INT_MIN）と、汎整数拡張により結果の型がオペランドの型より大きくなる場合を除き、算術オーバーフローが発生する。符号付き整数の算術オーバーフローは未定義動作を引き起こす。算術オーバーフローの例に関しては例えば INT32-C を参照。
6. ^ ここでビット反転とは各ビットに対する否定演算を指す。すなわち入力が 0 なら 1 を出力し、入力が 1 なら 0 を出力する。
7. ^ min はここで、与えられた数の中で最小の数を表す。
8. ^ 上位ビットの B は任意の値を表す。また、B は B のビット反転である。下線で示す部分は元の数と対応する2の補数で一致する下位ビットの範囲を示している。

出典

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.
14. ^ ^{a b c d} 西村『論理（スイッチング）回路と計算』, p. 18, 2の補数表現の性質.

参考文献

• 日本規格協会、情報処理学会 編『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の補数
• 整数型
• ブースの乗算アルゴリズム

ウィキペディア小見出し辞書

2の補数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/18 17:58 UTC 版)

「コンピュータの数値表現」の記事における「2の補数」の解説

最近のコンピュータでは2の補数表現が広く使われている。2の補数は、ビット毎のNOT演算を施した後に1を加算することで得られる。例えば、 0101 = +51011 = −5 したがって、 0000 = 十進 0 1000 = 十進 −8 0001 = 十進 1 1001 = 十進 −7 0010 = 十進 2 1010 = 十進 −6 0011 = 十進 3 1011 = 十進 −5 0100 = 十進 4 1100 = 十進 −4 0101 = 十進 5 1101 = 十進 −3 0110 = 十進 6 1110 = 十進 −2 0111 = 十進 7 1111 = 十進 −1 この方式では整数であれば、16ビットで −32768 から 32767 の範囲、32ビットでは −2147483648 から 2147483647 の範囲を表現する。 2の補数の利点は、加減算かつオーバーフローを考えない範囲に結果が収まるような限りであれば、符号を気にせず符号無しの整数と同様に扱える点である。 例えば、5 + (−5) は以下のようになる。 0101 +1011 10000 ここで、数値は4ビットで表しているので、演算結果も4ビットでなければならず、したがって先頭の1は捨てられ、結果として期待した通りの0が得られる。 演算において符号を気にする必要がないのは、2n を法とした合同式になっているためである。例えば、15 ≡ −1 (mod 16) である。コンピュータは一般に固定のビット数で数値を表すので、法が一定であり理想的である。2の補数表現と符号なし表現の違いは、大小比較方法と表示方法である。 2の補数表現の唯一の奇妙な点として、表現可能な最も小さい数（16ビットなら −32768）の2の補数をとると自分自身になる点が上げられる。しかし、それが問題となることは滅多に無い。むしろ、符号無しの場合にオーバーフローになる演算が、2の補数表現ではごくあたりまえの、0をまたいだ計算（正確には、負の整数と非負整数にまたがった計算）であることのほうが、慣れるまでは非直感的かもしれない。