理解补码
补数
在数学和计算机科学中，补数是一种编码技术，使得计算正数和负数的加法可以使用相同的机制。
整数的常见补码方案有两种：
假设对于基数为r长度为n的整数范围，某个负数-y：
- 基数补数(radix complement)：
r^n-y。 - 减一基数补数(dimished radix complement)
r^n-1-y。r^n-1是一个每位的值都是r-1，共n位的数，所以减一基数补数比较好计算。
在十进制系统中，基数补数成为‘十补数’，减一基数补数成为‘九补数’；类似的，二进制系统中，分别成为‘二补数’和‘一补数’；其他进制以此类推。
统一正负数的加法运算
依然考虑基数为r长度为n的整数范围。
我们下面以小写字母a，b代表整数，对应大写字母A代表该数值的补码表示对应的无符号数数值。令M=r^n, N=M-1。
那么，如果a>=0, 有A=a；如果a<0, 有A=M+a
假设a b都是正整数，使用两种基数补数计算，可以把负数的加法转换成正数加法和求补数的组合：
- 减一基数补数：
因为
a+(-b) = N-((N-a)+b)，把a-b转换成了三步，每个步骤只有加法运算或(减一基数)补数运算：- 计算a的补数A；
- 计算A+b，设为C；
- 计算C的补数
类似地，
(-a)+(-b) = (N-(a+b))+N。 - 基数补数：
因为
a+(-b) = a+(M-b)-M，同样把a-b转换成三步：- 计算b的补数B；
- 计算a+B，设为C；
- 计算C-M。
类似地，
(-a)+(-b) = (M-a)+(M-b)-2M。
计算机中的应用
补码与反码
补码与反码分别是二进制中的‘二补数’与‘一补数’。当代计算机处理器都是使用补码来表示整数。
负数补码的计算：
- 使用反码计算：负数绝对值按位取反后加1
- 直接计算：n位的有符号数，负数(-a)补码对应的无符号数为
2^n - a
补码统一正负数加法证明
在x86架构中，在指令级别有符号数与无符号数没有区别。
对于n位整数，它可能的取值范围是0~2^-1。以下我们区分编码和编码对应的值。
假设整数位数为8位，那么对于编码0xFF，如果以无符号数解释的值就是256，如果以有符号数解释的值就是-1。
我们把n位整数的编码空间切分为R1和R2两部分，n位整数相加的取值范围为n+1位，额外切分为R3和R4，如下表：
| R1 | R2 | R3 | R4 | |
|---|---|---|---|---|
| 编码 | 0 .. s | s+1 .. M-1 | M .. M+s | M+s+1 .. 2M-1 |
| 取值计算方法 | A+M*(x+1) | A+M*x | ||
| 8位编码切分1 (s=127) | 0 .. 127 | 128 .. 255 | 256 .. 383 | 384 .. 511 |
| 对应的有符号数取值(x=-1) | 0 .. 127 | -128 .. -1 | ||
| 8位编码切分2 (s=255) | 0 .. 255 | EMPTY | 256 .. 511 | EMPTY |
| 对应的无符号数取值(x=-1) | 0 .. 255 | EMPTY |
表中A代表某个编码，M=2^n
我们考虑编码为A和B的两个n位编码通过加法器相加的情况，令C=A+B； 下表列出了A、B、C分别在各自可能的编码范围的情况下的结果：
- 每行前三列：A、B的范围和它们所编码的值求和的预期值(EXP)，EXP取x=-1；
- 每列前4行：C所属的范围，加法器计算出来的编码(E_ACT)和对应的值(ACT)，ACT取x=-1；
- x=-1时两者的匹配情况，并加上编号。
- Invalid表示情况不可能出现(可以通过上面取值范围验证)，Y表示
x=1时EXP==ACT。
- Invalid表示情况不可能出现(可以通过上面取值范围验证)，Y表示
| C | R1 | R2 | R3 | R4 | ||
|---|---|---|---|---|---|---|
| E_ACT | A+B | A+B | A+B-M | A+B-M | ||
| ACT | A+B+M*(x+1) | A+B+M*x | A+B+M*x | (A+B-M)+M*x | ||
| A+B | EXP | x=-1 | A+B | A+B-M | A+B-M | A+B-2M |
| R1+R1 | A+B+M*2(x+1) | A+B | 1 Y | 2 | 3 | 4 Invalid |
| R1+R2 | A+B+M*(2x+1) | A+B-M | 5 Invalid | 6 Y | 7 Y | 8 Invalid |
| R2+R2 | A+B+M*2x | A+B-2M | 9 Invalid | 10 | 11 | 12 Y |
x=-1时，存在不同的取值策略：
- 无符号数加法：R2和R4为空；可能出现的结果：
- 1：正确结果；
- 3：溢出；
- 有符号数加法：可能出现：
- 1：正+正，正确结果；
- 2：正+正，溢出；
- 7：正+负=正，正确结果；
- 6：正+负=负，正确结果；
- 11 负+负，溢出；
- 12：负+负，正确结果。
- 假设
s=245，则取值范围是[-10, 245]，与有符号数情况类似，还会出现情况3，溢出； - 假设
s=10，则取值范围是[-245,10]，与有符号数情况类似，还会出现情况10，溢出；
上文中溢出是指预期的正确结果超出了取值范围。 C属于R3和R4的情况下，E_ACT=A+B-M 是因为n位加法器直接丢弃了n+1位。这是另一种溢出。
综上所述，利用补码来编码，那么不管对于有符号还是无符号的整数加法，在没有溢出的情况下都有EXP=ACT，也就是可以得到正确的结果。
另一种证明
上节用枚举的方式证明了用采用补码方式编码的情况下，对正数和负数的加法可以统一处理。 我们可以换一种更简洁的方式来证明。
首先我们有：EXP=A+B+M*y，ACT=A+B+M*z，其中y和z根据编码A，B，A+B的不同范围会有不同的取值。
但是不管y和z的取值如何，我们知道EXP和ACT同余：EXP ≡ ACT (mod M)。
假设选取的取值范围为R，如果EXP未溢出，则有EXP ∈ R，而因为ACT是编码的取值，有ACT ∈ R。
因为R中的元素数量为M，任何两个不同元素不同余，所以我们有EXP=ACT。证毕。
符号扩展
对有符号数，可以根据最高位直接进行符号扩展。但是如果映射为不对称的范围，如[-10, 245]，最高位与符号并不对应，无法进行符号扩展。
大小比较
虽然有符号数和无符号数的加法可以统一，但是如果比较大小，两者并不能统一。例如两个8位整数编码0xff和0x00，对应有符号数为-1和0，对应无符号数为255和0。
在x86架构下，是通过标志寄存器来区分的。CMP指令会修改标志位，然后通过不同的条件转移指令来实现跳转。
自定义取值范围
如以上所展示的，如果我们只考虑加减法，对于n位整数，我们可以自定义取值范围。例如对于8位整数，可以设定取值范围为[-10，245]。那么在程序中自己按正确的值进行解析即可。例如：
#include<stdio.h>
int main(){
char a;
signed char *p1=&a;
unsigned char *p2=&a;
(*p1) = -5;
printf("%d\n", a+a);
(*p2) = 120;
printf("%d\n", a+a);
return 0;
}