补码与带符号整数运算

设有 $n$ 位二进制容器，整数 $x$ 的取值范围是 $-2^{n-1}\le x\le 2^{n-1}-1$。$x$ 的补码编码规定为：$x\ge 0$ 时与 $x$ 的无符号二进制相同；$x<0$ 时取 $2^n+x$ 的 $n$ 位二进制。因为 $2^n+x=2^n-|x|$，负数的编码相当于从 $2^n$ 中减去它的绝对值。

补码也可以按位权读：最高位的权是 $-2^{n-1}$，其余位的权仍是正的 $2^i$，即

这解释了为什么最高位为1就代表负数，也说明最高位的权不是 $-1$ 而是 $-2^{n-1}$，这是按位读补码时最容易出错的地方。非负数的补码与无符号编码完全一致；同一串位按哪种规则解释，取决于变量的类型，而不是位串本身。

范围在负数一侧多一个数：$-2^{n-1}$ 有编码，而 $+2^{n-1}$ 没有。8位中1000 0000是 $-128$，1111 1111是 $-1$，0000 0000是0。无符号整数的位权与加法规则见二进制四则运算。

原码把最高位当符号位、其余位当绝对值。它有两个问题：0有 +0与 -0两种编码，浪费一个编码；做减法要先比较绝对值大小、再决定符号，电路无法与加法共用。

补码把这套判断省掉：0只有一种编码，且 $A-B=A+(-B)$，减法化成加法，只需要一个加法器。代价是表示范围不对称，负数比正数多一个，因为原码里 -0占的位置被 $-2^{n-1}$ 占用。

位数不足时在左侧补0再取反，取反的结果必须仍是 $n$ 位；加1产生的进位若超出 $n$ 位则丢弃。

$A-B$ 按 $A+(-B)$ 计算：把 $B$ 的 $n$ 位补码取反加一得到 $-B$，再与 $A$ 相加。结果超出 $n$ 位的最高进位被丢弃，这一步不是错误，而是模 $2^n$ 运算的自然结果。

补码加法只有同号相加才可能溢出：两个正数相加得到负数，或两个负数相加得到正数。异号相加的结果一定落在表示范围内，不会溢出。

设 $x>0$ 且 $x<2^{n-1}$，把 $x$ 写成 $n$ 位二进制 $b$，记按位取反的结果为 $\bar b$。

每一位取反后1与0互换，等价于用全1位串 $2^n-1$ 减去 $b$，所以

再加1，得

右边正是负数 $-b$ 的补码定义，因此取反加一得到的确实是 $-x$ 的编码。加1若产生超出第 $n$ 位的进位，舍弃它不影响低 $n$ 位的值，而补码本来就只保留 $n$ 位。