补码的原理和有限域_int8补码

补码的计算规则很简单，在大一的计算机系统里就学过。可是其原理一直困扰着当年的我，虽然当时发现补码的正负轴对称，相加就能通过溢出回到原点。以int8为例：

x+-x=00000000=11111111+1，

所以-x=(11111111-x)+1=~x+1

这就能得到每个负数的补码的转换，由于补码符合x+-x=0，因此通过结合律使加负数的运算推广到所以元素上。比如对于z=y+x：

z+-x=y+x+-x=y

但是很明显，其实这仍然有点拍脑袋的感觉，所以这种方法看起来很巧妙，就像解一元高次方程一样，方法很巧妙，却并不是通用的。

直到后来学了群论，终于对数值计算有了大概的了解。这里想通过群论来解释一下补码的原理。

对于计算机的加法运算，这是一个有限域。有限域通俗来讲就是一个有限的集合和两个集合上封闭的运算（加法和乘法）并且符合一定的公理。为了简单一点，我们只考虑加法运算。

这个角度下，我们发现了两件事：

1. 现实中的自然数运算是在无限域上完成的，因为我们不会有溢出，可以一直加下去。

2. 计算机的自然数运算（无符号类型）是在有限域上完成的，因为会产生溢出，两个整数相加有可能会溢出并回到更小的位置，比如uint8下11111111+1=00000000

因此，我们可以得到计算机的无符号加法运算规则(⊕表示计算机的加法，以便和整数加法区分。n表示类型所能表示的最大值）：

x⊕y=(x+y) mod n

因此，这个⊕是封闭的，并且运算结果是循环的。我们记这个代数系统为({0,1,2,...,n},⊕)。显然，这是一个循环群，即超出的n的部分会从0重新开始。

这时，我们需要把无符号类型推广到整数上，那么可以找一个同构于无符号类型的有符号类型的空间，并建立两个集合的映射：

f: {0,1,2,...,2n-1} → {-n+1,...,-1,0,1,...,n}

其中，最直接的方法就是线性映射：

0 ↦ -n+1

1 ↦ -n+2

...

n-1 ↦ 0

n ↦ 1

n+1 ↦ 2

...

2n-1 ↦ n

但是我们还是希望保持尽量多的恒等映射。由于这是循环群，所以我们可以旋转一下，得到：

0 ↦ 0

1 ↦ 1

...

n-1 ↦ n-1

n ↦ n

n+1 ↦ -n+1

...

2n-1 ↦ -1

这就得到了有符号类型和无符号类型的映射关系了。

我们可以通过公式表达：

x⊕y=((x+2n)mod 2n + (y+2n)mod 2n) mod 2n 

而其中(x+2n)mod 2n便是((x+2n-1)+1) mod 2n = (~x+1) mod 2n，即源码转补码