# 补码与带符号整数运算

## 定义

设有 $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$，即

$$
x=-b_{n-1}2^{n-1}+\sum_{i=0}^{n-2}b_i2^i .
$$

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

|  位宽 |             表示范围             |   编码个数   |
| :-: | :--------------------------: | :------: |
|  8位 |        $-128\sim 127$        |   $256$  |
| 16位 |      $-32768\sim 32767$      |  $65536$ |
| 32位 | $-2147483648\sim 2147483647$ | $2^{32}$ |

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

## 性质

### 为什么用补码

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

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

### 求补码

1. **确定位宽**：按题目给定的位数，或按变量类型取8、16、32位。

2. **正数直接写**：最高位为0，其余位与无符号二进制相同。

3. **负数取反加一**：先写对应正数的 $n$ 位编码，按位取反，再在末位加1。

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

> [!TIP]
> **快速笔算**
>
> 求负数的补码时，从右往左找第一个1：这个1和它右边的所有0保持不变，左边的所有位取反。结果与取反加一相同，但只需要扫描一次，不必处理逐位进位。

### 补码减法

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

### 溢出判断

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

> [!WARNING]
> **进位不等于溢出**
>
> 最高位产生进位，只说明和超过了 $n$ 位，不代表结果算错。$5+(-3)$ 丢弃了进位，结果是正确的2。反过来，两个同号数相加即使最高位没有进位，也可能已经越界：8位补码中 $127+1$ 只得到 $-128$。判断溢出只看两个加数的符号与结果的符号是否矛盾。

## 证明

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

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

$$
\bar b=(2^n-1)-b .
$$

再加1，得

$$
\bar b+1=2^n-b=2^n+(-b).
$$

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

## 例子

**求 $-5$ 的8位补码**

1. **写出正数编码**：$5=(0000\,0101)_2$。

2. **按位取反**：`1111 1010`。

3. **末位加1**：`1111 1011`。

所以 $-5$ 在8位补码中存为`1111 1011`。按最高位权 $-2^7$ 回代检验：

$$
-128+64+32+16+8+0+2+1=-5 .
$$

**用快速法求 $-20$ 的8位补码**

$20=(0001\,0100)_2$，从右往左第一个1在权为 $2^2$ 的那一位。

1. **保留第一个1及其右边**：低三位`100`不变。

2. **左边全部取反**：`0001 0`取反得`1110 1`。

3. **拼接**：得到`1110 1100`。

结果与取反加一一致。`1110 1100`按无符号读是236，正好等于 $256-20$，这也印证了负数编码是 $2^n-|x|$。

**用8位补码计算 $5-3$**

把减法化成加法：$5-3=5+(-3)$。

1. **写出 $5$ 的补码**：`0000 0101`。

2. **求 $-3$ 的补码**：$3=(0000\,0011)_2$，取反得`1111 1100`，加1得`1111 1101`。

把两个编码相加：

$$
\begin{array}{rl}
0000\,0101 & (5) \\
+\;1111\,1101 & (-3) \\ \hline
1\,0000\,0010 & (258)
\end{array}
$$

两个编码按无符号相加得 $258=(1\,0000\,0010)_2$。最高位的进位落在第9位，超出8位容器，被丢弃；剩下`0000 0010`是2，与 $5-3$ 一致。

## 练习

1. $-5$ 的8位补码是 \_\_\_\_\_\_（bits）（只填0和1，不写空格）。

   答案：11111011

   $5=(0000\,0101)_2$，取反得`1111 1010`，加1得`1111 1011`。

2. 8位补码能表示的整数范围是：

   * A.  $-128\sim 127$
   * B.  $-127\sim 127$
   * C.  $-128\sim 128$
   * D.  $0\sim 255$

   答案：A

   范围是 $-2^{n-1}\sim 2^{n-1}-1$，8位即 $-128\sim 127$。负数多出的那一个编码是`1000 0000`。

3. 用8位补码计算 $3-5$，结果的十进制值是 \_\_\_\_\_\_（value）。

   答案：-2

   $3$ 的补码是`0000 0011`，$-5$ 的补码是`1111 1011`。相加得`1111 1110`，按补码读是 $-2$。

4. 下列8位补码加法中，会溢出的是：

   * A.  $100+100$
   * B.  $(-100)+(-100)$
   * C.  $100+(-100)$
   * D.  $127+1$

   答案：A、B、D

   $200$ 与 $-200$ 都超出 $-128\sim 127$；$127+1=128$ 同样越界。$100+(-100)=0$ 在范围内，不溢出。

5. $-20$ 的8位补码是 \_\_\_\_\_\_（fast-bits）（只填0和1，不写空格）。

   答案：11101100

   用快速法：$20=(0001\,0100)_2$，保留第一个1及其右边的`100`，左边`0001 0`取反得`1110 1`，拼成`1110 1100`。

## 交互探索

交互演示：同一组位，为什么会有两个值？。切换八个二进制位，对照无符号整数与八位补码的解释。 请在站点操作演示。