原码反码补码

为何需要不同的编码方式？

在计算机世界中，一切信息最终都以二进制的 $0$ 和 $1$ 序列形式存在。对于非负整数，其二进制表示是直观的，例如十进制的 $5$ 对应二进制的 $101$。然而，计算机必须能够处理负数。这就引出了一个核心问题：如何在二进制的框架下表示一个数的正负属性？为了解决这个问题，计算机科学家们设计了多种编码方案，其中最重要、也最终在现代计算机中占据统治地位的便是补码 (Two's Complement)。

要理解补码的精妙之处，我们必须先了解其前身——原码 (Sign-and-Magnitude) 和 反码 (Ones' Complement)。这三种编码方式，本质上都是在固定的二进制位数（例如 $8$ 位、$16$ 位、$32$ 位）内，对整数（包括正、负、零）进行编码的规则。它们的设计目标是让计算机硬件能以尽可能简单、高效的方式执行算术运算。

在本文中，我们将统一使用“最高位”指代二进制数最左边的一位，在有符号整数中，它也被用作“符号位”。

1. 原码 (Sign-and-Magnitude)

原码是最符合人类直觉的一种表示法。它将一个数的二进制表示分为两部分：符号位 (Sign Bit) 和 数值位 (Magnitude)。

1.1 定义

在原码表示法中，最高位被用作符号位，其余位表示数值的绝对值。

• 符号位：$0$ 代表正数，$1$ 代表负数。
• 数值位：该数绝对值的二进制表示。

对于一个 $n$ 位的二进制数：

• 正数：符号位为 $0$，后 $n-1$ 位为其绝对值的二进制。
• 负数：符号位为 $1$，后 $n-1$ 位为其绝对值的二进制。
• 零：有两种表示方式。

以 8 位系统为例：

• 表示 $+5$：

  • 符号为正，所以符号位是 $0$。
  • 数值 $5$ 的二进制是 $101$。用 $7$ 位表示数值，不足的位补 $0$，即 $0000101$。
  • 因此，$+5$ 的原码是 $00000101$。

• 表示 $-5$：

  • 符号为负，所以符号位是 $1$。
  • 数值 $5$ 的绝对值是 $5$，二进制为 $101$。用 $7$ 位表示为 $0000101$。
  • 因此，$-5$ 的原码是 $10000101$。

1.2 表示范围

在一个 $n$ 位的系统中，原码可以表示的数值范围为：

$$[-(2^{n-1}-1), 2^{n-1}-1]$$

例如，在 8 位系统中，范围是 $[-(2^7-1), 2^7-1]$，即 $[-127, 127]$。

1.3 原码的困境

虽然直观，但原码在实际运算中暴露了两个致命缺陷：

1. “零”的两种表示

原码中存在两个零：

• $+0$: $00000000$
• $-0$: $10000000$

这在数学上是冗余的，也给硬件设计带来了不必要的复杂性。判断一个数是否为零，需要检查两种不同的二进制模式。

2. 算术运算的复杂性

原码的加法运算规则非常复杂。在执行两个数相加时，硬件需要先判断它们的符号：

• 同号相加：数值位相加，符号位不变。
• 异号相加：需要比较两个数值的绝对值大小，用大数的绝对值减去小数的绝对值，结果的符号与绝对值较大的数一致。

这种根据符号来切换加减法逻辑的设计，使得加法器的电路实现变得非常复杂和低效。例如，计算 $5 + (-3)$：

• $5$ 的原码：$00000101$
• $-3$ 的原码：$10000011$

硬件需要识别出它们是异号，然后执行减法 $5-3=2$，并取 $5$ 的符号作为结果的符号，最终得到 $00000010$（即 $+2$）。这与我们期望的、能够将符号位和数值位统一处理的简单加法器相去甚远。

2. 反码 (Ones' Complement)

为了解决原码在运算上的复杂性，反码被提了出来。反码试图将减法运算统一为加法运算。

2.1 定义

反码的规则如下：

• 正数：反码与原码相同。
• 负数：一个负数（例如 $-x$）的反码，可以通过其对应正数（$+x$）的全部 $n$ 位逐位取反得到。

以 8 位系统为例：

• 表示 $+5$：

  • 其表示（原码、反码、补码相同）为 $00000101$。

• 表示 $-5$：

  • 取 $+5$ 的反码表示 $00000101$。
  • 将全部 8 位按位取反（$0$ 变 $1$，$1$ 变 $0$），得到 $11111010$。
  • 因此，$-5$ 的反码是 $11111010$。

2.2 表示范围

与原码相同，一个 $n$ 位系统的反码表示范围也是：

$$[-(2^{n-1}-1), 2^{n-1}-1]$$

2.3 反码的进步与遗留问题

1. 运算的简化

使用反码，可以将减法转化为加法。减去一个数，等同于加上这个数的负数（的反码）。例如，计算 $5 - 3$，等价于 $5 + (-3)$：

• $+5$ 的反码：$00000101$
• $-3$ 的反码：$11111100$
• 相加：

  00000101
+ 11111100
------------
(1)00000001

这里出现了一个循环进位 (End-around carry)。当最高位产生进位时，需要将这个进位加到结果的最低位。 $00000001 + 1 = 00000010$。结果是 $00000010$，这正是 $+2$ 的反码。

这个“循环进位”虽然比原码的逻辑判断简单，但仍然是一个特殊操作，增加了硬件的复杂度。

2. “零”的问题依然存在

反码未能解决双零问题：

• $+0$: $00000000$
• $-0$: 将 $+0$ 的表示 $00000000$ 全部取反，得到 $11111111$。

所以，$00000000$ 和 $11111111$ 在反码系统中都表示零。这个问题依然是反码的一个缺陷。

3. 补码 (Two's Complement)

补码是现代计算机系统表示有符号整数的最终选择。它完美地解决了原码和反码的所有问题：只有一个零表示，并且加减法可以完全统一处理。

3.1 定义

补码的规则是：

• 正数：补码与原码、反码都相同。
• 负数：其补码是在其反码的基础上，整体加 $1$。

求负数补码的两种等价方法：

1. 正数 -> 反码 -> 补码：将对应正数的二进制表示全部位按位取反，再将得到的二进制数整体加 $1$。
2. 原码 -> 补码：写出负数的原码，保持符号位不变，其余数值位按位取反，最后将得到的二进制数整体加 $1$。

以 8 位系统为例，表示 $-5$：

• 方法一（推荐）：

  • $+5$ 的表示为 $00000101$。
  • 全部位按位取反，得到反码 $11111010$。
  • 整体加 $1$：$11111010 + 1 = 11111011$。
  • 所以 $-5$ 的补码是 $11111011$。

• 方法二：

  • $-5$ 的原码是 $10000101$。
  • 符号位 $1$ 不变，数值位 $0000101$ 取反得 $1111010$。这构成了 $11111010$（即反码）。
  • 整体加 $1$ 得 $11111011$。

一个重要技巧： 从一个负数的补码求其绝对值，操作是完全一样的：先对所有位按位取反，再对整体加 $1$。 例如，已知一个补码是 $11111011$。

1. 按位取反：$00000100$
2. 整体加 $1$：$00000100 + 1 = 00000101$ 这就是 $5$ 的二进制，所以 $11111011$ 表示 $-5$。

3.2 补码的优越性

1. 唯一的零

在补码系统中，零的表示是唯一的。

• $+0$ 的补码是 $00000000$。
• 我们来计算 $-0$ 的补码：
  • $+0$ 的表示为 $00000000$。
  • 按位取反得 $11111111$。
  • 整体加 $1$：

    11111111
  +        1
  ------------
  (1)00000000
  

  • 最高位的进位 $1$ 被丢弃（因为我们只有 8 位）。结果是 $00000000$。

因此，在补码系统中，$+0$ 和 $-0$ 的表示是统一的。

2. 统一的加减法

补码最强大的地方在于，它使得减法运算可以完全等价于加法运算。符号位可以直接参与运算，不再需要任何特殊的逻辑判断。

• 计算 $5 - 3$ (即 $5 + (-3)$)：

  • $+5$ 的补码：$00000101$
  • $-3$ 的补码：$11111101$
  • 相加：

    00000101
  + 11111101
  ------------
  (1)00000010
  

  • 最高位产生的进位直接丢弃，结果是 $00000010$，这正是 $+2$ 的补码。

• 计算 $3 - 5$ (即 $3 + (-5)$)：

  • $+3$ 的补码：$00000011$
  • $-5$ 的补码：$11111011$
  • 相加：

    00000011
  + 11111011
  ------------
    11111110
  

  • 结果是 $11111110$。这是一个负数的补码（最高位为 $1$）。其值为 $-( \text{~}11111110 + 1) = -(00000001 + 1) = -2$。结果正确。

可以看到，无论是正数减正数，还是小数减大数，补码系统下的加法器都可以用完全相同的电路逻辑来处理。这极大地简化了计算机的算术逻辑单元 (ALU) 的设计。

3.3 表示范围

由于零的表示只有一个，补码系统相比原码和反码，可以多表示一个负数。 在一个 $n$ 位的系统中，补码的表示范围是：

$$[-2^{n-1}, 2^{n-1}-1]$$

例如，在 8 位系统中，范围是 $[-128, 127]$。

• 最大正数：$01111111$，即 $127$。
• 最小负数：$10000000$。这个数比较特殊，它代表 $-128$。它没有对应的原码和反码表示，是补码系统独有的。

4. 深入理解补码：模运算的视角

为什么补码能够如此巧妙地工作？其数学基础是模运算 (Modular Arithmetic)。

我们可以把一个 $n$ 位的寄存器想象成一个可以容纳 $2^n$ 个状态的循环系统，就像一个时钟。一个 8 位系统可以表示 $2^8 = 256$ 个状态。

在这个环上，从 $0$ 开始顺时针走是增加，逆时针走是减少。

• 从 $0$ 顺时针走 $5$ 步，到达 $00000101$ ($+5$)。
• 从 $0$ 逆时针走 $5$ 步，等价于从 $256$ (在环上与 $0$ 重合) 的位置出发，向前走 $256 - 5 = 251$ 步。
• 十进制 $251$ 的二进制是 $11111011$。这正是 $-5$ 的补码！

从模运算的角度看，一个负数 $-x$ 的补码，就是它的模 $2^n$ 下的同余数 $2^n - x$。

$$[-x]_{补} \equiv 2^n - x \pmod{2^n}$$

而求补码的“按位取反，整体加一”操作正是计算 $2^n-x$ 的一种高效方式：

• 对 $n$ 位的 $x$ 按位取反，等于用 $n$ 个 $1$ 组成的数（即 $2^n-1$）减去 $x$。结果为 $(2^n-1) - x$。
• 再整体加 $1$，结果为 $((2^n-1) - x) + 1 = 2^n - x$。

"减法变加法"的本质： 计算 $A - B$，在模 $2^n$ 的系统中，等价于：

$$A - B \equiv A + (2^n - B) \pmod{2^n}$$

$A$ 的补码是 $A$，$B$ 的补码是 $B$，而 $-B$ 的补码是 $2^n - B$。所以，计算 $A-B$ 的补码，就是将 $A$ 的补码和 $-B$ 的补码相加。当结果超出 $2^n$ 时（即最高位有进位），这个进位在模运算中自动被舍弃，完美契合了硬件中丢弃进位的行为。

5. 常见位运算与补码

在 C++ 等语言中，整数类型（如 int, long long）默认使用补码表示。

• 按位非 ~ (NOT) ~x 的结果是 $-(x+1)$。 例如，对于 x = 5 ($00000101$)，~x 是 $11111010$。这正是 $-6$ 的补码。

• 左移 << (Left Shift) x << k 将 x 的二进制表示向左移动 k 位，右边补 $0$。对于非负数，这等价于乘以 $2^k$。对于有符号整数，如果左移导致符号位丢失或改变，根据 C++ 标准，这属于未定义行为 (Undefined Behavior, UB)。

• 右移 >> (Right Shift) 对于有符号整数 x >> k，C++ 标准规定其行为是实现定义 (Implementation-defined)。绝大多数现代编译器和处理器都采用算术右移：右移时，左边补充原始的符号位（正数补 $0$，负数补 $1$）。这保证了右移后数的符号不变，数值上近似于除以 $2^k$（向负无穷方向取整）。

  • 例：$-16$ ($...11110000$) >> 2 -> $...11111100$ (即 $-4$)。 对于无符号整数 (unsigned)，右移总是逻辑右移（左边补 $0$）。

• lowbit 操作 在算法竞赛中，一个常用的技巧是 x & -x，它能取出 x 的二进制表示中最低位的 1 所代表的数值。 例如 x = 12 ($00001100$)。

• 我们来求 -x (即 $-12$) 的补码。根据 ~x + 1 法则：

  • x 是 00001100。
  • ~x 是 11110011。
  • -x 是 ~x + 1，即 11110100。

• 执行 x & -x:

```
  00001100 (12)
& 11110100 (-12)
------------
  00000100 (4)
```
结果是 $4$，正是 $12$ 的二进制 $1100$ 中，最低位的 $1$ (即从右数第三位)所代表的权值 $2^2$。这个操作在树状数组等数据结构中有关键应用。

6. 代码实现与应用

6.1 打印整数的二进制表示

这个函数可以帮助我们直观地看到一个整数在内存中的补码形式。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 打印一个32位整数的二进制补码表示
void p32(int n) {
    for (int i = 31; i >= 0; --i) {
        cout << ((n >> i) & 1);
        if (i % 8 == 0) cout << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a = 5;
    int b = -5;

    cout << " 5: "; p32(a);
    cout << "-5: "; p32(b);

    cout << endl;

    cout << "5 + (-5) = " << (a + b) << endl;
    cout << "Binary sum: " << endl;
    cout << "  "; p32(a);
    cout << "+ "; p32(b);
    cout << "------------------------------------" << endl;
    cout << "= "; p32(a + b);

    cout << endl;

    int c = -1;
    cout << "-1: "; p32(c);
    int d = -128;
    cout << "-128: "; p32(d);
    int e = 127;
    cout << "127: "; p32(e);

    return 0;
}

程序输出：

 5: 00000000 00000000 00000000 00000101 
-5: 11111111 11111111 11111111 11111011 

5 + (-5) = 0
Binary sum: 
  00000000 00000000 00000000 00000101 
+ 11111111 11111111 11111111 11111011 
------------------------------------
= 00000000 00000000 00000000 00000000 

-1: 11111111 11111111 11111111 11111111 
-128: 11111111 11111111 11111111 10000000 
127: 00000000 00000000 00000000 01111111 

输出清晰地验证了之前讨论的所有补码表示和运算规则。

6.2 程序阅读与补全题示例

示例1：判断题

在一个 32 位系统上，对于 int x = 2147483647;（即 INT_MAX），执行 x + 1 后，x 的值会变为 $-2147483648$。 ( )

分析：

• 2147483647 是 32 位有符号整数的最大值，其补码为 01111111 11111111 11111111 11111111。
• 加 $1$ 后，发生溢出，二进制变为 10000000 00000000 00000000 00000000。
• 这个二进制表示是 32 位有符号整数的最小值，即 $-2147483648$ (INT_MIN)。
• 答案：正确。

示例2：代码分析

下面的函数 abs_fast 试图用位运算快速计算一个整数的绝对值。

#include<bits/stdc++.h>
using namespace std;

int abs_fast(int n) {
    int msk = n >> 31; // 如果 n >= 0, msk = 0; 如果 n < 0, msk = -1 (即0xFFFFFFFF)
    return (n + msk) ^ msk;
}

分析： 这个技巧利用了补码的性质，将 if-else 判断转换为了无分支的位运算。

• 当 n >= 0 时：
  • msk 是 $0$。
  • 表达式变为 (n + 0) ^ 0，结果是 n。
• 当 n < 0 时：
  • msk 是 $-1$ (算术右移的结果)。
  • 表达式变为 (n + (-1)) ^ (-1)，即 (n-1) ^ (-1)。
  • 与 $-1$ (全 $1$) 进行异或运算等价于按位取反 ~。
  • 所以结果是 ~(n-1)。根据 ~x = -(x+1)，~(n-1) 等于 -((n-1)+1)，即 -n。
• 边界情况： 这个实现有一个著名的边界问题。当输入为 n = INT_MIN (例如 $-2147483648$) 时，其绝对值 2147483648 无法在 int 类型中表示。此时，该函数会返回 INT_MIN 本身。在需要精确处理此边界的应用中，应添加额外判断或使用更宽的整数类型。

7. 总结与对比

为了清晰地回顾这三种编码方式的特点，下表进行了总结（以 8 位系统为例）：

特性	原码 (Sign-and-Magnitude)	反码 (Ones' Complement)	补码 (Two's Complement)
正数表示	符号位0 + 数值	与原码相同	与原码、反码相同
负数表示	符号位1 + 数值	对应正数全部位取反	对应正数全部位取反后，整体加 1
表示范围	[-127, 127]		[-128, 127]
零的表示	+0 ($00000000$) -0 ($10000000$)	+0 ($00000000$) -0 ($11111111$)	唯一零 ($00000000$)
算术运算	复杂，需判断符号和数值大小	需循环进位，仍有特殊处理	简单，加减法统一，符号位直接参与运算
现代应用	极少用于整数运算，浮点数尾数部分使用	已被淘汰	绝大多数现代计算机的标准表示法

从这个演进过程中，我们可以看到计算机体系结构设计中一个永恒的主题：追求硬件实现的简洁与高效。

补码之所以胜出，正是因为它用一种优雅的数学形式（模运算）统一了加减法，消除了冗余表示，从而允许设计出更简单、更快速的算术逻辑单元。