なぜ -~n = (n+1) となるのか

Pythonゴルフテク(AtCoder)を読んだ。

目から鱗のテクニックが目白押しだった。

その中で個人的に引っかかった -~n = (n+1)について調べた。

なぜビット反転したものに-1をかけると(n+1)と等しくなるのか

ここが一番の謎だった。

結論から言うと、

ビット反転させたものは、符号が反転し、絶対値が1つ増える性質がある

から。

Pythonでのビット反転(ビットNot)

Pythonは言語仕様的に整数の桁数に制限を設けていない。

そのため、Notの計算を下記のような計算で行っているとのこと。

~n = -(n+1)

(ビットNOT)

もうこれが答えだけれども、もうちょっと噛み砕いてみる。

これはどういうことかというと、10進数の世界でn+1した後に符号を反転させているということ。

2の補数を理解する (1)の「符号付き整数を2の補数によって表現する」にある表が分かりやすい。

2進数表記	符号付き10進数
1111	-1
1110	-2
1101	-3
1100	-4
1011	-5
1010	-6
1001	-7
1000	-8
0111	7
0110	6
0101	5
0100	4
0011	3
0010	2
0001	1
0000	0

(2の補数を理解する (1)をもとに作成)

負数に注目してほしい。

数字が小さくなるほどその絶対値は大きくなっている。

(-1 > -2 だけど |-1| < |-2|になっている)

いま、仮に3に注目して、これを反転させると

3(10) = 0011(2)
# 反転させる
1100(2) = -4

となる。

これが上述の、10進数の世界でn+1した後に符号を反転させている、ということ。

別の言い方をするならば、

符号付2進数の世界では、負数の国と正数の国とがあって、

お互いの国に鏡写しになった奴がいるけど、

その中身はちょうど1だけずれている

といったところだろうか。

3と-4をそれぞれ2進数に直すと、

3(10) = 0011(2)と-4(10) = 1100(2) となる。

ちょうどビットが反転した形になっているけど、その中身は|-4|-|3|=1 で、ちょうど1だけずれている。

遊んでみる

ビット反転とか2の補数とかで遊んでみる。

# 整数を4桁ビット表記する
def i2b(num):
    mask = 0b1111
    # 参考 : https://teratail.com/questions/81527
    return r'{:04b}'.format(num&mask)

# 実験対象
n = 13  # 1101
        # → 0010 (ビット反転)
        # → 0011 (2の補数表現)
print(i2b(n))  # 1101

# ビット反転
not_n = ~n
print(i2b(not_n))  # 0010
                   # 確かに反転している
print(not_n)  # -14
              # 確かに-(n+1)になっている

# ついでに、2の補数にしてみる
minus_n = not_n + 1
print(i2b(minus_n)) # 0011

# おまけで、元数と2の補数を足してみる
plus_result = n + minus_n
print(i2b(plus_result))  # 0000
                         # 確かに0になった

ビット反転の性質ならば、Python以外でもできるはず。

using System;
using System.Linq;
using System.Collections.Generic;

static class Program {
    static void Main() {
        Int32 n = "01101".FromBit();  
        Console.WriteLine($"~n == -1 * (n+1) => {~n == -1 * (n+1)}");
        Console.WriteLine($"{n} => {n.ToBit(4)}");
        Console.WriteLine($"{~n} => {(~n).ToBit(4)}");
        Console.WriteLine($"{{-~n}} == {{-(-(n+1))}} => {-1*~n==-(-(n+1))}");
        Console.WriteLine($"{{-~n}} - {{n}} => {-~n - n}");
    }

    public static string ToBit(this int n, int digits=4){
        List<char> chList = new List<char>();
        string _ret = Convert.ToString(n,2);
        int len = _ret.Length;
        for(int i=0;i<digits;i++){
            if (i >= len) {
                chList.Add('0');
                continue;
            }
            chList.Add(_ret[(len-1)-i]);
        }
        chList.Reverse();
        return new String(chList.ToArray());
    }

    public static int FromBit(this string bit) {
        int len = bit.Length;
        int ret = 0;
        for(int i=0;i<len;i++){
            ret += (1<<i) * (bit[(len-1)-i] == '1' ? 1 : 0);
        }
        return ret;
    }
}

-~nの正体

ビット反転が「10進数の世界でn+1した後に符号を反転させている」に対応する操作なら、

さらに符号を反転させれば、1だけ増えることになるよね。

あるいは、

-~n = -(~n) = -(-(n+1)) = (n+1)

ということだった模様。