3.3 · 二进制运算与溢出
目标： 正确做二进制加减，并在 n 位储存中检测溢出。
二进制加法规则
跟十进制一样，只是仅有 0 和 1：
| A | B | 和 | 进位 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
有趣的是 1 + 1 = 10₂ —— 写 0，进 1。跟十进制的 5 + 5 = 10 一样。
例 · 5 + 6（4 位）
进位: 1 1 1
0 1 0 1 (5)
+ 0 1 1 0 (6)
─────────
1 0 1 1 (11)2
3
4
5
结果：1011₂ = 11₁₀。✓
例 · 9 + 7（4 位） —— 溢出！
进位: 1 1 1 1
1 0 0 1 (9)
+ 0 1 1 1 (7)
─────────
1 0 0 0 0 (16，但 5 位)2
3
4
5
4 位里结果为 0000 加一个进位输出。该进位就是溢出标志 —— 见下。
二进制减法
两种常用方法：
方法 1 · 借位（学校式）
| A | B | 差 | 借 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
1 0 0 1 (9)
− 0 1 0 1 (5)
─────────
0 1 0 0 (4) ✓2
3
4
方法 2 · 加二的补码
这就是真 CPU 干的事（见 3.4 二的补码）。把减数转成负的形式，然后相加。
A − B = A + (−B)。
什么是溢出？
溢出发生在算术结果装不下可用位数时。
对无符号 n 位数，最大可表示值是 2ⁿ − 1。超过就让结果按 2ⁿ 取模环绕。
| 位数 | 无符号最大值 |
|---|---|
| 4 | 15 |
| 8 | 255 |
| 16 | 65,535 |
| 32 | 4,294,967,295 |
检测溢出
无符号加法规则
如果加法产生从最高位 (MSB) 溢出的进位 —— 即答案需要额外位，就发生了溢出。
4 位: 9 + 7
进位: 1
1001 (9)
+ 0111 (7)
──────
1 0000 (16 —— 需要 5 位 → 溢出！)2
3
4
5
6
有符号（二的补码）加法规则
溢出发生在两个操作数同号但结果异号时。
+5 + +6 用 4 位有符号二的补码
0101 (+5)
+ 0110 (+6)
──────
1011 (4 位二的补码下为 -5！)2
3
4
5
两个操作数都正但结果被解读为负 → 溢出。
（关于有符号表示的细节见下一节。）
n 位储存的最小最大值
课程指引明确提到 n 位寄存器能容纳的最小与最大数字。
| 位数 | 无符号最小 | 无符号最大 | 有符号最小（二补） | 有符号最大（二补） |
|---|---|---|---|---|
| 4 | 0 | 15 | −8 | +7 |
| 8 | 0 | 255 | −128 | +127 |
| 16 | 0 | 65,535 | −32,768 | +32,767 |
要会推导**最多 16 位（2 字节）**的情况，课程指引明确点出。
实例
例 A · 8 位无符号 200 + 100
200₁₀ = 1100 1000，100₁₀ = 0110 0100。
1100 1000
+ 0110 0100
-----------
1 0010 1100 ← 9 位 → 溢出（8 位最大为 255）2
3
4
8 位截断后结果是 00101100 = 44 —— 不是真正的 300。忽略溢出的程序会默默给出 44。
例 B · 4 位有符号 +5 + +6
两数都能塞进 4 位，但和 11 超过有符号最大 +7。溢出。
例 C · 4 位有符号 −5 + −4
−5 = 1011，−4 = 1100。和 = 1 0111。4 位截断后是 0111 = +7。两个输入都负但结果为正 → 溢出。
练习活动
用 4 位二进制算并标记溢出：
0110 + 01011101 + 0011（无符号）0111 + 0001（有符号）1100 − 00111000 + 1000（有符号）
答案
1011（无溢出）10000→0000+ 进位，无符号溢出1000，有符号 → 溢出（正 + 正 = 负）1001（无溢出）10000→0000，有符号 → 溢出（负 + 负 = 零，符号变了）
溢出的现实影响
- 《文明》游戏的 Gandhi 核弹 bug —— 他的好战度从 1 下溢到 255。
- YouTube 浏览计数 —— 在 2,147,483,647（有符号 32 位最大）卡住。
- 波音 787 发电机 —— 因 32 位有符号溢出，不能持续供电超过 248 天。
- 网络安全 —— 许多漏洞（缓冲区溢出攻击）从算术溢出开始。
学生常见错误
- 混淆进位输出（无符号溢出）与符号改变（有符号溢出）。
- 忘了只要结果装不下所选宽度，就算数学正确也会溢出。
- 不同位宽相加时没补齐到统一宽度。
考试式题目
题（4 分）： 做以下 8 位无符号二进制加法，说明是否溢出。 (a)
1010 1101 + 0001 0011(b)1111 1000 + 0000 1000
参考答案：
(a) 1010 1101 + 0001 0011 = 1100 0000。无 MSB 进位 → 无溢出。
(b) 1111 1000 + 0000 1000 = 1 0000 0000。从 MSB 进位 → 溢出（正确结果 256 装不进 8 位）。
关键要点
- 二进制加法用与十进制相同的逐列进位思路。
- 溢出 = 结果装不下所分配的位。
- 无符号溢出 ⇒ MSB 有进位。
- 有符号溢出 ⇒ 两操作数同号、结果反号。
- n 位无符号最大值为
2ⁿ − 1。
➡️ 下一节：3.4 二的补码