3. 整数的加减运算

我们已经了解了计算机中正整数如何表示,加法如何计算,那么负数如何表示呢?减法又如何计算呢?本节来讨论这个问题。为了书写方便,本节举的例子都用8个bit表示一个数,实际计算机算术运算的操作数可以是8位、16位、32位甚至64位的。

要用8个bit表示正数和负数,一种简单的思路是把最高位当作符号位(Sign Bit),0表示正1表示负,剩下的七位表示绝对值的大小,这称为Sign and Magnitude表示法。例如-1表示成10000001,+1表示成00000001。思考一下,N个bit的Sign and Magnitude表示法能够表示的最大整数和最小整数分别是多少?请写出算式。

计算机要对这样的两个数做加法运算需要处理以下逻辑:

  1. 如果两数符号位相同,就把它们的低7位相加,符号位不变。如果低7位相加时在最高位产生进位,则结果超出7位所能表示的数值范围,这称为溢出(Overflow),通常把计算机中的一个标志位置1表示产生溢出。

  2. 如果两数符号位不同,首先比较它们的低7位谁大,然后用大数减小数,结果的符号位和大数相同。

减法运算需要处理以下逻辑:

  1. 如果两数符号位相同,并且低7位是大数减小数,则符号位不变,如果低7位是小数减大数,则按大数减小数计算,结果要变号。

  2. 如果两数符号位不同,把低7位相加,如果是正数减负数则结果为正,如果是负数减正数则结果为负,低7位在相加时可能产生溢出。

这其实和手算加减法的逻辑是相同的。算加减法需要处理这么多逻辑:比较符号位,比较绝对值,加法改减法,减法改加法,小数减大数改成大数减小数……这是非常低效率的。还有一个缺点是0的表示不唯一,既可以表示成10000000也可以表示成00000000,进一步增加了逻辑的复杂性,所以我们迫切需要重新设计数的表示方法,以使计算过程更简单。

有一种方法可以把减法全部转化成加法来计算,这样就不必设计加法器和减法器两套电路了。我们以十进制减法为例来理解一下这种方法。比如

167-52=167+(999-52)-1000+1=167+947-1000+1=1114-1000+1=114+1=115

首先把52换成999-52,也就是947,这称为取9的补码(9's Complement),虽然这也是减法但它不需要借位,只需要对每一位数字分别取补码,所以比一般的减法要简单得多。然后把167和947相加,百位上的进位舍去,得到114,然后再加1得到115[21],这就是最终结果了。一句话概括就是:减去一个数等于加上这个数取9的补码再加1(忽略最高位的进位)。

这种方法也可以类推到二进制加减法:减去一个数等于加上这个数取1的补码(1's Complement)再加1(忽略MSB的进位)。取1的补码就是1-1=0,1-0=1,其实相当于把每一位数字取反了,以后将1的补码简称为反码。比如

00001000-00000100->00001000+11111011+1->00000011+1=00000100

上式的前两步不是等价变换,所以没有用=号而是用->表示,第一步多加了一个100000000,第二步少加了一个100000000,效果相互抵消,所以最终结果正是00001000-00000100的结果。现在我们发现,如果把第一步写成00001000+(-00000100)->00001000+11111011+1,则11111011+1就可以用来表示负数-00000100。所以,补码表示法不仅可以把减法转化为加法,而且合理地规定了负数的表示方法,就是“先取反码再加1”。负数的这种表示称为2的补码(2's Complement),以后简称为补码。为什么称为2的补码呢?因为如果对一位数取补码,则1的补码是1-1+1=10-1=1,相当于从2里面减去1。类似地,对00000100取补码是11111111-00000100+1=100000000-00000100,相当于从100000000(十进制的256)里面减去00000100。

将负数全部用补码表示之后,8个bit可以表示的正数有00000000~01111111(十进制的0~127),负数有10000000~11111111(十进制的-128~-1),合起来是十进制的-128~127,一共256个数,而8个bit最多可以表示28=256个不同的数,所以已经充分利用了这8个bit,每个数都只有一种表示,0也只有一种表示就是00000000。我们还发现,所有正数的最高位是0,所有负数的最高位是1,因此最高位仍然具有符号位的含义,要检查一个数是正是负只要看最高位就可以了,但在计算时却可以把符号位和数放在一起做加法运算,而不必像Sign and Magnitude表示法那样对符号位单独处理。

采用补码做加减运算时总是忽略MSB的进位,这让人很不放心:如果在计算过程中忽略进位的效果没有相互抵消怎么办?如果没有相互抵消,最后的结果肯定是错的,这种情况一定是由溢出引起的。只要我们有办法判断哪些情况会产生溢出,其它情况下都可以放心地忽略MSB的进位。判断溢出的办法是这样的:在相加过程中最高位产生的进位和次高位产生的进位如果相同则没有溢出,否则就说明产生了溢出。逻辑电路的实现可以把这两个进位连接到一个异或门,把异或门的输出连接到溢出标志位。对于8位二进制数的加减运算来说,当计算结果超出-128~127的范围时就会溢出,例如:

图 14.3. 有符号数加法溢出

有符号数加法溢出

最高位产生的进位是1,次高位产生的进位是0,说明溢出了,计算结果换算成十进制是122,这显然不对,根本原因是(-126)+(-8)=-134超出了8位二进制数能表示的范围。

用8个bit既表示正数又表示负数,则能够表示的范围是-128~127,如果8个bit全部表示正数,则能够表示的范围是0~255,前者称为有符号数(Signed Number),后者称为无符号数(Unsigned Number)。但是计算机在做加法时并不区分操作数是有符号数还是无符号数,计算过程都是一样的,所以上面的例子也可以看作无符号数的加法:

图 14.4. 无符号数加法进位

无符号数加法进位

把两个操作数看作无符号数分别是130和248,计算结果换算成十进制是122,最高位的一个进位相当于256,122+256这个结果是对的。计算机的加法器在做完计算之后,根据最高位产生的进位设置进位标志,同时根据最高位和次高位产生的进位的异或设置溢出标志。至于这个加法到底是有符号数加法还是无符号数加法则取决于程序怎么理解了,如果程序把它理解成有符号数加法,就去检查溢出标志,如果程序把它理解成无符号数加法,就去检查进位标志。通常计算机在做算术运算之后还可能设置另外两个标志,如果结果为零则设置零标志,如果结果的最高位是1则设置负数标志(只有当理解成有符号数运算时才去检查这个标志)。



[21] 也可以看作是把百位上的进位加回到个位上去,本来应该加1000,结果加了1,少加了999,正好把先前多加的999抵消了。