LeetCode 371 Sum of Two Integers を解く上で、Python3での負の整数のビット表現と~演算子の演算結果が、2の補数との関連でわかりづらかったので整理してみた。
2の補数
補数（基数の補数）というのは元の数に足したときに桁上がりする「最小」の数のことを指す。
10進数の場合の10の補数は、6に対して4、66に対して34。
2進数の場合の2の補数は、1に対して1、110に対して10。
また2の補数は、負の数を2進数で表す際に用いられる方法。先頭ビット（左端）が「1」である場合に、負の数を表す。
2進数の場合、元の数に足したときに桁上がりする「最小」の数は、各ビットを反転させて1を加えれば計算できる。4ビットの2進数の場合、0100(10進数で4)の2の補数は、ビットを反転して1011、それに1を加えると1100（10進数で-4）となる。
補数表現というのはマイナスを使わずに負の数を表現できる、つまり「引き算を足し算で表現できる」ということ。
2の補数は以下のようにも計算できる。補数は元の数に足したときに桁上がりする「最小」の数なので、4ビットの補数を考える場合には、桁上がりした結果の最小値 $2^4$（2進表現で10000）との差分を求めると2の補数になる。
10000 - 0100 = 1100
逆に、2の補数を元の数と加算すると
0100 + 1100 = 10000
となり、結果の10000の4ビットから溢れた５桁目の1を取って0000となる。
10進数での計算、
4 + (-4) = 0
と同等となる。
例えば、7 - 4 = 3
を、2進数で普通に減算すると
0111 - 0100 = 0011
これを2の補数表現を使って加算で計算すると、
0111 + 1100 = 10011
この結果の4ビットから溢れた先頭の1を取って、0011となり10進数では3となる。
これは、以下のように式変形するとわかりやすい。
0111 + 1100 = 10011
ここで、-4の2の補数表現1100は、もともと 1100 = 10000 - 0100 なので、
0111 + (10000 - 0100) = 10011
0111 + (10000 - 0100) - 10000 = 10011 - 10000
0111 - 0100 = 0011
先頭の5ビット目の1を取るのは、両辺に10000が加算されているから両辺から10000を減算するためだといえる。
下の表は4ビットの2進数と符号付き整数と符号なし整数を表にしたもの。
| 2進数 | 10進数 | 10進数 |
|---|---|---|
| 4ビット | 符号つき整数 | 符号なし整数 |
| 0000 | 0 | 0 |
| 0001 | 1 | 1 |
| 0010 | 2 | 2 |
| 0011 | 3 | 3 |
| 0100 | 4 | 4 |
| 0101 | 5 | 5 |
| 0110 | 6 | 6 |
| 0111 | 7 | 7 |
| 1000 | -8 | 8 |
| 1001 | -7 | 9 |
| 1010 | -6 | 10 |
| 1011 | -5 | 11 |
| 1100 | -4 | 12 |
| 1101 | -3 | 13 |
| 1110 | -2 | 14 |
| 1111 | -1 | 15 |
~演算子（ビット反転）
~演算子（ビット反転）は整数の各ビットを反転する。例えば上の表の符号付き整数で、4(0100)のビット反転は-5(1011)。
Python3では~演算子で反転する際に、オペランドが正数だと、値の先頭が無限個の符号ビット「0」で埋めたもの(...00000100)とみなされるので1、反転した結果の値の先頭はそれが全て反転された無限個の符号ビット「1」で埋めたもの(...11111011)とみなされる。演算結果は符号ビットが「1」の負数-5として出力される。
print(~4)
# -5
また、ビット反転結果は元の数の1の補数（減基数の補数）と同じ。1の補数は元の数に足して桁上がりを起こさない最大の数。4ビットで桁上がりをしないためには、加算して1111になるように元の数の各桁が1ならば0、0ならば1と反転すればよいので、結局ビット反転することと同じになる。
0100 + 1011 = 1111
この場合、1011より1多いと桁上がりして10000となるので、0100に足して桁上がりを起こさない最大の数は1011。また、1011より1多い1100は桁上がりする最小の数なので0100の2の補数。
このように、1の補数は2の補数より1少ない。そこで元の値をxとすると、xの2の補数は-xなので、1の補数はそれより1少ない-x-1となる。~xはxの1の補数と同じなので、~xも-x-1 = -(x+1)となる値を返す。2
x = 4 のときに、~xは -(x+1) = -5となる。
負数のビット表現
Python3で10進数の負数をbin()で2進数の文字列に変換すると、2の補数形式ではなく絶対値にマイナス符号が付いた形で返される。bin(-5)は0b1011とはならず、-0b101と出力される。
print(bin(-5))
# -0b101
Python3のint型には上限、下限がなく、上の桁が無限個の符号ビット（0もしくは1）となる想定であるため1、負数の2進数はそのままでは無限個の符号ビット1があることになり出力する場合に表現できない。そのため、負数をより短い表現で済むように、負数の2の補数に-1を掛けた値 (符号反転)で表現している。この場合、負数の2の補数は当該負数の絶対値に等しい。1011(-5)の2の補数は0101(5)で、それに-1を掛けて-101(-5)と出力する。このように2の補数表現ではなく、マイナスを使って負数を表現する。
負数の2の補数表現文字列
負数の2の補数表現の文字列を取得するには、表現する桁数を限定する必要がある。4bitなら0xf(0b1111)、8bitなら0xff(0b11111111)、16bitなら0xffff(0b1111111111111111)のように、必要なビット桁数の最大値との論理積(AND)を取る。
print(bin(-5 & 0b1111))
# 0b1011
print(bin(-5 & 0b11111111))
# 0b11111011
2の補数の数値リテラル
また、Python3で数値リテラルで2の補数を与えても、2の補数とはみなされず正の整数として扱われる。例えば4ビットの数値リテラルの場合、0b1011の10進表現の出力は11となり、-5にはならない。
x = 0b1011
print(x)
# 11
これは数値リテラルの4ビットより上位のビットが全て0とみなされて、正の整数となるため。（上の表の符号なし整数列を参照）
この場合、以下のようにすると2の補数として解釈されるので、負数として扱われる。
~(x ^ 0b1111)
1011と1111との排他的論理和は、1011のビットを反転するので0100となる。さらに~演算子で再度ビット反転して元の1011となるので、単に元に戻しているだけのようにみえる。
しかし、~演算子で反転する際にオペランド0100の4ビットより上位のビットが無限個の符号ビット「0」で埋めたもの(...00000100)とみなされるので1、反転された結果の1011の上位ビットも反転して全て「1」(...11111011)になり、符号ビットが「1」の2の補数になるので、負数-5として出力される。
print(~(x ^ 0b1111))
# -5
与えられた数値リテラルの桁数が増えても同様である。