# 二进制四则运算

## 定义

$n$ 位**无符号整数**把全部位宽用于表示大小：第 $i$ 位（最低位为第0位）的权是 $2^i$，因此它表示 $0$ 到 $2^n-1$ 之间的全部整数，共 $2^n$ 个不同的值。位权与进制记号的由来见[进制转换](/knowledge/cs/data-representation/number-base-conversion/)。

|  位宽 |      最大值     | 常见对应     |
| :-: | :----------: | :------- |
|  8位 |     $255$    | 1字节      |
| 16位 |    $65535$   | 短整数      |
| 32位 | $4294967295$ | 单字（约42亿） |

下文用固定位宽书写，$(0101)_2$ 表示4位二进制数 $0101$；下标2是底数，不属于数值。

加法从最低位起逐位相加，**逢二进一**：

* $1+1=(10)_2$：本位写0，向高位进1；
* $1+1+1=(11)_2$：本位写1，向高位进1。

所以竖式中每一列的输入是“两个加数位 + 低位送来的进位”，输出是“本位和 + 向高位的进位”，一次最多进1。

## 性质

### 加法的位宽与溢出

两个 $n$ 位无符号数相加，真实和最多需要 $n+1$ 位。若真实和超过 $2^n-1$，最高位的进位在 $n$ 位容器中放不下，被直接丢弃，容器里的结果等于真实和减去 $2^n$：计数从最大值回绕到0，再继续累加。这像只能正转的里程表，走到全1之后再走一格，显示回到全0。

> [!NOTE]
> 无符号加法中，最高位产生进位就是溢出的信号。$n$ 位结果会丢弃进位；处理器是否保存进位标志，以及程序是否检查它，取决于具体指令与实现。补码加法不能照搬这条判断，见[补码与带符号整数运算](/knowledge/cs/data-representation/twos-complement/)。

### 乘法的移位相加

乘数的每一位只有0和1，所以部分积只有两种：该位为1时，把被乘数抄下来并按位左移；该位为0时，整行为0。把各行的部分积相加即得乘积。

两个 $n$ 位无符号数相乘最多需要 $2n$ 位才一定放得下，因此在 $n$ 位容器里直接存放乘积可能被截断。

### 除法的移位与相减

二进制长除法与十进制长除法相同：每轮把被除数的一位落下来，与除数比较，够除则商写1并减去除数，不够除则商写0。每一位的商只可能是0或1，所以“试商”退化成一次比较。

重复减法可以说明商和余数的含义：余数反复减去除数，能减几次商就是几。实际处理器可采用其他除法算法，不能仅据此判断具体执行代价。

## 例子

**竖式计算 $(0101)_2+(0011)_2$（4位）**

$$
\begin{array}{rl}
0101 & (5) \\
+\;0011 & (3) \\ \hline
1000 & (8)
\end{array}
$$

1. **最低位**：$1+1=10$，写0进1。

2. **次低位**：$0+1+1=10$，其中一个是低位送来的进位，写0进1。

3. **第三位**：$1+0+1=10$，同样写0进1。

4. **最高位**：$0+0+1=1$，不再产生进位。

结果 $(1000)_2=8$，与 $5+3$ 一致。

**竖式计算 $(0101)_2\times(0011)_2$**

$$
\begin{array}{rll}
 & 0101 & (5) \\
\times & 0011 & (3) \\ \hline
 & 0101 & \text{最低位为1，抄下被乘数} \\
 & 1010 & \text{次低位为1，左移一位} \\
+ & 0000 & \text{第三位为0，整行取0} \\ \hline
 & 1111 & (15)
\end{array}
$$

三行部分积分别对应乘数的低三位；乘数最高位为0，对应的一行全为0，省略不写。写的时候已经按位左移对齐，相加时按列处理即可。

乘积 $(1111)_2=15$ 仍在4位范围内。若乘数更大，部分积会超过4位，需要更宽的容器存放。

**长除法计算 $(1111)_2\div(11)_2$**

被除数 $(1111)_2=15$，除数 $(11)_2=3$。

1. **取最高两位**：$11$ 与除数 $11$ 比较，$11\ge 11$，商的最高位取1，余数 $11-11=0$。

2. **落下第三位**：余数拼成 $1$，$1<11$，这一位商取0，余数仍为 $1$。

3. **落下第四位**：余数拼成 $11$，$11\ge 11$，这一位商取1，余数 $11-11=0$。

商是 $(101)_2$，余数是0。回代 $(101)_2\times(11)_2=(1111)_2$，与被除数一致。

## 交互探索

调整两个四位无符号数，比较完整的加法结果与低四位。

交互演示：四位无符号加法何时产生进位？。改变两个四位数，比较完整结果和四位寄存结果。 请在站点操作演示。

## 练习

1. 8位无符号整数能表示多少个不同的值？最大值是多少？

   1. 不同值的个数是 \_\_\_\_\_\_（count-value）。

      答案：256

      位宽为 $n$ 时共有 $2^n$ 个编码，$2^8=256$。

   2. 最大值是 \_\_\_\_\_\_（max-value）。

      答案：255

      最小值是0，最大值是 $2^8-1=255$。

2. $(0110)_2+(0011)_2$ 的结果用4位二进制表示是 \_\_\_\_\_\_（sum）（只填0和1，不写下标）。

   答案：1001

   $6+3=9=(1001)_2$。最低位 $0+1=1$ 不进位，中间两位各产生一次进位，最高位再加上进位得1。

3. 用4位容器计算 $(1111)_2+(0001)_2$，容器中保存的结果是：

   * A.  $(0000)_2$
   * B.  $(10000)_2$
   * C.  $(1111)_2$
   * D.  $(0001)_2$

   答案：A

   真实和是 $16=(10000)_2$，需要5位。4位容器丢弃最高位的进位，只剩 $(0000)_2$，即回绕到0。

4. $(0101)_2\times(0010)_2$ 的积是 \_\_\_\_\_\_（product）（只填0和1）。

   答案：1010

   乘数 $(0010)_2$ 只有权为 $2^1$ 的那一位是1，部分积只有一行：被乘数左移一位，得 $(1010)_2=10$。

5. 用长除法计算 $(1100)_2\div(10)_2$，商和余数分别是多少？

   1. 商是 \_\_\_\_\_\_（quotient-value）（只填0和1）。

      答案：110

      $(1100)_2=12$，$(10)_2=2$，$12\div 2=6=(110)_2$。

   2. 余数是 \_\_\_\_\_\_（remainder-value）。

      答案：0

      被除数末位是0，$12$ 能被 $2$ 整除，余数为0。