简要介绍补码的原理

2019-12-23 21:45:45


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

首先考虑一个$ 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?

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

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