计算机的算术运算.doc

第4章 计算机的算术运算数字的精度对科学非常重要。Darcy Wentworth Thompson On Growth and Form, 19174.1.简介14.2 带符号数与无符号数24.3 加法与减法174.4 逻辑运算264.5 构造算术逻辑单元354.6乘法504.7 除法694.8.浮点运算834.9.实际资料：PowerPC和80x86中的浮点部件1174.10.谬误和陷阱1224.11 结论1274.12.历史回顾和参考文献1344.13 重要术语1484.14 习题149计算机的五个典型部件4.1.简介计算机中的字（word）是由位（bits）组成的，因此，字可以表示为二进制的数字。大家都知道，自然数（0，1，2等等）既可以用十进制的形式表示，也可以用二进制的形式表示，但是，其它一些常见的数又如何表示呢？例如， 如何表示负数？ 可以用计算机中的字表示的最大的数是多少？ 如果某一操作所产生的结果比一个字所能表示的最大的数还大，那会出现什么情况呢？ 小数和实数如何表示？奔腾芯片曾经出过一个臭名昭著的浮点运算错误，你可能会问，这到底是怎么一回事呢？在所有这些问题的背后，都有一个很基本的原理需要弄清楚：硬件究竟是如何进行加法、减法、乘法以及除法运算的？本章的目的就是要揭示这些基本原理；这其中包括如何表示各种数据，用什么算法来实现算术运算，硬件是如何实现这些算法的，以及在指令集中如何表示所有这些有关的内容，等等。有了这些知识之后，你就能解释在使用计算机的过程中遇到的各种不明白的事情了。（如果你对如何表示带符号的二进制数很熟悉的话，就可以跳过下一节，直接转到220页的4.3节）。4.2 带符号数与无符号数我们可以通过各种基数（base）来表示一个整数。正象我们在第三章中所介绍的那样，人们通常习惯于以10为基数，而在计算机中则更适合于以2为基数。由于我们常常既要用到十进制数，又要用到二进制数，因此，为了避免混淆，我们用下标10来表示十进制数，而用下标2表示二进制数。对于任何一种进制（设基数为base）而言，其中的第i个数字d所代表的值为：d Base i其中，i由右至左从0开始依次递增。自然而然地，由此也得到一种对字（word）中的各个位进行编号的方法：直接将与该位对应的基数的幂次作为其编号即可。例如：10112代表了：(1 23) + (0 22) + (1 21) + (1 20)10= (1 8) + (0 4) + (1 2) + (1 1)10= 1110在这个字中，各位按从右到左的顺序依次编号为0, 1, 2, 3, 。下图给出的是MIPS机器一个字中各个数位的编号方法，并标出了数10112的放置位置：31302928272625242322212019181716151413121110987654321000000000000000000000000000001011一个字的各位既可以按由低位到高位的顺序从左至右排列，也可以从右至左排列。因此，“最左位”（leftmost）和“最右位”（rightmost）这两个词是有歧义的。为了避免这个问题，我们用最低有效位（Least significant bit; LSB）来表示上例中最右侧的第0位，而用最高有效位（Most significant bit; MSB）来表示最左侧的第31位。MIPS机器的字长为32位，因此，一个字可以用来表示232种32位长的不同模式。很自然地，我们可以用这些组合来分别表示数字0到232-1（一共4,294,967,29510个）： = = = . = = = 软硬件接口将2作为基数，这并不符合人们的习惯。由于人有10个手指头，我们自然而然地就习惯了以10为基数的计数法。那么，计算机为什么不采用十进制呢？实际上，最早的商用计算机确实提供了一些十进制操作。但问题是，由于计算机只能用“开”和“关”这两种信号来表示这些数据，因此，一个十进制数位其实也是用若干个二进制位来表示的。人们发现，计算机采用十进制时效率很低，因此，后来的机器采用的几乎全都是二进制，只是在进行一些不很常用的输入输出操作时才会用到十进制。用ASCII字符表示数字与用二进制表示数字例题:整数除了可以用2的补码来表示（参见第142页的图3.15）之外，我们还可以用ASCII数字字符来表示一个数字。如果要表示的数字为10亿，那么，用ASCII数字字符表示法所需要的存储空间是用32位长的二进制表示法的多少倍？解:10亿就是1,000,000,000，需要用10个ASCII数字字符来表示，每个字符长度为8位。因此，所需的存储空间是用32位长的二进制表示法的(108)/32=2.5倍。除了需要更多的存储空间以外，对于用这种方法表示的数字，硬件在做加法、减法、乘法以及除法等各种运算时，所执行的操作也要比二进制表示法复杂得多。正是基于这些原因，计算机专家们才一致认为，在计算机中使用二进制表示法是再自然不过的了，即使只是偶尔使用十进制表示法，也会让他们感到奇怪的。要注意的是，二进制位的各种组合方式不过是用来代表某个数字而已。其实，每一个整数实际上都有无数位；在这无数位中，除了最右边的若干位以外，其余的都是0。只不过我们通常不写出数字左边的这些0而已。我们在4.5节到4.7节中将提到，可以用硬件的方式直接对以二进制方法表示的数进行加法、减法、乘法以及除法等运算。如果这些运算的正常结果无法用硬件所能提供的有效位数表示出来，就称这种现象为“溢出”（overflow）。溢出发生时，操作系统和相应的程序必须决定如何处理这种现象。计算机程序既要处理正数，也要处理负数，因此，我们必须设计一种表示方法，用以区分正数与负数。最直观的办法是增加一个单独的表示正负的符号，这只要用一个二进制位就可以方便地实现。这种表示方法称为符号加绝对值（sign and magnitude）表示法，又称为原码。不过，原码表示法也有一些不足之处。首先，我们应该将符号位放在哪里呢？放在数的最左边？还是放在最右边？这个问题不是很好解决的。早期的计算机中，有的将符号位放在数的左边，有的则放在右边。第二个缺点则是在做加法运算时，如果用原码表示法表示数的话，由于我们无法提前确定结果的符号，因此，就必须单独设立一个步骤，专门用来设置结果的符号。再有，单独的符号位意味着这种表示法会造成两个零值：一个正零和一个负零，在这种情况下，程序员稍不留神就会出问题。由于有这些不足，很快就没有人再用这种原码表示法了。要想找到一种更好的表示方法，首先就要弄清楚，用一个小的正整数减去一个较大的正整数时会得到怎样的结果。在做这样的减法运算时，必须从被减数左侧的0中（通常不写出来）借位，而运算结果（差）的左侧则是无数位的1。因此，如果我们没有更好的办法的话，就只好认为，若最高位为0，所表示的就是正整数，而若最高位为1的话，所表示的就是负整数。这种表示带符号数的方法称为2的补码表示法（twos complement representation）：0000 0000 0000 0000 0000 0000 0000 00002=0100000 0000 0000 0000 0000 0000 0000 00012=1100000 0000 0000 0000 0000 0000 0000 00102=2100111 1111 1111 1111 1111 1111 1111 11012=2,147,483,645100111 1111 1111 1111 1111 1111 1111 11102=2,147,483,646100111 1111 1111 1111 1111 1111 1111 11112=2,147,483,647101000 0000 0000 0000 0000 0000 0000 00002=-2,147,483,648101000 0000 0000 0000 0000 0000 0000 00012=-2,147,483,647101000 0000 0000 0000 0000 0000 0000 00102=-2,147,483,646101111 1111 1111 1111 1111 1111 1111 11012=-3101111 1111 1111 1111 1111 1111 1111 11102=-2101111 1111 1111 1111 1111 1111 1111 11112=-110表中的上半部分是正整数，有效值的范围从0到2,147,483,64710（231-1）；正整数与原码表示法表示的正整数是一样的。接下来的（10000002）表示的则是绝对值最大的负整数-2,147,483,64810（-231）。然后依次为-2,147,483,64710（100000012）直至-110（111111112），其绝对值依次递减。用2的补码表示法可以大大地方便硬件设计人员。不过，在用它来表示带符号整数时，有一个负数-2,147,483,64810是没有相应的正数与其对应的（即其相反数不能用这种方法表示出来）。虽然这种不平衡的情况有时候也会让一些特别在意这一点的程序员伤脑筋，但是，原码表示法则更糟，因为它同时使硬件设计人员和程序开发人员都觉得不方便。因此，如今所有的计算机都用2的补码来表示带符号的整数。2的补码表示法有一个很大的优点，即所有负数的最高有效位（MSB）为1。因此，只要检查一下最高有效位，硬件就能判断某个数是正数还是负数（姑且把0也当成正数）。这个特殊的位称为符号位（sign bit）。在考虑了符号位的特殊情况以后，我们仍然可以用各位的值与2的相应次幂的乘积之和来表示该整数（这种方法对正整数和负整数都适用）。这一点如下式所示（其中，xi表示整数x的第i位）：(x31 (-231) + (x30 230) + (x29 229) + + (x1 21) + (x0 20)其中，符号位的值与-231相乘，而其它位则与基数（2）相应幂次的正值相乘。将二进制数转换为十进制数例题:如下用2的补码表示的二进制数相对应的十进制数是多少？1111 1111 1111 1111 1111 1111 1111 11002解:将各位的值代入上面的公式，得：(1 -231) + (1 230) + (1 229) + + (1 22) + (0 21) + (0 20)= -231 + 230 + 229 + + 22 + 0 + 0= -2,147,483,64810 + 2,147,483,64410= -410后面我们还要介绍一种将二进制数转换为十进制数的更简便的方法。软硬件接口带符号数与无符号数的区别不仅表现在算术运算上，还表现在将这些数据存入寄存器的过程中。将带符号数写入寄存器时，需要用符号位填满寄存器左侧中多余的位我们称这一过程为符号扩展（sign extension）其目的是为了使这个寄存器能以正确的形式表示该带符号数。而无符号数装入时，只需将左侧剩余的位置全部填上0即可，因为其中的数据是没有正负之分的。将32位字长的数据装入32位宽的寄存器时，带符号数与无符号数的区别是没有什么意义的，它们的装入过程是一样的。但在往寄存器中写入长度为一个字节的整数时，就必须注意这种区别了。MIPS机器提供了两种形式的字节装入指令；一种是带符号的字节装入（load byte; lb），它将要装入的字节看成一个带符号整数，并用符号位填充寄存器左侧的24个剩余的二进制位；另一种无符号的字节装入（load byte unsigned; lbu）则将要装入的字节看作无符号的整数。由于程序中通常是用字节来表示字符类型的数据（characters），很少将其当成带符号的短整数，因此，几乎所有的字节装入都是lbu。就像无符号数的算术运算结果可能超出硬件的表示范围（即溢出）一样，在对用2的补码表示的数进行算术运算时也有可能出现溢出的现象。对于2的补码表示法而言，当最高有效位（即所谓的保留位）的值与左侧无限多的符号位不相等时（即符号位出错），就发生了溢出。也就是说，如果负数的最高位为0或正数的最高位为1，那就是溢出了。软硬件接口与我们前面讨论的不同的是，内存地址都是自然而然地从0顺次增长到最大地址值。也就是说，负的地址是没有意义的。由此可见，虽然程序处理的数据有时候既可能为正数又可能为负数，但有些类型的数据则只能是正数。各种编程语言都很好地反映了这种区别。例如，C语言中将前一种数据称为整数（integers；在程序中用int定义），而后一种数据则称为无符号整数（unsigned integers；用unsigned int定义）。比较指令也必须考虑到这一两义性问题。有时候，最高有效位为1的二进制数表示的是一个负整数，显然，这个数比所有最高有效位为0的正数都要小。而另一方面，对于无符号数而言，最高有效位为1的数则比任何一个最高有效位为0的数都要大。MIPS提供了两组不同类型的小于（less than）指令，用来处理所有这些情况。“小于等于时置1”（set on less than；slt）指令和“小于等于立即数时置1”（set on less than immediate；slti）对带符号整数进行比较，而“小于等于无符号数时置1”（set on less than unsigned; sltu）以及“小于等于无符号立即数时置1”（set on less than immediate unsigned; sltiu）则对无符号整数进行比较。带符号数的比较与无符号数的比较例题:设寄存器$s0中包含有如下二进制数据：1111 1111 1111 1111 1111 1111 1111 11112而寄存器$s1中则有如下二进制数据：0000 0000 0000 0000 0000 0000 0000 00012那么，下面的两条指令执行完以后，寄存器$t0和$t1的值分别是多少？slt$t0, $s0, $s1# 带符号数的比较sltu$t1, $s0, $s1# 无符号数的比较解:$s0的值是-1（带符号整数）或4,294,967,29510（无符号整数）。而无论$s1是带符号数还是无符号数，它的值都是1。因此，寄存器$t0的值将变为1（因为-110110）。在介绍整数加法和整数除法的有关内容之前，我们先来看一看几种处理2的补码表示法的简便方法。第一种简便方法是如何更快地求出一个用2的补码表示的整数的相反数。我们只要将原来为1的各位改为0，为0的各位改为1，然后再将结果加1即可。这种方法基于这样一个原理：一个整数和它的相反数之和为1111112（即-1）。由于，因此，即。求相反数的简单方法例题:求210的相反数，然后再求出所求得的-210的相反数；请列出演算过程。解:210 = 0000 0000 0000 0000 0000 0000 0000 00102对各位求反，然后再加1得：1111 1111 1111 1111 1111 1111 1111 11012+ 12=1111 1111 1111 1111 1111 1111 1111 11102= -210反过来，我们再将1111 1111 1111 1111 1111 1111 1111 11102的各位求反，然后加1：0000 0000 0000 0000 0000 0000 0000 00012+ 12=0000 0000 0000 0000 0000 0000 0000 00102= 210第二种简便方法则告诉我们如何将一个n位的二进制数转换为一个多于n位的数。例如，在取数、存数、分支转移、加法以及小于等于时置1等指令中常常包括了一个立即数字段；这个字段是一个16位长的以2的补码形式表示的带符号数，其有效值的范围从-32,76810（-215）到32,76710（215-1）。在将这个立即数字段与某个32位寄存器相加之前，机器首先要将这个16位长的立即数转换成与之相等的32位二进制数。我们要介绍的简便方法就是将16位立即数的最高有效位（即符号位）填满32位中多出的那些位，而原有的位则原样填充到新字的低16位。这种方法常常被称为“符号扩展”（sign extension）。符号扩展例题:将16位的二进制数210和-210转换成32位的二进制数。解答:可以用16位二进制数将210表示为：0000 0000 0000 00102 = 210要将其转换成32位二进制数，应先将最高有效位（0）复制16份，将它们填到整个字左半部分，然后，再将原来的16位填至右半部分：0000 0000 0000 0000 0000 0000 0000 00102 = 210现在，让我们用前面介绍的简便方法对用16位二进制表示的数210求反。即由0000 0000 0000 00102 = 210求得：1111 1111 1111 11012+ 12=1111 1111 1111 11102然后，再用32位二进制数来表示-210。也就是将符号位复制16份并将其放置在原来16位的左侧：1111 1111 1111 1111 1111 1111 1111 11102 = -210这种方法之所以是正确的，主要是因为，对于用2的补码表示的整数来说，正数的左侧实际上有无数个0，而负数的左侧则有无数个1。只是在用二进制方式表示它们时，由于硬件寄存器与存储单元的长度有限，只好将左侧多出的这些0和1截掉；而符号扩展时不过是恢复了其中的一部分而已。最后一种简便方法我们曾经在第三章中提到过，就是在书写比较长的二进制表示的数时，我们可以用更大的基数来表示它，这样，既能方便地转换回二进制，又缩短了长度。由于计算机中几乎所有数据的位数都是4的倍数，因此，我们常用十六进制数（hexadecimal；即基数为16）来表示它们。因为基数16是2的倍数，因此，我们可以很方便地将二进制数转换成十六进制数：只要将每四位二进制位作为一组，将它用一个十六进制的数字表示出来即可。反之亦然。图4.1列出了十六进制数字与二进制数之间的转换关系。我们可以用下标hex来表示某个数是十六进制数，或者用C语言中表示十六进制数的办法，即用0xnnnn来表示十六进制数。十六进制二进制十六进制二进制十六进制二进制十六进制二进制0hex000024hex010028hex10002chex110021hex000125hex010129hex10012dhex110122hex001026hex01102ahex10102ehex111023hex001127hex01112bhex10112fhex11112图4. 1 十六进制数二进制数转换表.在将十六进制数转换为二进制数时，只要将十六进制数字替换为相应的四个二进制数字即可；反之亦然。如果二进制数的位数不是4的倍数，则按从右往左的顺序进行转换。将二进制数转换为十六进制数的简便方法例题:将下面用十六进制表示的数转换成二进制，将二进制的数转换成十六进制数：eca8 6420hex0001 0011 0101 0111 1001 1011 1101 11112解:将十六进制数转换为二进制数（查表即得）：（如218页图）将二进制数转换成十六进制数：（如218页图）总结本节主要讨论了如何在计算机字长的范围内表示正整数和负整数。虽然各种方案各有其优缺点，但是，自从1965年以来，所有的计算机都采用了2的补码表示法。图4.2列出了本节中提到的MIPS汇编语言的一些补充内容（MIPS汇编语言的更多细节请参见本书最后部分的附录）。MIPS汇编语言中的操作数类别举例说明32个寄存器$s0-$s7,$t0-$t9,$gp,$fp,$zero,$sp,$ra,$at用于存放需要迅速存取的数据。在MIPS中，算术运算的操作数必须位于寄存器中。MIPS寄存器$zero的值永远为0；寄存器$at是为汇编程序保留的，用来存放大的常数。230个内存字Memory0,Memory4, Memory4294967292内存中的数据只能通过数据读数（load）和存数（store）指令来访问。MIPS的地址是按字节编码的，因此，相邻字的地址相差4。内存单元有多种功能，它们既可以用来存放各种数据与运算结果（例如数组），也可以用来在过程调用时保存各寄存器原有的值，等等。MIPS汇编语言中的指令分类指令类型 指令示例含义说明算术运算加法add $s1,$s2,$s3$s1=$s2+$s3三个操作数减法sub $s1,$s2,$s3$s1=$s2-$s3三个操作数立即数加法addi $s1,$s2,100$s1=$s2+100与立即数相加数据存取取一个字lw $s1,100($s2)$s1=Memory$s2+100将一个字从内存读入寄存器中存一个字sw $s1,100($s2)Memory$s2+100=$s1将一个字从寄存器中写入内存取一个字节（无符号数）lbu $s1,100($s2)$s1=Memory$s2+100将一个字节从内存读入寄存器中存一个字节sb $s1,100($s2)Memory$s2+100=$s1将一个字节从寄存器中写入内存将常数读入高16位lui $s1,100$s1=100216将常数写入寄存器的高16位条件转移相等时转移beq $s1,$s2,25if ($s1=$s2) go to PC+4+100判断两个数是否相等；根据PC的值跳转不等时转移bne $s1,$s2,25if ($s1!=$s2) go to PC+4+100判断两个数是否不等；根据PC的值跳转小于时置1slt $s1,$s2,$s3if ($s2$s3) $s1=1;else $s1=0判断一个寄存器的值是否小于另一个寄存器的值；带符号数的比较小于立即数时置1slti $s1,$s2,100if ($s2100)$s1=1;else $s1=0判断一个寄存器的值是否小于一个立即数；带符号数的比较小于无符号数时置1sltu $s1,$s2,$s3if ($s2$s3)$s1=1;else $s1=0判断一个寄存器的值是否小于另一个寄存器的值；无符号数的比较小于无符号立即数时置1sltiu $s1,$s2,100if ($s2100)$s1=1;else $s1=0判断一个寄存器的值是否小于一个立即数；无符号数的比较无条件转移指令跳转j 2500go to 10000程序跳转至目的地址跳转至寄存器所指地址jr $rago to $ra用于switch语句以及过程调用返回跳转并链接jal 2500$ra=PC+4;go to 10000用于过程调用图4. 2 MIPS指令体系（截止至本节所涉及到的内容）.彩色的部分是第三章图3.20（第155页）中所没有的部分。有关MIPS汇编语言更详细的情况请参见本书最后的附录。细节:“2的补码表示法”这一名称来源于这样一个规则：如果将一个n位的二进制数与其相反数都看作无符号数并将它们相加的话，所得到的结果为2n。因此，用2的补码表示的数x的相反数为2n-x。除了前面介绍的两种表示数的方法以外，还有第三种表示方法，即所谓“反码表示法”。采用反码表示法时，一个数的相反数就是将其各位都求反（将0变为1，1变为0）所得的数。由于一个数x的相反数为2n-x-1，因此，我们称这种表示法为反码表示法。与原码表示法比起来，反码表示法也有一些明显的优点，因此，有些用作科学计算的计算机采用的就是这种表示法。除了有两个0：正零00.002与负零11112以外，它与2的补码表示法是很相似的。反码表示法所能表示的最大负数为100002，即-2,147,483,64710，因此，正数与负数的数目是相等的。采用这种表示法时，加法器做减法运算时也需要有额外的一个步骤用来判断结果的符号。由于这个原因，如今占统治地位的还是2的补码表示法。最后，再介绍另一种数的表示方法。在这种表示法中，最小负数用000002表示，而最大正数则用111112表示，而0则用10002来表示。这种方法相当于是将所有整数都加上了一个正的偏移量，使得它们都能用正数来表示。因此，我们将其称为移码表示法（biased notation）。4.3 加法与减法很显然，加法是计算机中不可缺少的运算。计算机做加法与我们手工笔算加法的原理是一样的，即按从右到左的顺序一位一位地求和，并将进位加到左侧相邻的高位。而减法则是通过加法实现的：只要将减数求反，然后再相加即可。二进制加法与减法例题:请用二进制加法求610和710的和，并求710与610之差。解:0000 0000 0000 0000 0000 0000 0000 01112= 710+0000 0000 0000 0000 0000 0000 0000 01102= 610 =0000 0000 0000 0000 0000 0000 0000 11012= 1310所有操作都在低四位进行；图4.3画出了求和与进位的情况。进位值标在括号中，而箭头则表明它们到底是向哪一位进位的。图4. 3 二进制加法（带有进位情况的图示）.从右边数第1位是1和0相加，该位的结果为1，进位为0。第2位为0+1+1。因此，第2位的结果为0，进位为1。第3位为1+1+1之和，该位的进位与和都是1。第4位为1+0+0，因此，和为1而进位为0。710与610之差可以直接通过减法求得：0000 0000 0000 0000 0000 0000 0000 01112= 710-0000 0000 0000 0000 0000 0000 0000 01102= 610 =0000 0000 0000 0000 0000 0000 0000 00012= 110或者，也可以将-6用2的补码表示，然后再与7相加：0000 0000 0000 0000 0000 0000 0000 01112= 710+1111 1111 1111 1111 1111 1111 1111 10102= -610 =0000 0000 0000 0000 0000 0000 0000 00012= 110我们曾在前面提到过，当计算机的硬件（在这个例子中，硬件的字长为32位）无法表示运算的结果时，就会发生溢出现象。在加法运算中，什么时候会发生溢出呢？两个加数的符号相反时，是不可能发生溢出的。这是因为在这种情况下，和的绝对值肯定不会大于两个加数中任何一个的绝对值（例如，-10+4=-6）。由于加数可以用32位字长表示，而和的绝对值又不会比任何一个加数的绝对值更大，因此，和也一定能用32位字长表示。也就是说，正数和负数相加时，是不会发生溢出的。类似的，在一定情况下，减法运算也肯定不会发生溢出，只不过其条件恰好与加法相反。当减数和被减数的符号相同时，溢出是不可能发生的。为了说明这一点，我们只需注意到x y = x + (-y)就可以了。在做减法时，可以将减数求反，然后再与被减数相加即可。因此，如果减数与被减数符号相同的话，我们实际上是对两个不同符号的整数做加法运算。而前面已经解释过，在这种情况下是不会发生溢出的。弄明白了在什么情况下加法和减法运算肯定不会发生溢出之后，我们还必须回答另一个问题：究竟何时会发生溢出？这个问题的答案是：对于加法而言，溢出发生在两个正数相加，而结果为负时；或者两个负数相加而结果为正时。显然，将两个32位的整数相加或者相减时，结果有可能需要33位才能完整地表示出来。缺少第33位意味着发生溢出时，符号位实际上被结果的数值部分占据了，而没有被设置成结果真正的符号位。由于我们所缺少的只是一个额外的数位，因此，只有符号位一位是不正确的。也就是说，最高位的进位值就是结果的符号位。对于减法而言，如果正数减去负数而结果为负数，或者负数减去正数而结果为正数，那么，此时就发生了溢出。这意味着在做减法时从符号位借了1。图4.4列举了溢出发生时操作数、运算类型以及运算结果的各种可能的组合情况。（习题4.42介绍了硬件用来判断溢出是否发生的非常简便的方法）。我们前面介绍的是在使用2的补码表示法的情况下计算机如何检测是否发生了溢出。如果是无符号整数的话，那又会是什么情况呢？通常情况下，无符号整数一般都是用来表示内存地址的，溢出即使发生，也大多被忽略掉了。因此，在设计计算机时，有的情况下需要忽略溢出的条件，而有的情况下则必须能识别出是否发生了溢出。MIPS解决这个问题的办法是采用两种不同的算术运算指令来分别处理这两类情况： 加法（add）、立即数加法（addi）以及减法（sub）指令在发生溢出时会产生异常。 无符号数加法（addu）、无符号立即数加法（addiu）以及无符号数减法（subu）在发生溢出时不会产生异常。由于C语言通常都是忽略溢出情况的，因此，无论是对何种类型的变量做算术运算，MIPS上的C语言编译器都会选用无符号的算术运算指令，即addu, addiu以及subu。而MIPS上的Fortran编译器则会根据操作数的不同类型来选择合适的算术运算指令。运算类型操作数A操作数B结果A + B 0 0 0A + B 0 0 0A B 0 0 0A B 0 0 0图4. 4 加法和减法的溢出条件软硬件接口CPU的设计者必须决定通过什么方式来处理算术运算时发生的溢出情况。有的程序设计语言（例如C语言）将此类异常情况的处理权留给了硬件的设计者。而另外一些语言，如Ada以及Fortran等，则要求机器在发生溢出异常时通知相应的程序，至于程序得知异常发生了以后应该采取什么措施，则可以由程序员在程序中指定，或者采用编译器设置的缺省处理方案。MIPS在检测到溢出发生时，会产生一个异常（exception），有的计算机也将异常称之为中断（interrupt）。异常（或曰中断）实质上是一种不需要在程序中显式调用的过程。溢出发生时，造成溢出的那条指令的地址被存放到一个特定的寄存器中，然后，计算机跳转到一个预先定义好的地址，去执行与该异常情况相对应的异常处理函数。之所以要将造成溢出的指令地址保存起来，主要是为了在有的情况下，在纠正了出错情况以后，程序还能够继续运行。（5.6节中介绍了有关异常的更多细节，而第7章和第8章则介绍了其它一些会导致异常和中断的情况）。MIPS中有一个名为异常程序计数器（Exception program counter; EPC）的寄存器，用来保存造成异常的那条指令的地址。指令mfc0（move from system control）可以将EPC中的地址复制到某个通用寄存器中，这样，只需通过一条跳转语句，程序就可以返回到造成异常的那条指令处继续执行。总结 这一节的主要内容是有关溢出的问题。由于计算机中的数字从本质上来讲具有无限多的位数，因此，无论我们采用什么方法来表示一个数，在进行算术运算时，所得到的结果很有可能无法用计算机中位数有限的字长来表示。无符号数算术运算的溢出情况是很容易检测到的，不过，我们通常都将这类溢出情况忽略掉了；因为无符号数（即自然数）最常见的用处是用作地址，而地址运算发生溢出时，程序一般都不会太在意。而对用2的补码表示的数进行算术运算时，溢出就成了一个必须注意的问题。由于有的软件系统需要检测溢出发生的情况并做一定的处理，因此，如今的计算机都有办法检测到这种情况。图4.5列出了本节中提到的有关MIPS指令系统结构的一些补充内容。MIPS汇编语言中的操作数类别举例说明32个寄存器$s0-$s7, $t0-$t9, $gp, $fp, $zero, $sp, $ra, $at用于存放需要迅速存取的数据。在MIPS中，算术运算的操作数必须位于寄存器中。MIPS寄存器$zero的值永远为0；寄存器$at是为汇编程序保留的，用来存放大的常数。230个内存字Memory0,Memory4,Memory4294967292内存中的数据只能通过数据读数（load）和存数（store）指令来访问。MIPS的地址是按字节编码的，因此，相邻字的地址相差4。内存单元有多种功能，它们既可以用来存放各种数据与运算结果（例如数组），也可以用来在过程调用时保存各寄存器原有的值，等等。MIPS汇编语言中的指令分类指令类型指令示例含义说明算术运算加法add $s1,$s2,$s3$s1=$s2+$s3三个操作数；检测溢出情况减法sub $s1,$s2,$s3$s1=$s2-$s3三个操作数；检测溢出情况立即数加法addi $s1,$s2,100$s1=$s2+100与常数相加；检测溢出情况无符号数加法addu $s1,$s2,$s3$s1=$s2+$s3三个操作数；不检测溢出情况无符号数减法sub $us1,$s2,$s3$s1=$s2-$s3三个操作数；不检测溢出情况无符号立即数加法addiu $s1,$s2,100$s1=$s2+100与常数相加；不检测溢出情况数据存取取一个字lw $s1,100($s2)$s1=Memory$s2+100将一个字从内存读入寄存器中存一个字sw $s1,100($s2)Memory$s2+100=$s1将一个字从寄存器中写入内存取一个字节（无符号数）lbu $s1,100($s2)$s1=Memory$s2+100将一个字节从内存读入寄存器中存一个字节sb $s1,100($s2)Memory$s2+100=$s1将一个字节从寄存器中写入内存将常数读入高16位lui $s1,100$s1=100216将常数写入寄存器的高16位条件转移相等时转移beq $s1,$s2,25if ($s1=$s2) go to PC+4+100判断两个数是否相等；根据PC的值跳转不等时转移bne $s1,$s2,25if ($s1!=$s2) go to PC+4+100判断两个数是否不等；根据PC的值跳转小于时置1slt $s1,$s2,$s3if ($s2$s3) $s1=1;else $s1=0判断一个寄存器的值是否小于另一个寄存器的值；带符号数的比较小于立即数时置1slti $s1,$s2,100if ($s2100)$s1=1;else $s1=0判断一个寄存器的值是否小于一个立即数；带符号数的比较小于无符号数时置1sltu $s1,$s2,$s3if ($s2$s3)$s1=1;else $s1=0判断一个寄存器的值是否小于另一个寄存器的值；无符号数的比较小于无符号立即数时置1sltiu $s1,$s2,100if ($s2100)$s1=1;else $s1=0判断一个寄存器的值是否小于一个立即数；无符号数的比较无条件转移跳转j 2500go to 10000程序跳转至目的地址跳转至寄存器所指地址jr $rago to $ra用于switch语句以及过程调用返回跳转并链接jal 2500$ra=PC+4;go to 10000用于过程调用图4. 5 MIPS指令体系（截止至本节所涉及到的内容）.彩色的部分是图4.2（第219页）之后才涉及到的内容。有关MIPS汇编语言更详细的情况请参见本书最后的附录。细节:虽然MIPS可以捕获到溢出异常，但是，和许多别的机器不一样的是，在MIPS中我们无法用条件转移指令来测试溢出异常是否发生。不过，我们可以设计一个MIPS指令序列，用来检测是否发生了溢出。对于带符号加法而言，我们可以设计如下的指令序列（请参见第329页“提高题”中xor和nor指令的定义）：addu$t0, $t1,$t2# 结果赋值给$t0，但不捕获溢出异常xor$t3, $t1,$t2# 检查两个加数的符号是否相同slt$t3, $t3,$zero# 如果两个加数符号不同，则将$t3设为1bne$t3,$zero,No_overflow# $t1和$t2符号不同，则跳转至No_overflow（未溢出）xor$t3, $t0,$t1# 符号相同；检查结果（和）的符号是否也与加数相同。如果符号与加数不同，则将$t3置为负数slt$t3, $t3,$zero# 如果和的符号与加数不同，则将$t3置为1bne$t3, $zero,Overflow# 结果与加数符号不同，故跳转至Overflow（溢出）而对于无符号数加法（$t0=$t1+$t2），相应的测试代码为：addu$t0, $t1,$t2# 求和，结果赋值给$t0nor$t3, $t1,$zero# 对$t1按位求反，赋值给$t3；# 结果为$t1的2的补码减1，即232-$t1-1sltu$t3, $t3,$t2# 如果(232-$t1-1)$t2则232-1$t1+$t2bne$t3,$zero,Overflow# 如果232-1$t1+$t2，则跳转至Overflow（溢出 ）细节:前面谈到，我们可以用mfc0指令将EPC中的地址复制到某个通用寄存器中，然后就可以通过jr指令（跳转至寄存器所指地址）返回因溢出而中断的代码处。不过，这同时也带来了一个有趣的问题：为了使用jr指令，我们必须将EPC的值复制到某个通用寄存器中，这样一来，程序返回到中断处时我们又怎么能够将所有寄存器恢复为它们原有的值呢？我们要么先将所有寄存器恢复原值，但已经复制好的EPC中的返回地址就会丢失，我们就不能用jr指令跳转回去。或者，除了保存有返回地址的那个寄存器以外，我们先将所有其它寄存器恢复原值，然后用jr指令跳转。但这就意味着，程序运行的任何时刻都有可能因为发生了异常情况而使得某个寄存器的值被无端地改变。这两种方案都不能使人满意。为了让硬件摆脱这种两难境地，MIPS程序员们都必须保留两个寄存器$k0和$k1，使它们专供操作系统使用。发生异常时，这两个寄存器中的值是不会被恢复的。就像MIPS的编译器不会使用寄存器$at，以便汇编程序可以将其用作临时寄存器一样（请参见第147页第三章有关硬件与软件接口的内容），编译器也不能使用寄存器$k0和$k1，而是将它们专门留给操作系统。异常处理函数可以将返回地址置入这两个寄存器中的任一个，并利用jr指令返回到造成异常的指令处继续执行。4.4 逻辑运算最早的计算机只能对完整的字进行运算，但人们很快就发现，如果能对一个字中的若干位进行运算，甚至是对单个的位进行运算，那将是非常有用的。例如，字符运算就属于这种类型，因为字符是用8位来表示的，每个字符只占用一个字中的一部分而已。有鉴于此，后来的计算机都增加了这方面的指令，并采取了其它一些相应的措施，从而使位操作变得更加简便。移位指令（shift）就属于这类指令之一；它将字中的所有位顺序向左或向右移动，并将空出来的各位填0。例如，设寄存器$s0的值如下所示：0000 0000 0000 0000 0000 0000 0000 11012执行左移（shift left）8位的指令以后，它的值将变为：0000 0000 0000 0000 0000 1101 0000 00002与左移指令相对应的是右移指令。在MIPS中，这两条移位指令的全称分别是逻辑左移指令（shift left logical；sll）及逻辑右移指令（shift right logical；srl）。上面的例子可以用MIPS指令表示如下（移位后的结果保存在寄存器$t2中）：sln$t2, $s0, 8# 寄存器$t2 = 寄存器$s0左移8位第三章中，我们在讲到指令的R格式时暂时没有对其中的shamt域进行说明。这个域用在移位指令中，用来存放移位的位数（shift amount）。因此，上述指令用机器语言表示出来就是：oprsrtrdshamtfunct00161080指令sll