简要介绍补码的原理

补码对于我来说向来是一个神秘的概念。主要因为不论是课堂所授，教材所述，博文所记，但凡涉及补码相关，无不罗列“取反加一”之类的生涩定义，至多列举几个实例，而再无详解。我却在近日阅读《深入理解计算机系统》一书时发现关于补码原理的讲解。此书所述亦无长篇大论，却简洁精要，直入本质，令人恍然大悟，拍手称快。故作此文以记之，一来留作备忘，二来造福后人，减少迷惑无力之困境。 首先考虑一个$ 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语言中） 1. 为什么abs(-2147483648)=-2147483648？ 2. 什么情况下i<=strlen(b)-1会出现错误？应该怎么更改以避免这个错误？（提示：strlen()函数的返回值为无符号整数） 3. 为什么在C语言的limits.h头文件中要把int类型变量的最小值INT_MIN定义为(-INT_MAX-1)，而不是直接定义为-2147483648？ 这三道思考题引导读者探索更多关于整数表示的知识。 最后再次推荐《深入理解计算机系统》一书，它介绍了有关计算机系统的诸多原理，最重要的是紧密贴合实际，既容易理解又引人入胜，推荐给每一个对计算机系统感兴趣的人。