《计算机组成与体系结构(原书第4版)》 —2.4.2 补码系统
2.4.2 补码系统
数论学家在几百年前就已经知道从一个十进制数中减去一个数时也可以通过这个方法来获得,即被减数加上9(位数与被减数相同)与每位减数的差并加回一个进位。这称为获得了减数9的补码,或者更正式的说法是,找到基数减一的补码。比方说,我们想求解167-52的结果。已知999-52=947。根据9的补码运算,我们有167-52=167+947=1114。来自百位的“进位”加回到数据中,就得到一个正确的结果167-52=115。这种方法已经扩展到二进制操作中以简化计算机的运算。我们处理原码时补码系统带给的好处是,没有必要单独处理符号位,但我们仍然可以很容易地通过观察其高阶位,检查数的符号。
将补码系统的另一种方法想象成一辆自行车上的里程表。不同于汽车,当自行车倒退时,里程表也会倒退。假设里程表有3位数字,如果从0开始,并到700mile(1mile=1609.344m)结束,我们不能确定自行车是前进了700mile还是后退了300mile!这一难题最简单的解决方法是把数的范围削减一半,并使用001~500为正英里,501~999为负英里。实际上,我们减少了里程表可以测量的距离。但现在如果它的读数为997,那么我们知道自行车是向后走了3mile而不是向前走了997mile。数字501~999表示001~500的基数补码(下面介绍两种方法中的第二种),并用于表示负距离的数字。
1的补码
如上所述,在以10为基的数中,一个数字的基数减一的补码是从基数减1(即十进制中的9)中减去减数得到的。更加形式化的表述方式为:给定一个具有d位数字且基数为r的数字N,N的基数减一的补码定义为(rd-1)-N。对于十进制数,r=10,基数减一是10-1=9。例如,2468的9的补码为9999-2468=7531。对于二进制的等价运算,我们从一个较小的基数2中减去1,得到1。例如,01012的1的补码是11112-01012=10102。如上所述我们可以乏味地借位做减法,但是一些实验会说服你产生一个二进制数的1的补码(译者注:二进制数的1的补码一般称为反码),只需要把所有的1换成0,所有的0换成1。这种二进制位翻转在计算机硬件中实现起来非常简单。
在这一点上值得注意的是,虽然我们可以找到任何十进制数的9的补码或任何二进制数的1的补码,但是我们最感兴趣的是使用补码表示法来表示负数。我们知道执行一个减法时,如10-7,也可以考虑像10+(-7)这样“加上负数”。补码表示法允许我们把减法变为加法来简化减法,另一方面也给了我们一个表示负数的方法。因为我们不希望使用一个特殊位来表示符号(正如我们在原码表示中所做的那样)。我们需要记住,如果一个数是负数,那么应该将它转换为它的补码。结果应该在最左边的位上有一个1,表示这个数字是负数。
虽然一个数的1的补码严格地说是用2的幂减1再减去那个数得到的,但是我们经常把对负数使用1的补码的计算机称为1的补码系统,或使用1的补码运算的计算机。这可能有点误导,因为正数不需要补码。我们只对负数求补码,所以可以把它们变成计算机能理解的格式。例2.16阐述了这些概念。
例2.16用8位二进制表示2310和-910,假设一台计算机使用1的补码表示。
-910=-(000010012)=111101102与原码不同,在1的补码加法中没有必要使符号位与其他位分离。符号由自己保管。将例2.17与例2.10进行比较。
例2.17使用1的补码加法计算010011112加001000112。
假设我们希望从23中减去9。为了执行一个1的补码减法,我们首先用1的补码表示减数(9),然后将它加到被减数(23)上,我们现在实际上是将-9与23相加。高阶位将有一个1或0的进位,这个进位加到低阶位。(这就是所谓的尾进位循环和使用基数减一的补码的结果。)
例2.18使用1的补码运算,计算2310加-910。
例2.19使用1的补码运算,计算910加-2310。
我们怎么知道111100012实际上是-1410?我们只需要求这个二进制数的1的补码(记住它必须是负数,因为最左边的位是负的)。111100012的1的补码是000011102,它是14。
1的补码的主要缺点是我们仍然要有两个表示为零的数:000000002和111111112。由于这个原因和其他原因,计算机工程师早已不再使用1的补码了,而是使用更有效的2的补码以表示二进制数。
2的补码
2的补码是基数补码的一个例子。给定一个数字N,它的基数为r,具有d位数字,N的基数补码定义为:当N=0时为0,N≠0时为rd-N。基数补码通常比基数减一的补码更直观。使用我们的里程表的示例,前进2mile的10的补码是103-2=998,我们已经商定了这个距离是指负(向后)距离。同样,在二进制中,4位二进制数00112的2的补码为24-00112=100002-00112=11012。
仔细观察你会发现,2的补码仅比1的补码多1。因此,求解二进制数的2的补码只需要将二进制数的各位取反,然后末位加1即可。这大大简化了加法和减法运算。因为减数(求补和加的数字)是在一开始增加的,而且没有尾进位循环的担心。我们可以简单地丢弃涉及高阶位的任何进位。和1的补码一样,2的补码也是一个数的补码,而使用这种表示法来表示负数的计算机被称为2的补码系统,或称为使用2的补码运算。(译者注:二进制数的2的补码一般称为补码)。和以前一样,正数可以单独列出来;我们只需要对负数求补使它们变成2的补码形式。例2.20阐述了这些概念。
例2.20假设一台计算机使用2的补码表示,把2310、-2310和-910表示为8位二进制数。
因为正数在1的补码表示和2的补码表示中是相同的(以及在原码中),因此两个正的二进制数相加的过程相同。将例2.21与例2.17和例2.10进行比较。
例2.21使用2的补码加法,计算010011112加001000112的结果。
假设我们给出一个以二进制表示的数字,并想知道其等价的十进制数。这对正数是很容易的。例如,要转换2的补码值000101112到十进制,我们只需转换这个二进制数字到十进制数,结果是23。但是,转换负数的2的补码值过程与把十进制转换到二进制的逆过程类似。假设我们给出了2的补码值为111101112,我们想知道等价的十进制数值。我们知道这是一个负数,但必须记住它是使用2的补码表示的。我们首先翻转这些位,然后再加1(找到1的补码并加1)。这个结果如下:000010002+1=000010012。这等同于十进制值9。但是,开始的原始数字是负数,所以我们最终使用9作为等价于111101112的十进制数。
以下两个示例说明如何使用2的补码表示法执行加法(减法同理,因为减去一个数字是加上它的负数)。
例2.22使用2的补码运算,计算910加-2310的结果。
留给你一个练习,验证111100102实际上是使用2的补码表示的-1410。
例2.23使用2的补码运算,求解用二进制表示的2310与-910的和。
在2的补码中,两个负数相加会产生一个负数结果,就像我们所期望的那样。
例2.24使用2的补码加法运算,求111010012(-23)与111101112(-9)的和。
注意在例2.23和例2.24中丢弃进位没有导致错误的结果。如果两个正数相加并且和是负数,或者如果两个负数相加并且结果为正,则会发生溢出。当使用2的补码表示法时,如果一个正数和一个负数相加,不可能发生溢出。整数的乘法和除法除非使用复杂的算法,否则乘法和除法运算在获得结果之前会消耗相当多的计算周期。在这里,我们只讨论执行这些操作最直接的方法。现实系统中,专用硬件用于优化吞吐量,有时并行执行部分计算。好奇的读者可能会想研究在本章结尾参考文献中的一些更优的方法。
计算机使用的最简单的乘法运算类似于人类使用的传统的用铅笔和纸进行运算的方法。二进制数的完全乘法表不能更简单了:0乘以任何数结果都为0,以及1乘以任何数结果还是那个数。
为了说明简单的计算机乘法,我们首先将被乘数和乘数写入两个单独的存储区域。还需要第三个放结果的存储区域。从低位开始,指针设置为乘数的每个数字。对于乘数中的每个数字,被乘数向左“移位”一位。当乘数为1时,“移位”的被乘数加到部分乘积的累加和中。因为对于乘数中的每一位,被乘数都需要移动一位,所以乘数、被乘数和结果都需要双精度的工作空间。
执行二进制除法有两种简单的方法:既可以迭代地从被除数中减去分母,也可以使用与小学学的长除法相同的试错法。与乘法一样,对于二进制除法最有效的方法超出了本书范围,读者可以在本章末尾的参考文献中找到。
不管使用的算法相对效率如何,除法总是会导致计算机崩溃的操作。当尝试除以零或当两个数值相差极大的数作为操作数时,情况更特别。当除数远远小于被除数时,我们会看到一个称为除法下溢的情况,即计算机将这种情况视为除数等于0,这是不可能的。
计算机可以区分整数除法和浮点数除法。整数除法的结果分为两部分:商和余数。浮点数除法产生一个用二进制表示的小数。在这两种类型的除法之间有着明显的不同,因此每种除法都需要自己的特殊电路。浮点计算是在名为浮点单元(FPU)的专用电路中进行的。
例 求解000001102和000010112的乘积。
简单的计算机电路可以使用很容易记住的规则检测溢出情况。在例2.23和例2.24中你会注意到,进入符号位的进位(一个1从前一个位置进位到符号位的位置)与出符号位的进位(一个1从符号位出并丢弃)是相同的。当这些进位相等时,不发生溢出。当它们不同时,在算术逻辑单元中的溢出指示器被置位,表示结果不正确。
检测有符号数运算是否存在溢出的简单规则:如果进符号位的进位等于出符号位的进位,则无溢出。如果两者不同,出现溢出(从而出现错误)。
最难的是让程序员(或编译器)来持续检查溢出情况。例2.25表示有溢出,因为进符号位的进位(即进来一个1)不等于出符号位的进位(即出去一个0)。
例2.25使用2的补码运算,求解12610与810的二进制之和。
一个1被进位到最左边的位中,但是从这一位出来的进位是一个0。因为这些进位不相等,所以发生了溢出。(我们可以很容易地看到两个正数相加,但结果却是负的。)我们回到2.4.6节的这个主题。
2的补码是表示有符号数的最普遍选择。这个算法对加法和减法都相当容易,对于0它有最好的表示(全0位),是自反相的,并且容易扩展到更多的位。最大的缺点是在由N位表示的取值范围内可看到不对称性。例如,4位使用原码的数允许表示的值为-7~+7。但是,使用2的补码可以表示的值为-8~+7,这通常会使学习补码表示的人很混乱。要了解为什么+7是使用4位2的补码表示的最大数,只需要记住第一位必须是0。如果剩余的位都是1(可能的最大数值),我们得到01112,这就是7。对此的立即反应是最小的负数应该是11112,但可以看到11112实际上是-1(翻转位,加1,并使数字为负)。那么我们如何用4位二进制数的2的补码表示-8呢?它应表示为10002。我们知道这是一个负数。如果我们翻转位(0111),再加1(得到1000,这就是8),并使其为负,我们得到-8。
- 点赞
- 收藏
- 关注作者
评论(0)