CPU 只有加法器，没有减法器。为了让 A - B 直接变成 A + (-B)，人们发明了补码；原码、反码只是推导脚手架。本文将从最基础的原码出发，经过反码的过渡，最终抵达补码的本质——环形数轴上的模运算，并深入探讨补码在不同编程语言中的体现。

Part 1: 原码——人类的直觉

符号位 + 绝对值

原码是最直观的有符号整数表示方法：最高位表示符号（0 正 1 负），其余位表示绝对值。

以 8 位为例：

十进制 原码 说明
+5 0000 0101 符号位 0（正），绝对值 5
-5 1000 0101 符号位 1（负），绝对值 5
+0 0000 0000 正零
-0 1000 0000 负零
+127 0111 1111 最大正数
-127 1111 1111 最小负数

表示范围：-127 到 +127，共 255 个不同的值（因为 +0 和 -0 占了两个编码）。

原码的致命缺陷

缺陷一：双零问题

+0（0000 0000）和 -0（1000 0000）是两个不同的编码，但它们表示的是同一个数学值 0。这给硬件判断"结果是否为零"带来了麻烦——需要检查两种情况。

缺陷二：加法需要特殊处理符号位

用原码做加法时，不能简单地将两个原码直接相加。例如：

1
2
3
4
5
  5 + (-3) 应该等于 2
  0000 0101  (+5 的原码)
+ 1000 0011  (-3 的原码)
-----------
  1000 1000  (-8 的原码？错误！)

硬件必须先比较符号位，再决定是做加法还是减法，然后确定结果的符号。这使得加法器的电路设计变得复杂。

原码在现代计算机中的残留

虽然整数不再使用原码，但 IEEE 754 浮点数的符号位仍然采用原码的思想：最高位 0 表示正，1 表示负。这也是为什么浮点数有 +0.0 和 -0.0 之分。

Part 2: 反码——过渡的桥梁

负数的反码

反码的规则：

  • 正数：反码与原码相同
  • 负数：符号位不动，其余位按位取反
十进制 原码 反码
+5 0000 0101 0000 0101
-5 1000 0101 1111 1010
+0 0000 0000 0000 0000
-0 1111 1111 1111 1111

反码的改进

反码的加法可以统一处理正数和负数，但需要一个额外的步骤——循环进位（End-Around Carry）：

1
2
3
4
5
6
7
8
  5 + (-3) = 2
  0000 0101  (+5 的反码)
+ 1111 1100  (-3 的反码)
-----------
1 0000 0001  产生进位
+         1  循环进位（将溢出的 1 加回最低位）
-----------
  0000 0010  = +2 ✓

反码的遗留问题

反码仍然有双零问题：+0（0000 0000）和 -0（1111 1111）。

而且循环进位增加了硬件复杂度——需要额外的加法步骤。

反码在实际中的应用

虽然反码不用于整数表示，但它在网络协议中仍有应用：

TCP/IP 校验和（RFC 1071） 使用反码求和：

  • 将数据按 16 位分组
  • 使用反码加法（带循环进位）求和
  • 取反码作为校验和

反码校验和的优势：

  • 字节序无关（大端和小端计算结果相同）
  • 可以增量更新（修改部分数据时不需要重新计算整个校验和）

Part 3: 补码——CPU 的真正语言

补码的定义：模运算的视角

对于 n 位二进制系统，补码的数学定义是：

  • 正数：补码 = 原码
  • 负数 -x：补码 = 2^n - x

以 8 位为例，2^8 = 256：

  • -5 的补码 = 256 - 5 = 251 = 1111 1011
  • -1 的补码 = 256 - 1 = 255 = 1111 1111
  • -128 的补码 = 256 - 128 = 128 = 1000 0000

8 位补码的表示范围

十进制 补码
+127 0111 1111
+1 0000 0001
0 0000 0000
-1 1111 1111
-127 1000 0001
-128 1000 0000

范围：-128 到 +127，共 256 个不同的值。

为什么补码多了一个 -128

在原码和反码中，1000 0000 表示 -0。但在补码中，由于零只有一个表示（0000 0000），1000 0000 被"释放"出来，用于表示 -128。

这意味着 8 位补码的负数比正数多一个：-128 到 -1 有 128 个负数，而 1 到 127 只有 127 个正数。

补码的核心优势

  1. 零唯一：只有 0000 0000 表示 0
  2. 加法统一：正数和负数的加法使用完全相同的电路
  3. 无需特殊处理符号位：符号位参与运算，自然得出正确结果

补码加法器的硬件实现

补码加法器由多个**全加器（Full Adder）**级联而成：

1
2
3
4
5
6
7
8
9
10
11
12
全加器：
输入：A_i, B_i, C_in（进位输入）
输出：S_i = A_i ⊕ B_i ⊕ C_in（和）
      C_out = (A_i · B_i) + (C_in · (A_i ⊕ B_i))（进位输出）

8 位加法器：
A7 A6 A5 A4 A3 A2 A1 A0
B7 B6 B5 B4 B3 B2 B1 B0
↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓
FA FA FA FA FA FA FA FA ← C_in = 0（加法）或 1（减法）
↓  ↓  ↓  ↓  ↓  ↓  ↓  ↓
S7 S6 S5 S4 S3 S2 S1 S0

减法 A - B 的实现：将 B 的每一位取反，然后将最低位的进位输入设为 1。这等价于 A + (~B + 1) = A + (-B)。整个减法只需要一个加法器和一组取反门。

进位前瞻加法器（Carry-Lookahead Adder）

上述级联全加器的设计存在性能瓶颈：高位的计算必须等待低位的进位传递完成。进位传播延迟与位宽成正比，对于 64 位加法器，最长进位链延迟可能达到 64 级全加器的延迟之和。

进位前瞻加法器通过并行计算所有位的进位来解决该问题。其核心思想是定义两个中间变量：

  • G（Generate，进位产生）：G_i = A_i · B_i（当 A_i 和 B_i 都为 1 时，无论进位输入如何，都会产生进位）
  • P（Propagate，进位传递）：P_i = A_i ⊕ B_i（当 A_i 或 B_i 中有一个为 1 时，进位输入会传递到输出）

进位输出 C_out 的计算公式：

  • C_0 = C_in
  • C_1 = G_0 + P_0 · C_0
  • C_2 = G_1 + P_1 · G_0 + P_1 · P_0 · C_0
  • C_3 = G_2 + P_2 · G_1 + P_2 · P_1 · G_0 + P_2 · P_1 · P_0 · C_0

通过这种方式，所有位的进位可以同时计算，延迟仅取决于进位前瞻逻辑的门延迟，与位宽无关。

实际 CPU 中通常采用分层分组的方式：将 4 位或 8 位分为一组，组内使用进位前瞻，组间再使用进位前瞻，在面积和速度之间取得平衡。

乘法器的实现

乘法本质上是重复的加法和移位。以无符号数乘法 A × B 为例：

  1. 移位-加法算法：从 B 的最低位开始，若该位为 1，则将 A 左移相应位数后累加到结果中
  2. Booth 算法：针对有符号数的优化算法，通过检查相邻位的组合来减少加法次数
  3. Wallace 树：使用进位保存加法器（Carry-Save Adder）并行化部分积的加法，将 O(n²) 的加法延迟降低到 O(log n)

示例：5 × 3（无符号）

1
2
3
4
5
6
7
8
  5 = 0101
× 3 = 0011
─────────
    0101  (5 × 1)
   0000   (5 × 0，左移 1 位)
  0101    (5 × 1，左移 2 位)
─────────
  1111 = 15

现代 CPU 的乘法器通常采用流水线设计，将多个乘法操作分阶段执行，提高吞吐量。

除法器的实现

除法比乘法复杂得多，主要采用以下算法：

  1. 恢复余数法：试商后若余数为负则恢复余数，效率较低
  2. 不恢复余数法：根据商的符号决定下一步是加还是减，无需恢复余数
  3. SRT 除法：同时计算多个商位（如 radix-4 每次计算 2 位），使用查找表加速商的选择
  4. Newton-Raphson 迭代法：通过倒数迭代实现，适用于浮点除法

除法的延迟通常远高于加法和乘法（数十个时钟周期），因此现代 CPU 往往不包含整数除法器，而是将除法指令转换为微代码序列执行。

Part 4: 环形数轴——最直观的理解方式

256 个值的环

把 8 位无符号整数的 256 个值（0-255）排列成一个环：

1
2
3
4
5
6
7
8
9
        0
    255   1
  254       2
 253         3
252           4
 ...         ...
 130         126
  129       127
    128

现在，我们重新解释这个环：将 128-255 的部分重新标记为 -128 到 -1：

1
2
3
4
5
6
7
8
9
       0
    -1   1
  -2       2
 -3         3
-4           4
 ...        ...
-126        126
 -127      127
   -128

模运算的时钟模型

采用 256 进制的时钟模型可以直观理解补码：

  • 从 0 点正向递增 5 = 到达 5 点
  • 从 0 点逆向递减 5 = 到达 251 点 = 到达 -5 点

在环形数轴上，-5 和 251 表示同一位置。这体现了模运算的本质：

-5 ≡ 251 (mod 256)

加法和减法的统一

在环形数轴上，加法对应顺时针方向，减法对应逆时针方向。逆时针方向移动 5 个单位等价于顺时针方向移动 251 个单位（256 - 5 = 251）。

因此 7 - 5 可以转换为 7 + 251：

  • 从 7 点顺时针方向移动 251 个单位
  • 7 + 251 = 258
  • 258 mod 256 = 2 ✓

溢出的直观理解

溢出即在环形数轴上跨越分界点（0/-128 的边界）：

  • 127 + 1：从 127 顺时针方向移动 1 个单位，到达 -128（溢出）
  • -128 - 1：从 -128 逆时针方向移动 1 个单位，到达 127（溢出）

Part 5: 基准锤权重公式

补码的"真正定义"

补码的值可以用一个简洁的公式计算：

value = -b₇ × 128 + b₆ × 64 + b₅ × 32 + b₄ × 16 + b₃ × 8 + b₂ × 4 + b₁ × 2 + b₀ × 1

即：值 = -128 × 符号位 + 其余七位按权展开

从 1111 1011 还原出 -5

1
2
3
4
value = -1×128 + 1×64 + 1×32 + 1×16 + 1×8 + 0×4 + 1×2 + 1×1
      = -128 + 64 + 32 + 16 + 8 + 0 + 2 + 1
      = -128 + 123
      = -5 ✓

数学定义的本质

"取反加一"仅是一种计算方法，而基准锤公式才是补码的数学定义。该公式明确表明：最高位的权重为 -128（而非 +128），其余位的权重保持不变。

与"取反加一"的等价性

对于负数 -x（x > 0），其补码的二进制表示为 B = 2^n - x。

"取反加一"的过程：

  1. 写出 x 的原码（符号位为 1，其余为绝对值）
  2. 除符号位外，其余位取反：得到 2^(n-1) - 1 - |x| 的低 n-1 位，加上符号位 1
  3. 加 1：得到 2^n - x

这与直接用 2^n - x 计算的结果完全一致。

Part 6: 补码的对称性与自逆性

对一个负数的补码再取补码（取反加一），可以得到其对应正数的原码：

1
2
3
-5 的补码：1111 1011
取反：      0000 0100
加一：      0000 0101 = +5 ✓

反之亦然：

1
2
3
+5 的补码：0000 0101
取反：      1111 1010
加一：      1111 1011 = -5 的补码 ✓

数学证明

设 x 的补码为 C(x) = 2^n - x（对于负数）。

对 C(x) 再取补码：C(C(x)) = 2^n - (2^n - x) = x

所以补码运算是自逆的（involution）。

特殊情况

-128 的补码取反加一：

1
2
3
-128 的补码：1000 0000
取反：        0111 1111
加一：        1000 0000 = -128（自逆）

由于 +128 超出了 8 位有符号整数的表示范围（最大 +127），"取反加一"溢出后返回 -128。这表明**"取反加一"并不能用于计算所有补码**——-128 的补码只能通过定义（2^8 - 128 = 128 = 1000 0000）来理解。

0 的补码取反加一：

1
2
3
0 的补码：0000 0000
取反：     1111 1111
加一：     0000 0000（溢出丢弃最高位的 1）= 0 ✓

Part 7: 减法即加法——完整示例

示例 1：7 - 5 = 2

1
2
3
4
5
 7 的补码：0000 0111
-5 的补码：1111 1011
────────────────────
相加：   1 0000 0010
丢弃溢出位：0000 0010 = 2 ✓

示例 2：-3 - 4 = -7

1
2
3
4
5
6
-3 的补码：1111 1101
-4 的补码：1111 1100
────────────────────
相加：   1 1111 1001
丢弃溢出位：1111 1001
验证：-128 + 64 + 32 + 16 + 8 + 0 + 0 + 1 = -128 + 121 = -7 ✓

溢出检测

CPU 通过两个标志位来检测溢出：

标志位 含义 检测方法
CF（Carry Flag） 无符号溢出 最高位产生进位
OF（Overflow Flag） 有符号溢出 符号位进位 ⊕ 最高有效位进位

有符号溢出的判断规则：

  • 两个正数相加得到负数 → 溢出
  • 两个负数相加得到正数 → 溢出
  • 一正一负相加 → 永远不会溢出

不同 CPU 架构的溢出处理差异

x86 架构（Intel/AMD）：

  • 提供 OF（Overflow Flag）和 CF（Carry Flag）两个独立标志位
  • OF 标志有符号溢出，CF 标志无符号溢出
  • 支持条件跳转指令（如 JO、JNO、JC、JNC）基于这些标志位
  • 溢出后结果静默回绕，不会触发异常

ARM 架构：

  • 提供 V（Overflow）标志位（类似 x86 的 OF）
  • 提供 C（Carry）标志位（类似 x86 的 CF）
  • ARMv8（AArch64）增加了条件选择指令（CSEL），可基于标志位选择不同结果
  • 溢出后结果静默回绕，不会触发异常

RISC-V 架构：

  • 仅提供基本的算术运算，不提供专门的溢出标志位
  • 需要通过软件检测溢出（如比较操作数的符号和结果的符号）
  • 提供专用指令（如 ADDU、SUBU）用于无符号运算，避免混淆
  • 溢出后结果静默回绕，不会触发异常

共同特点：

  • 所有主流架构都采用补码表示法
  • 溢出行为都是静默回绕（模 2^n）
  • 编译器通常依赖软件检测而非硬件异常处理溢出
  • 浮点运算使用 IEEE 754 标准，溢出时产生 +∞、-∞ 或 NaN

Java 中的整数溢出

Java 的整数溢出是**静默回绕（wrapping）**的：

1
2
3
4
5
6
int maxInt = Integer.MAX_VALUE;  // 2147483647
System.out.println(maxInt + 1);  // -2147483648（静默溢出）

// 安全算术方法（Java 8+）
Math.addExact(maxInt, 1);  // 抛出 ArithmeticException
Math.multiplyExact(maxInt, 2);  // 抛出 ArithmeticException

Part 8: 不同位宽的补码

符号扩展（Sign Extension）

将窄类型转换为宽类型时，需要用符号位填充高位：

1
2
3
8 位 -5：  1111 1011
16 位 -5：1111 1111 1111 1011  （高 8 位全部填充符号位 1）
32 位 -5：1111 1111 1111 1111 1111 1111 1111 1011

验证 16 位 -5：-32768 + 32763 = -5 ✓

零扩展（Zero Extension）

无符号数的扩展，高位填 0：

1
2
8 位 251（无符号）：1111 1011
16 位 251：         0000 0000 1111 1011

Java 中的类型转换陷阱

1
2
3
4
5
6
byte b = -1;          // 1111 1111
int i = b;            // 符号扩展 → 1111...1111 1111 1111 = -1
int unsigned = b & 0xFF;  // 强制零扩展 → 0000...0000 1111 1111 = 255

System.out.println(i);        // -1
System.out.println(unsigned);  // 255

& 0xFF 是 Java 中将 byte 当作无符号数使用的常见技巧：先符号扩展到 int，再用掩码清除高位。

位运算与补码

Java 提供三种移位运算：

运算符 名称 行为 示例（-8 = 1111…1000）
<< 左移 低位补 0 -8 << 1 = -16
>> 算术右移 高位补符号位 -8 >> 1 = -4
>>> 逻辑右移 高位补 0 -8 >>> 1 = 2147483644

>>> 是 Java 特有的运算符，C/C++ 中没有（C 的 >> 对有符号数的行为是实现定义的）。

Part 9: 补码在编程语言中的体现

Java

Java 的所有整数类型都使用补码，且溢出行为是明确定义的（静默回绕）：

类型 位宽 范围
byte 8 -128 ~ 127
short 16 -32768 ~ 32767
int 32 -2^31 ~ 2^31 - 1
long 64 -2^63 ~ 2^63 - 1

Java 没有无符号整数类型（Java 8 引入了 Integer.toUnsignedLong() 等辅助方法）。

1
2
3
4
5
6
// Java 的溢出是确定性的
byte b = 127;
b++;  // b = -128（溢出回绕）

// 安全算术
int result = Math.addExact(Integer.MAX_VALUE, 1);  // ArithmeticException

C/C++

C/C++ 中，有符号整数溢出是未定义行为（Undefined Behavior, UB）：

1
2
int x = INT_MAX;
x = x + 1;  // UB！编译器可以做任何事情

编译器可能基于"有符号整数不会溢出"的假设进行优化，导致意外行为。例如：

1
2
3
4
// 编译器可能将这个循环优化为无限循环
for (int i = 0; i >= 0; i++) {
    // 编译器假设 i 永远不会溢出，所以 i >= 0 永远为真
}

无符号整数的溢出在 C/C++ 中是明确定义的（模 2^n 回绕）。

Python

Python 使用任意精度整数（bigint），没有溢出的概念：

1
2
x = 2**63 - 1  # 9223372036854775807
x + 1          # 9223372036854775808（自动扩展，不会溢出）

Python 的整数可以无限大，只受内存限制。

Rust

Rust 对整数溢出有最精细的控制：

模式 行为
Debug 模式 溢出时 panic（程序崩溃）
Release 模式 溢出时回绕（wrapping）

Rust 还提供了四种显式溢出处理方法：

1
2
3
4
5
6
let x: i32 = i32::MAX;

x.wrapping_add(1)    // 回绕：-2147483648
x.checked_add(1)     // 返回 None
x.saturating_add(1)  // 饱和：仍然是 i32::MAX
x.overflowing_add(1) // 返回 (-2147483648, true)，第二个值表示是否溢出

JavaScript

JavaScript 的 Number 类型是 IEEE 754 双精度浮点数，整数运算通过位运算符 | 0 截断为 32 位有符号整数：

1
2
3
4
5
2147483647 + 1        // 2147483648（浮点数，不溢出）
(2147483647 + 1) | 0  // -2147483648（截断为 32 位补码）

// BigInt（ES2020）
2n ** 63n - 1n + 1n   // 9223372036854775808n（任意精度）

总结

编码 零的表示 8 位范围 加法统一 硬件复杂度 现代使用
原码 两个（+0, -0） -127 ~ +127 ❌ 高 IEEE 754 符号位
反码 两个（+0, -0） -127 ~ +127 ⚠️（需循环进位） 中 TCP/IP 校验和
补码 一个（0） -128 ~ +127 ✅ 低 所有现代 CPU

补码的本质是模运算：在一个有限的数值环上，减法等价于加上补数。这个简洁的数学原理，使得 CPU 只需要一个加法器就能完成所有的加减运算。

参考资料