简要介绍补码的原理

补码对于我来说向来是一个神秘的概念。主要因为不论是课堂所授，教材所述，博文所记，但凡涉及补码相关，无不罗列“取反加一”之类的生涩定义，至多列举几个实例，而再无详解。我却在近日阅读《深入理解计算机系统》一书时发现关于补码原理的讲解。此书所述亦无长篇大论，却简洁精要，直入本质，令人恍然大悟，拍手称快。故作此文以记之，一来留作备忘，二来造福后人，减少迷惑无力之困境。

首先考虑一个$w$位二进制数$X=\sum_{i=0}^{w-1}x_i\cdot2^i(x_i=0\ or\ 1)$，可以用一个向量$\vec{x}=\{x_{w-1},x_{w-2},...,x_{0}\}(x=0\ or\ 1)$来表示它的$w$位原码表达形式。

所谓的向量，不过是$w$个$0$或$1$的序列，不必见到不熟悉的数学知识就大惊失色，几欲先走。

在原码中，第$i$位表示$2^i$，而补码实质上是用最高位，即符号位表示$-2^{w-1}$，其余位仍表示$2^i$。

用最高位表示$-2^{w-1}$是否是最初设计补码时的考虑尚不得知，网络上也有一篇从模意义角度出发的讲解。但不可否认，$-2^{w-1}$是一个极简单又十分正确的理解。

例如对于$4$位补码二进制数$1011$，它的十进制表示为$-8+2+1=-5$。

这里借用《深入理解计算机系统》中的图片来更直观地说明符号位的作用:

如此一来便可以发现，$w$位有符号整数（即补码表示的二进制数）实质上相当于把$w$位无符号整数（即原码表示的二进制数）的后一半映射到负数，而前一半的意义保持不变。二进制的美好性质在这里得到了充分的体现。

根据最高位表示$-2^{w-1}$的解释，便可以推导一对相反数的补码表示的关系：

令正数$A=\{x_{w-1},x_{w-2},...,x_{0}\}=\sum_{i=0}^{w-1}x_i\cdot2^i$，由于A是正数，所以符号位$x_{w-1}=0$，$A=\sum_{i=0}^{w-2}x_i\cdot2^i$。

$-A$是负数，所以其最高位应为$x_{w-1}=1$，不妨将$A$中的最高位变为1，其余位不变，观察其变化。

令$A'=-2^{w-1}+\sum_{i=0}^{w-2}x_i\cdot2^i$，2的整数幂减去低位的二进制数有什么特点？ 需要注意到$\sum_{i=0}^{w-2}x_i\cdot2^i+\sum_{i=0}^{w-2}(1-x_i)\cdot2^i+1=2^{w-1}$，所以$A'=-\sum_{i=0}^{w-2}(1-x_i)\cdot2^i-1$。

其中$\sum_{i=0}^{w-2}(1-x_i)\cdot2^i$就是把$A$除了最高位全部取反的结果。

那么不妨令$B=\sum_{i=0}^{w-2}(1-x_i)\cdot2^i$，则$B'=-\sum_{i=0}^{w-2}x_i\cdot2^i-1=-A-1$，即$-A=B'+1$。

$B$是$A$除最高位取反的结果，而$B'$是$B$最高位取反的结果，那么$B'$就是$A$全部取反的结果，所谓取反再加一的计算方法可以由此推来。

回顾刚才的推导过程，不和谐的$+1$实质上是把无符号整数的后一半通过减法映射到负数时自然出现的。进一步地说，会出现$+1$本质上是因为一个$w-2$位全是$1$的二进制数和第$w-1$位是$1$，剩下位为$0$的二进制数之间相差为$1$。

了解了补码的原理，关于整数表示的一些知识也变得容易起来。

例如逻辑右移和算数右移。所谓逻辑右移，就是右移$k$位后前$k$位补零，例如$4$位二进制数$1010$逻辑右移$1$位的结果为$0101$。而算数右移会在前$k$位补符号位，例如$1010$算数右移$1$位结果为$1101$，而$0101$算数右移$1$位结果为$0010$。

如果对补码采用算术右移，则不仅能做到符号位不变（补上了相同的符号位），还能做到绝对值的变化与正数右移时的变化一致。一方面可以理解为补码转$10$进制表达时如果是负数，则需要取反，这时补上的$1$就会转成$0$，另一方面可以类比上文，以$2$的次幂的形式进行数学推导：

$-2^{w-1}+2^{w-2}=-2^{w-2}$，这就等价于最高位为$w-2$位的二进制负数。

文末为感兴趣的读者提供三道思考题：

（在C语言中）

这三道思考题引导读者探索更多关于整数表示的知识。

最后再次推荐《深入理解计算机系统》一书，它介绍了有关计算机系统的诸多原理，最重要的是紧密贴合实际，既容易理解又引人入胜，推荐给每一个对计算机系统感兴趣的人。