原码-反码-补码

我们知道，计算机内部只能处理 0 和 1，二进制才是计算机的“母语”，我们在计算机里用到的数字、图片、视频，最终都是转换成二进制形式在计算机内进行存储和运算的。

我们在本章节里重点关于数字，为了简化，暂时只考虑其中的整数，整数（包括正数和负数），它们是如何用二进制来表示和运算的呢？

正整数的二进制表示比较直观，这个之前有讨论过，比如 5 的二进制是 101，假设每个正整数用 8 位二进制来表示，就是 0000 0101。

但负数怎么表示呢？比如 -5？也不能写成 -0000 0101，因为二进制里只有 0 和 1，并没有 - 这个符号。

注：在 C++ 中，一个整数（int类型）通常占 4 个字节，而 1 个字节为 8 位，也就是说一个 int 整数有 32 位。为了便于讲解，在本章节的讨论中，我们都是用 8 位二进制来表示的。

原码

最直观的想法是，用一个特殊的位来表示正负号，这个特殊的位也被称为符号位。例如，用最高位作为符号位，比如：0 表示正，1 表示负，这种表示方法就是这个数的原码形式，简称 原码。

例如：

 5 的原码是 0000 0101
-5 的原码是 1000 0101

原码的最大特点是表示简单，易于辨认，一个十进制数转换为原码形式也很方便。

• 对于正数，原码就是其二进制本身，最高位是 0
• 对于负数，最高位为 1，其余位是其绝对值（也就是对应的正数）的二进制表示

例如，对于数字 13，其二进制表示（8 位）是 0000 1101，因此

• +13 的原码就是 0000 1101
• -13 的原码是 1000 1101

原码的问题

虽然原码能表示负数，但它在进行加法运算时会遇到问题。

例如：计算 1 + (-1)：

• +1 的原码 (8 位) 是 0000 0001
• -1 的原码 (8 位) 是 1000 0001
• 如果直接按位相加：0000 0001 + 1000 0001 = 1000 0010。这个结果的原码是 -2。
• 但是 1 + (-1) 的结果应该是 0，这个结果不对。

另一个还有一个问题，原码有两种表示 0 的方式：

• +0 的原码是 0000 0000
• -0 的原码是 1000 0000

这不仅浪费了一个编码空间，而且在判断是否为零时也需要特殊处理。

为了解决原码在加法运算和零表示上的问题，人们引入了反码和补码。

反码

反码是为了解决原码加法运算的问题而引入的一种过渡编码方式。

反码的定义

• 正数： 反码与原码相同。
• 负数： 在其原码的基础上，符号位保持不变（仍为 1），其余各位取反（0 变 1，1 变 0）。

例如：

• +5：
  • 原码：0000 0101
  • 反码：0000 0101 (与原码相同)
• -5：
  • 原码：1000 0101
  • 反码：1111 1010，符号位为 1（表示负数），其余位取反 (000 0101 -> 111 1010)
• +0：反码：0000 0000
• -0：反码：1111 1111 (符号位 1 不变，其余 7 位取反)

反码的加法运算

反码的加法规则：将两个数的反码相加，如果最高位（符号位）产生了进位，则将这个进位加到最低位上（循环进位）。

再来计算 3 + (-1)：

• +3 的反码：0000 0011
• -1 的反码：1111 1110 (注意，-1 的原码是 1000 0001，反码是 1111 1110)

反码按照加法规则相加：

  0000 0011
+ 1111 1110
-----------
1 0000 0001  (最高位有进位 1)

将最高位的进位 1 加到最低位（循环进位）：

  0000 0001
+ 0000 0001 (将进位加到最低位)
-----------
  0000 0010  

这里最终得到的结果是反码，反码是 0000 0010。这个反码对应的原码也是 0000 0010，表示 2。结果正确！

再来计算一个，-3 + 2，同样的方法：

• -3 的反码：1111 1100  (注意，-3 的原码是 1000 0011，反码是 1111 1100)
• +2 的反码：0000 0010

反码按照加法规则相加：

  1111 1100
+ 0000 0010
-----------
  1111 1110

反码是 1111 1110。这个反码对应的原码是 1000 0001，表示十进制数 -1。结果正确！

注意：如果循环进位后，最高位又产生进位，则将这个进位舍弃。

反码优缺点

优点：

• 反码的引入解决了使用原码是加法运算需要额外判断符号位的问题，可以直接按位相加。

缺点：

• 仍然存在 +0 和 -0 两种 0 的表示
• 加法运算需要额外的“循环进位”处理，增加了硬件设计的复杂性

补码

补码是为了解决上述反码遗留的两个缺点（0 的两种表示和循环进位处理）而引入的。补码也是现代计算机中最常见的整数编码方式。

补码的定义

• 正数： 补码与原码、反码相同。
• 负数： 在其反码的基础上，最低位加 1。

先来看 0 的两种表示的问题。

• +0：补码是 0000 0000 （与原码 / 反码相同）
• -0：反码是 1111 1111，最低位加 1，1111 1111 + 0000 0001 = 1 0000 0000。由于是 8 位，最高位的进位直接舍弃，结果也是 0000 0000

也就是说，在补码中，+0 与 -0 都表示为 0000 0000，零的表示现在是唯一的了！

补码的加法运算

补码的加法规则：将两个数的补码直接按位相加，最高位的进位自然舍弃（不存在循环进位了）。

计算 1 + (-1)：

• +1 的补码：0000 0001
• -1 的补码：-1 的反码是 1111 1110，补码是 1111 1111
• 补码相加：

  0000 0001
+ 1111 1111
-----------
1 0000 0000  (最高位进位 1，舍弃)

结果的补码是 0000 0000，表示 0。结果正确！

计算 5 + (-2)：

• +5 的补码：0000 0101
• -2 的补码：-2 的反码是 1111 1101，补码是 1111 1110

补码相加：

  0000 0101
+ 1111 1110
-----------
1 0000 0011  (最高位进位 1，舍弃)

结果的补码是 0000 0011，表示 +3。结果正确！

补码的优点

• 零只有一种表示方式
• 加法运算简单：正数和负数的加法都可以直接按位相加，最高位的进位自然舍弃得到，不需要额外的循环进位处理。这极大简化了计算机硬件的设计。
• 减法可以转换为加法：计算 A - B 等价于计算 A + (-B)，而 -B 的补码可以通过 B 的补码（如果是正数，就直接是原码）按位取反再加 1 得到。

补码的范围

对于一个 n 位二进制数：

• 无符号整数： 可以表示 0 到 2^n - 1 的范围。
• 有符号整数 (补码表示)：
  • 最高位是符号位。
  • 可以表示 -2^{n-1} 到 2^{n-1} - 1 的范围。 例如，32 位有符号整数的范围是 -2^{31} 到 2^{31} - 1，在 C++ 中，如果大家输出整数（int）的最大和最小值宏定义的值：

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

int main() {
  cout << "INT 最小值：" << INT_MIN << endl;
  cout << "INT 最大值：" << INT_MAX << endl;
  return 0;
} 

输出：

INT 最小值：-2147483648
INT 最大值：2147483647

最小值也就是 -2^{31} 的结果，最大值也就是 2^{31} - 1 的值。

注意负数的最小值的绝对值比正数的最大值大 1，这是因为 0 占用了正数的一个编码空间，而补码中只有一个 0 的表示。那个额外的负数（如 8 位中的 -128）没有对应的正数原码。

总结

• 原码： 最高位表示符号，其余位表示绝对值。直观但加法和零表示有问题。
• 反码： 正数同原码，负数符号位不变，其余位取反。解决了加法符号问题，但零表示和循环进位仍是问题。
• 补码： 正数同原码/反码，负数在反码基础上最低位加 1。解决了零的表示唯一性问题和加法运算的复杂性。

现代计算机中，整数（包括有符号和无符号）都是以补码形式存储和运算的。

理解原码、反码、补码，特别是补码的设计思想，对于理解计算机底层如何进行整数运算非常有帮助。在算法竞赛中，虽然直接手算这些转换不多，但理解它们能帮助你更好地理解位运算、溢出等概念。