计算机组成原理考点总结

《计算机组成原理》课程考点总结整理，内容较长，迁移至本博客。参考教材为唐朔飞《计算机组成原理》（第三版）。

• 在线阅读地址：https://weread.qq.com/web/bookDetail/acd32ce0811e4e902g019a39
• 离线下载地址：https://pan.baidu.com/s/1HoULLYxx-WC8kuWg5EHVtg?pwd=rmlp

芯片设计与连线题

基础知识

该考点涉及的基本知识包括存储器容量构成、存储器容量的扩展等等。

存储器容量

通常（若以位为单位）存储器的容量=存储单元个数×存储字长，存储字长就是单个存储单元的位数，前者和地址线相关，后者和数据线相关。

对于一个存储容量为$m\times n位$（其中$m$表示存储单元个数，$n$表示存储字长）的存储芯片，则该芯片的地址线数量为$\log_2m$（通常$m$是2的整数次幂），数据线数量为$n$，逻辑示意图如下。

存储器容量的扩展

由于单片存储芯片提供的存储容量与字长一般不能直接满足实际需求，所以经常是将若干存储芯片连接在一起组成特定机器的存储系统，这就是存储器扩展。存储器的扩展通常可以分为位扩展，字扩展以及位、字同时扩展。

位扩展，指的是只扩展存储字长，表现为被选中的芯片同时工作，但是与之相连的数据线增加了。

上图表示两片2114（1K×4位）组成1K×8位的存储系统。可以看出，两个芯片的数据引脚（每个4个，一共8个）与处理器的8条数据线$D_7,D_6,\dots,D_0$相连，而不涉及片选信号（$\overline{CS_0}$），表示两个芯片总是同时被选中一起工作，只是存储字长翻倍了。

字扩展，则只扩展存储单元数量。表现为被选中的芯片分时工作。

上图表示两片1K×8位芯片组成2K×8位的存储系统。可以看出，存储字长并没有变化，始终为8（都是芯片的8根数据线与处理器的8根数据线相连），而处理器的低位地址线$A_9,A_8,\dots,A_0$与芯片的地址线相连，$A_{10}$则作为片选信号，当$A_{10}=1$为高电平时，$\overline{CS_1}$低电平导通，该芯片被选中工作，反之$\overline{CS_0}$被选中工作。

字、位同时扩展，指存储单元和存储字长同时扩展。图中的片选译码通常为74LS138。请尝试自行理解。

74LS138译码器

常见的片选译码器，知道什么功能即可。

其中$A_2,A_1,A_0$为变量输入端，$S_1,\bar{S}_2,\bar{S}_3$为使能端。

简言之，变量输入端$A_2A_1A_0$表示的十进制数为$i$，则输出端$\bar{Y}_0,\bar{Y}_1,\dots,\bar{Y}_7$中只有$\bar{Y}_i$为低电平0，其余均为高电平1。

考点概述

通常地，题目会给出一个处理器的规格（$x$条地址线、$y$条数据线），以及控制信号（读写控制信号、访存控制信号等），给出若干RAM、ROM，以及需要分配的地址范围要求（三大区：系统程序区、系统程序工作区和用户程序区），考察如何选取芯片并连接芯片与处理器，完成设计。

首先是确定系统程序区、用户程序区和系统程序工作区三者的地址范围。题目可以给出各种各样的条件（直接给出十进制范围，比如0 32767；最大16K；与xxx相邻的16K等等），只需要用二进制表示出三个区的地址范围以及范围大小，这一步就完成了。

接下来，得到三个区的地址范围后，开始选取芯片。RAM、ROM芯片的选取原则如下为系统程序区：ROM系统程序工作区、用户程序区：RAM。

另外，需要保证选取的ROM、RAM数据线不少于处理器的数据线（否则将造成浪费———处理器剩余未连接的引脚全部浪费）。当前者多于后者时，这种情况就是所谓的位扩展。

需要选取合适的芯片保证三个区的地址范围都被覆盖。比如系统程序区32K，则为该区选取的所有的ROM地址范围之和必须不小于32K。当所选取的ROM数量大于1时，这种情况就是所谓的字扩展。字扩展是这类题目最常考的考点，如果考试没有出现字扩展，那此题难度下降一半。

其次，连接数据线和低位地址线。

就数据线而言，因为前面说过原则是保证选取的ROM、RAM数据线不少于处理器的数据线，因此将两者直接对应着连起来就行，ROM、RAM可能会剩余数据线，这没关系；而处理器不能剩余数据线。

就低位地址线而言，如果涉及了字扩展，那么一定涉及片选信号的形成，也就是需要一套”逻辑”来判定何时选中扩展芯片1，何时选中另外的扩展芯片。我们将处理器的高位地址线参与片选信号的形成，处理器的低位地址线仍然与芯片的地址线直接相连即可。

最关键的是，关于片选信号的形成¹。

通常需要使用译码器（常见的是74LS138地址译码器，它的基本功能需要掌握，数字逻辑电路课程里面也有接触），将处理器高位地址线与74LS138译码器的输入端连起来，同时注意使能端的连线（否则74LS138译码器无法正常工作），将对应的$\bar{Y}_0,\bar{Y}_1,…,\bar{Y}_7$与参与字扩展的芯片使能端直接相连，或者经过与非门等逻辑门电路后再与芯片使能端相连。

最后是控制线的连接。

控制线，这里指的是处理器的控制引脚，比如常见的访存控制信号（$\overline{MREQ}$，表示低电平导通），读写信号（$\overline{WR}$，低电平导通）等。

再次强调，处理器的所有引脚（地址引脚、数据引脚、控制引脚）不允许悬空！

示例

这个示例题之前出现在知识点总结里面过。以此为例大致说明怎么做这种题目。

步骤1：写出题目给定的地址空间范围，用二进制表示：
系统程序区：$00\ 0000\ 0000\ 0000\ 0000B-00\ 0111\ 1111\ 1111\ 1111B$，$0 \sim 32767$，32K；
用户程序区：$00\ 1000\ 0000\ 0000\ 0000B-01\ 0111\ 1111\ 1111\ 1111B$，$32768\sim98303$，64K；
系统程序工作区：$11\ 1100\ 0000\ 0000\ 0000B-11\ 1111\ 1111\ 1111\ 1111B$，最大的16K。

步骤2：选择存储芯片类型与数量

根据第一步已经分析出来的结果，得

• 32K系统程序区：1片32K×8的ROM，
• 64K用户程序区：2片32K×8的RAM，
• 16K系统程序工作区：1片16K×8的RAM。

步骤3：连接好数据线和低位的地址线，这些只需要配对直接相连即可。比如此题中，

• 对于选中的2片32K×8的RAM和1片32K×8的ROM，它们均有15个地址引脚，于是直接将CPU的$A_0 \sim A_{14}$与之相连；
• 对于16K×8的RAM，它有14个地址引脚，于是直接将CPU的$A_0\sim A_{13}$与之相连；
• 8条数据线直接相连。

步骤4：片选信号的形成

(注意，$A_{17},A_{16},\dots,A_0$均表示CPU的地址线)

借助74LS138地址译码器，高三位作为译码器的输入端。

对于32K的ROM、32K的RAM，CPU的高三位$A_{17},A_{16},A_{15}$参与片选信号的形成：由于32K的ROM有效地址范围前三位均为0，因此，将输出端$\bar{Y_0}$与32K的ROM片选信号端（芯片片选信号端低电平有效）相连，表示当$A_{17}=A_{16}=A_{15}=0$时，32K的ROM有效，被选中。

两块RAM的进行字扩展也是这个道理。将$\bar{Y_1}$与其中一块32K的RAM的片选信号端相连，而将$\bar{Y_2}$与另一块32K的RAM的片选信号端相连。

对于16K的RAM，CPU高四位$A_{17},A_{16},A_{15},A_{14}$均参与片选信号的形成，只有当以下两个条件同时成立，16K的RAM才被选中：
高三位地址均为1，也就是通过地址译码器输出了$\bar{Y_7}$；$A_{14}$也是1。

为此，我们将地址译码器的$\bar{Y_7}$先经过一个非门，然后再和$A_{14}$一起经过与非门，结果再和16K的RAM的片选信号端相连。

步骤5：控制线的连接

很简单，清楚控制线的含义和导通规则（高电平有效还是低电平有效），直接相连即可。

练习

习题1

设CPU有16根地址线、8根数据线，并用$\overline{MREQ}$作为访存控制信号（低电平有效）、${\overline{WR}}$作为读写控制信号（高电平为读，低电平为写）。现有73LS138译码器、各种门电路以及如下存储芯片：

RAM：1K×4位、4K×8位、8K×8位 ROM：2K×8位、4K×8位、8K×8位

请画出CPU和存储器的连接图，并指出存储芯片的种类及数量。其中要求主存的地址空间满足如下条件：

最小8K地址为系统程序区，与其相邻的16K地址为用户程序区，最大的4K地址空间为系统程序工作区。

习题2

CPU以及其他芯片假设同习题1，主存地址空间分配为：6000H ~ 67FFH为系统程序区；6800H ~ 6BFFH为用户程序区；请画出CPU和存储的连接图，并指出存储芯片的种类及数量。

习题3

某CPU有20根地址线，8根数据线，并用$\overline{MEMR}$和$\overline{MEMW}$
作为访存控制信号。由两片27256EPROM和两片62256SRAM构成一个8位存储器系统如下图所示。已知27256和62256均为32K×8位的存储芯片，问：
(1)图中采用何种译码方式形成存储器的片选信号；
(2)图中各存储芯片的地址范围为多少；
(3)图中还有多大的地址空间可以用于存储器扩展。

习题4

设某计算机CPU有16根地址线（$A_{15},A_{14},\dots,A_0$，$A_0$为低位），16根数据线（$D_{15},D_{14},\dots,D_0$），并用$\overline{MREQ}$作为访存控制信号（低电平有效），$\overline{WR}$作为读/写控制信号（高电平为读命令，低电平为写命令）。现有下列存储芯片及各种门电路（门电路可自定）如图2所示，请画出CPU与存储芯片的连接图示，要求：
(1)存储芯片的地址空间分配为：最大32K为系统程序区；相邻16K为用户程序区；
(2)合理选用存储芯片，指出选用的存储芯片类型以及数量；
(3)详细画出存储芯片的片选逻辑。

参考答案

习题1

见教材例题。

习题2

见教材例题。

习题3

(3)事实上，$A_{18},A_{19}$都已经与译码器的使能端相连，固定为01时，译码器才可以正常工作。因此，剩余的地址空间还有$2^{18}-4\times 32K = 2^{18} - 2^{17} = 2^{17}$。

习题4

地址分配情况如下。
用户程序区： $\begin{aligned} \mathbf{010}0\ 0000\ 0000\ 0000\\ \cdots\\ \mathbf{010}1\ 1111\ 1111\ 1111\\ \mathbf{011}0\ 0000\ 0000\ 0000\\ \cdots\\ \mathbf{011}1\ 1111\ 1111\ 1111\\ \end{aligned}$ 系统程序区： $\begin{aligned} \mathbf{10}00\ 0000\ 0000\ 0000 \\ \cdots\\ \mathbf{10}11\ 1111\ 1111\ 1111\\ \mathbf{11}00\ 0000\ 0000\ 0000 \\ \cdots \\ \mathbf{11}11\ 1111\ 1111\ 1111 \end{aligned}$

可见，

• 对于32K的系统程序区，选取2片16K×16位的ROM；
• 对于16K的用户程序区，则选取2片8K×16位的RAM。

关于高位地址，已经标粗，一种比较简单的做法是，将高位地址线$A_{15},A_{14},A_{13}$作为译码器变量输入端，参与形成两片RAM的片选信号（用户程序区的地址空间刚好除开直接与处理器地址线相连的低位地址线，还剩下3条高位地址线）；而对于ROM的片选信号，可以直接使用$A_{15},A_{14}$两条地址线，为10时选通第一片ROM，为11时选通第二片ROM。

如果将最高三位的地址线参与ROM的片选信号也可以。$A_{15},A_{14},A_{13}$为100、101时，选通第一片ROM；为110、111时，选通第二片ROM。而前者译码器的$\bar{Y}_4,\bar{Y}_5$输出为01或者10，后者译码器的$\bar{Y}_6,\bar{Y}_7$输出为01或者10。根据这个特点，可以用异或结果，通过非门得到低电平，选通ROM即可。具体的逻辑图不妨自行尝试。

Cache与主存的编址题

基础知识

该考点涉及Cache出现原因、设计结构、工作原理等知识点。

高速缓存存储器Cache

为了解决”主存储器的速度始终赶不上处理器的速度“这一问题，在主存和处理器之间增加一级高速缓冲存储器Cache是一种非常有效的办法。 Cache一般采用SRAM实现，虽然容量小于主存容量，但是速度大大高于基于动态RAM的大容量主存。

Cache的工作原理

由于Cache是对主存中块的”暂存”以提高访存速度，因此，Cache中需要记录下来究竟记录到了主存的哪一块内容、主存中也需要记录它到Cache的映射情况。

在正式介绍主存和Cache的编址之前，你也许注意到上面的描述中经常出现”块”而不是字节、字等其他单位。是的，若干存储单元组成了一个数据块，而内存与Cache之间进行数据交换时，正是以块为单位。

所谓主存和Cache的编址，实际上就是对主存中的块映射到Cache中的记录，根据映射方式的不同，编址方式也不尽相同。常见的映射方式有三种：直接映射、全相联映射和组相联映射。

直接映射，按照公式$i=j\ mod\ 2^c$进行映射，其中j表示主存中的字块号，i表示Cache中的字块号。示意图如下。

为了更清楚地展示映射过程，此处标明了不同的组，这些组按照主存中的块号与$2^c$作整除运算所得到的整数商进行分类，而$2^c$正是Cache的字块总数。换言之，同组内部的每一个字块整除以$2^c$得到的商都相同。另外，正如图中连线所示，所有模$2^c$所得的余数相同的字块映射到Cache中的同一个字块。那如何准确地表示出Cache中的某一个字块到底来自主存中的哪一个？故需要保存主存块号（共$2^m$块）除以$2^c$所得到的商和余数，前者决定它来自哪一个组（$2^{m-c}=2^t$）、后者决定它映射到Cache中的位置（共$2^c$块）。

最后再解释字块内地址b。之前提过，Cache与主存进行数据交换均以字块为基本单位，一个数据块包含多个存储单元。而这b位的地址正是用于单个块内部寻址：找到具体是哪个存储单元。

全相联映射，相比于直接映射，取消了按模公式进行映射所具有的”固定性”，采取了更加随机的映射方式：对于主存中的任意一个字块，它可以映射到Cache中的任意位置。

主存地址格式解释起来比较简单，因为字块总数就是$2^m$，自然主存字块标记（主存字块地址）有m位。而对于Cache的编址，可以发现较之于直接映射，Cache标记位不再是t，而是m，因为Cache中的任意一个字块可以对应着主存$2^m$个字块中的任意一个。

组相联映射实际上是直接映射和全相联映射的结合。将Cache划分为若干组，每组内有若干字块。对于所有的组，按照直接映射；而每一个组内，按照全相联映射。另外请注意，这里的”组”与上文”直接映射”中的”组”含义不同，后者只是笔者方便描述而临时起意。

组相联下的主存地址格式由三部分组成。由于Cache中的组数为$\frac{2^c}{2^r}=2^{c-r}$，则组地址有$q=c-r$位；而每一个组内由于是全相联映射，可以对应主存中的$\frac{2^m}{2^{c-r}}=2^{m-c+r}$个块，因此Cache中的字块标记位有s=m-c+r位，主存地址中同样有此s=m-c+r位地址。对于Cache地址，由于总共的字块数量为$2^c$，字块地址用c位表示。另外的字块内地址上文提过，不再赘述。²

考点概述

这种类型的题目往往会给出主存容量和Cache的容量，以及每一个字块的大小。同时需要明确访存地址到底是字地址还是字节地址，这个直接影响到字块内地址的位数。一般地，需要根据给出的主存容量、Cache容量计算出主存中的字块总数和Cache中的字块总数，这样也可以得到两者的字块地址位数。然后根据题目指定的映射方式，给出各个段的位数。下面以具体的例子进行描述。

示例

假设主存容量为512K×16位，Cache容量为4096×16位，块长为4个16位的字，访存地址为字地址。请回答： (1)在直接映射方式下，设计主存的地址格式。

(2)在全相联映射方式下，设计主存的地址格式。

(3)在二路组相联映射方式下，设计主存的地址格式。

(4)若主存容量变为512K×32位，块长不变，在四路组相联映射方式下，设计主存的地址格式。

解析：注意访存地址是字，而块长为4个16位的字，则块内字地址位数即为b=$\log_24=2$；我们将Cache容量转换为以”块”为单位，即$\displaystyle\frac{4096\times 16}{4\times 16}=1024=2^{10}$块，因此Cache的字块地址位数c=10。接下来考虑主存中的字块总数：$\displaystyle\frac{512K \times 16}{4\times 16}=2^{17}$，因此主存字块地址位数m=17。

(1)直接映射下的主存地址格式有三部分：主存字块标记，Cache字块地址，字块内地址。后两者分别为c=10位、b=2位。主存字块标记位数即为m-c=7位。事实上，直接映射下的主存字块根据公式$i\% j$进行映射时，此处的j=$2^c=2^{10}$，故主存中映射到Cache中同一个字块的字块总数即为$\displaystyle\frac{2^m}{2^c}=\frac{2^{17}}{2^{10}}=2^7$，故主存字块标记位数t=7。 (主存字块标记7位，Cache字块地址10位，字块内地址2位)

(2) 全相联映射下的主存地址格式有两部分：主存字块标记，字块内地址。由于是随机性的映射，对于Cache中的某一字块，主存中的任意一块都可以映射到该处，故主存字块标记位数就是m=17。 (主存字块标记17位，字块内地址2位)

(3) 二路组相联映射下，Cache中每组有2块（r=1），此时主存地址格式有三部分：主存字块标记，组地址，字块内地址。一种很方便的思考思路是，算出Cache中的组数$\displaystyle\frac{2^c}{2^r}=\frac{2^{10}}{2^1}=2^9$，则组地址位数为q=9；然后直接用主存字块地址位数m减去q即为主存字块标记位数s=m-q=17-9=8。 (主存字块标记8位，组地址9位，字块内地址2位)

(4) 同样地，先算出主存字块总数以及主存字块地址位数：$\displaystyle\frac{512K\times 32}{4\times 16}=2^{18}$块，主存字块地址位数变为m’=18。Cache中的组数变为$\displaystyle\frac{2^{10}}{2^2}=2^8$，故主存地址中的组地址位数为q’=8，主存字块标记位数为m’-q’=18-8=10。由于字块长不变，则字块内地址仍为b=2。 (主存字块标记10位，组地址8位，字块内地址2位)

练习

习题1

假设主存容量为512KB，Cache容量为4KB，每个字块为16个字，每个字32位。访存地址为字节地址，请问：
(1) Cache地址有多少位？可容纳多少块？
(2)主存地址有多少位？可容纳多少块？
(3)在直接映射方式下，主存的第几块映射到Cache中的第5块（设起始字块为第1块）？
(4)画出直接映射方式下主存地址字段中各段的位数。

习题2

设某计算机主存容量为16MB，Cache的容量为8KB。每一个字块有8个字，每字32位。若访存单位为字节，请设计一个四路组相联映射的Cache组织：
(1)画出主存地址字段中各段的位数。
(2)设Cache初态为空，CPU依次从主存第0,1,2,...,99号单元读出100个字（主存一次读出一个字），并重复此次序读10次，试求命中率。
(3)若Cache的速度是主存速度的5倍，在第二问的基础上，请问有Cache和无Cache相比，速度提高了多少倍？

习题3

设某计算机的主存容量为256K×32位，Cache容量为64K×32位，块长为32个32位的字，且规定主存和Cache都按照字编址，请回答：
(1) 主存地址共计有多少位？可容纳多少个块？
(2)Cache地址共计有多少位？可容纳多少个块？
(3)若采用全相联映射方式，画出主存的地址格式，并指出各段的位数。

习题4

假设某机的主存容量为4MB，Cache容量为16KB，每个字块有16个字，每个字有32位。规定访存地址为字地址，请回答一下问题。
(1)若Cache采取直接映射，请画出主存地址字段中各段的位数。
(2)若Cache采取四路组相联映射，请画出主存地址中各段的位数。

参考答案

习题1

(1)由于访存地址为字节地址，而$4KB=2^{12}B$，因此Cache地址有c+b=12位。总共的字块数量为$\displaystyle \frac{4KB \times 8}{16\times 32} = 2^6$，c=6。
(2)由于$512KB = 2^{19}B$，因此主存地址位数为m+b=19位。总共的字块数量为$\displaystyle\frac{512KB\times 8}{16\times 32} = 2^{13}$，m=13。\
(3)主存一共有$2^{13}$块，而Cache一共$2^6$块，则$\displaystyle \frac{2^{13}}{2^6}=2^7$，故主存中映射到Cache中的第5块的块号为$5+i\times 2^6,\ i\in \{0,1,\dots,2^7-1\}$。\
(4) (主存字块标记7位，Cache字块地址6位，块内地址6位)。

习题2

(1)由$\displaystyle\frac{8\times 32}{8}=2^5$，得字块内地址位数b=5。计算得出主存字块总数为$2^{19}$，而Cache字块总数为$2^{8}$块，故组数为$2^{6}$，组地址位数q=6，主存地址格式为：(主存字块标记13位，组地址6位，字块内地址5位)\
(2)每一个字块有8个字，初始状态时，CPU读入第0号单元，没有命中，此时必须访问主存，并且将主存中该字所在的字块调入Cache第0组的任意一块内。接着，CPU读取第1、2、…、7号单元时，均命中（属于同一个字块）。

以此类推，CPU读取第8、16、...、96号单元时，均未命中。因此，CPU第一次连续读出100个字时，共有13次未命中。而接下来的9次重复读操作，全部命中。计算命中率为

$$\displaystyle \frac{100 \times 10 - 13}{100 \times 10} \approx 98.7\%$$

(3)假设Cache的存取周期为t，则主存的存取周期为5t，没有Cache时，访问时间为$5t \times 1000$，有Cache时，访问时间为$t \times (1000-13) + 5t \times 13$，因此后者相比于前者速度提高的倍数为

$$\displaystyle \frac{5t \times 1000}{t\times (1000-13)+5t\times 13} - 1 \approx 3.75$$

习题3

(1)
主存容量$\displaystyle\frac{256K \times 32}{32} = 2^{18}$字，故主存地址总位数m+b=18，而$\displaystyle\frac{256K \times 32}{32 \times 32} = 2^{13}$块，故可以容纳$2^{13}$个块。
(2)
Cache容量$\displaystyle\frac{64K \times 32}{32} = 2^{16}$字，故Cache地址总数为16，而$\displaystyle\frac{64K \times 32}{32 \times 32} = 2^{11}$块，故可以容纳$2^{11}$个块。
(3)
全相联下的主存地址有两部分。其中主存字块标记位数m=13，字块内地址位数b=5。

习题4

主存字块总数为$\displaystyle\frac{4MB}{16\times 4B}=2^{16}$块，则m=16；Cache字块总数为$\displaystyle\frac{16KB}{16\times 4B}= 2^8$块，则c=8。
(1)
每一个字块有16个字，则字块内地址位数b=4。而m=16，c=8，t=m-c=8，主存地址格式为：(主存字块标记8位，Cache字块地址8位，字块内地址4位)。
(2)
组数为$\displaystyle\frac{2^8}{2^2}=2^6$，组地址位数q=6，则主存字块标记位数s=m-q=10位。因此主存地址格式为：(主存字块标记10，组地址6位，字块内地址4位)

计算机中数据的加减运算

基础知识

该考点属于第6章《计算机的运算方法》。涉及四种机器码的表示、计算机中浮点数的四则运算。这里只关注加减运算，乘除运算另外单独介绍。

机器码

为了方便计算机运算，人们将形如10、-35这样的十进制真值用机器码表示。常见的四种机器码为原码，反码，补码，移码。这四种机器码与真值的相互转换以及它们之间的转换，请务必掌握，可以参考基本知识点梳理，这里简单给出四种机器码的求法。

给出真值$x=–0101011B$，则（整数位数n默认为7）

原码表示为$[x]_{true} = 1,0101011$（加上符号位，正数符号位为0，负数符号位为1）

反码表示为$[x]_{inv} = 1,1010100$（在原码基础上，符号位不变，数值部分按位取反）

补码表示为$[x]_{com} = 1,1010101$（在反码基础上，符号位不变，数值部分加一）

移码表示为$[x]_{shift} = 0,1010101$（在真值基础上，加上$2^n$；或者简记为补码基础上仅将符号位取反，其余不变）

定点数的加减运算

定点数的加减运算比较简单，将参与运算的定点数全部转化为补码，然后进行运算，因为对于任意真值$x,y$，下式成立

$$[x+y]_{\mbox{补}} = [x]_{\mbox{补}} + [y]_{\mbox{补}}$$ $$[x-y]_{\mbox{补}} = [x]_{\mbox{补}} + [-y]_{\mbox{补}}$$

对于减法，也连同负号将负数转化为补码，进行补码加法运算。

可能出现的一种情况是，运算之后结果溢出。为了判断是否发生溢出，有两种常用的方法。

一种是用一位符号位判断溢出。这种情况可以参考教材第239页表6.7。

另一种是用两位符号位判断溢出。这种情况下，需要将参与运算的真值全部转换为带2位符号位的变形补码，然后将其相加。2位符号位连同数值部分一起参与运算，且高位符号位产生的进位自动丢失。当2位符号位不同时，结果溢出，否则无溢出。这种情况的示例可以参考教材第240页例6.14、6.15、6.16。

浮点数的加减运算

浮点数相比于定点数形式上有差异。

通常地，浮点数被表示为$N=M\times R^E$，其中M为尾数，用一个定点小数表示，通常需要规格化，即尾数的真值绝对值在0到1之间；若为原码则数值部分第一位必须为1；若为补码则符号位和数值部分第一位不同；R为基值，一般取2；E为阶码，表示基值的幂。尾数和阶码都是有符号位的，分别用尾符和阶符指代。

浮点数加减运算的步骤如下。
(1)对阶：是为了将两个操作数的小数点位置对齐，即使得两个数的阶码一致。遵循小阶向大阶看齐原则，阶码小的浮点数尾数右移，从而阶码增大。³
(2)尾数求和：对接完成后，两个尾数可以按照定点数的加减运算规则直接求和；
(3)规格化；
(4)舍入；
(5)判断结果：判断结果是否溢出。

示例

两浮点数$x=0.1101\times 2^{01}, y=(-0.1010)\times 2^{11}$，求x+y，要求给出详细的运算过程。

第一步：对阶。

首先，将给出的两浮点数写成补码形式： $[x]_{com} = 00,01;00.1101$

$$[y]_{com} = 00,11;11.0110$$ 求出两者阶差： $$[\Delta_j]_{com} = [j_x]_{com} - [j_y]_{com} = 00,01 + 11,01 = 11,10$$

故$\Delta_j = -2$，表示x的阶码比y的阶码小。根据小阶向大阶看齐原则，将x进行变换：

$$[x]_{com} = 00,01;00.1101 = 00,11;00.0011$$

第二步：尾数求和。

已经得到： $[x]_{com} = 00,11;00.0011$ $[y]_{com} = 00,11;11.0110$
尾数相加，阶码不变，得到结果： $[x+y]_{com} = 00,11;11.1001$

第三步：规格化。

观察补码结果$11.1001$，它并不是一个规格化数，原因是补码规格化数的符号位和数值部分第一位相异，而此处均为1。规格化分为两种：左规和右规，前者针对尾数过小的情况，后者针对尾数过大的情况。

当结果出现00.0XXXXX...或者11.1XXXXX...时，需要左规。尾数左移（即小数点右移）变大，阶码减小。每移动一位，阶码减一。

当结果（溢出）出现01.XXXXX...或者10.XXXXX...时，需要右规。尾数右移（即小数点左移）变小，阶码增大。每移动一位，阶码加一。

因此，此处对于结果$[x+y]_{com} = 00,11;11.1001$，它需要进行左规。尾数左移一位即可，得到结果：

$$[x+y]_{com} = 00,10;11.0010$$ 把它用真值表示为$(-0.1110)\times 2^{10}$ 第四步：舍入。 舍入操作根据题目要求来，它主要是为了提高精度，因为右规过程可能带来精度损失问题。通常分为两种：一种是**"0舍1入"法**，类似十进制下的"四舍五入法"，即尾数右移一位时，若舍弃的末位为0，则直接舍去；若为1，则右移一位后，在尾数末位加上1。另一种是**恒置1法**，即尾数右移时，无论舍弃的末位是0还是1，都使右移后的尾数末位恒置1。 比如$11,100;10.110001$，显然它需要右规。采取"0舍1入"法，尾数右移一位后得到$11,101;11.011000$，原先的最末位1被舍弃，于是把当前的尾数加上1得到最终结果$$11,101;11.011001$$

练习与解答

习题1

选择题
1.在机器码()中，零的表示形式是唯一的。B
A.原码
B.补码
C.反码
D.原码和补码
2.设寄存器内容为10000000，若它等于-0，则为()。A
A.原码
B.补码
C.反码
D.移码
3.浮点数的表示范围和精度取决于()。C
A.阶码的位数和尾数的机器数形式
B.阶码的机器数形式和尾数的位数
C.阶码的位数和尾数的位数
D.阶码的机器数形式和尾数的机器数形式
4.若浮点数用补码表示，则判断运算结果为规格化数的要求是()。C
A.阶符与数符相同
B.阶符与数符相异
C.数符与尾数小数点后第一位数字相异
D.数符与尾数小数点后第一位数字相同

习题2

设x=$\displaystyle-\frac{11}{16}$，y=$\displaystyle-\frac{7}{16}$，试计算x+y，并判断是否发生溢出。
解答：x = -0.1011,y =-0.0111,用双符号位判断溢出法，则$[x]_{\mbox{补}} = 11.0101,[y]_{\mbox{补}} = 11.1001$，$[x+y]_{\mbox{补}} = [x]_{\mbox{补}}+[y]_{\mbox{补}} = 10.1110$，双符号位相异，因此结果溢出。

习题3

设浮点数的格式为：阶码5位，其中含1位阶符；尾数11位，其中含1位尾符。请分别写出下面两种情况下，$\displaystyle\frac{51}{128},7.375,-86.5$所对应的机器数：
(1)阶码和尾数均为补码； (2)阶码为移码，尾数为补码。

先将给出的三个数化为二进制形式与浮点数规格数形式：

$$\displaystyle\frac{51}{128} = 0.0110011B = 0.110011B \times 2^{-1B}$$ $$7.375 = 111.011B = 0.111011B \times 2^{11B}$$ $$-86.5 = -1010110.1B = -0.10101101B \times 2^{111B}$$

1. $$\displaystyle\frac{51}{128} = 1,1111;0.1100110000$$ $$7.375 = 0,0011;0.1110110000$$ $$-86.5 = 0,0111;1.0101001100$$
2. $$\displaystyle\frac{51}{128} = 0,1111;0.1100110000$$ $$7.375 = 1,0011;0.1110110000$$ $$-86.5 = 1,0111;1.0101001100$$

习题4

已知两个二进制形式的真值X=-100101和Y=-101101，将其分别存放在计算机的8位字长的寄存器中，且最高两位为符号位。请用补码”双符号位”加减运算规则计算$[X+Y]_{\mbox{补}}$，并判断结果是否发生溢出。
解答：求出双符号位下的补码：

$$[X]_{\mbox{补}}=11.011011$$ $$[Y]_{\mbox{补}}=11.010011$$

而$[X+Y]_{\mbox{补}} = [X]_{\mbox{补}}+[Y]_{\mbox{补}} = 10.101110$，结果双符号位相异，溢出。

习题5

已知x=-0.1011，y=0.0101，要求计算：(1)x+y，(2)x-y，并给出具体的计算过程，同时指出结果是否溢出。
解答：

$$[x]_{\mbox{补}} = 11.0101$$ $$[y]_{\mbox{补}} = 00.0101$$ $$[-y]_{\mbox{补}} = 11.1011$$ 因此， $$[x+y]_{\mbox{补}} = [x]_{\mbox{补}}+[y]_{\mbox{补}} = 11.1010$$ $$[x-y]_{\mbox{补}} = [x]_{\mbox{补}}+[-y]_{\mbox{补}} = 11.0000$$

则x+y=-0.0110,x-y=-1。

习题6

已知两浮点数x=$0.1101\times 2^{10}$，y=$0.1011\times 2^{01}$，求x+y。请写出详细的运算过程。

解答：见教材第271页例6.29。

计算机中数据的乘除运算

基础知识

紧承考点”计算机中数据的加减运算”，乘除运算相对而言更加复杂。这一部分会尽量从考点角度出发，介绍数据乘除法的运算过程。当然为了简单起见，只介绍定点数的乘除运算，浮点数的乘除运算可以类比完成。

乘法

首先来分析一下二进制下的竖式计算乘法过程。

假设两二进制乘数M=-0.1101，N=0.1011，我们列竖式计算它们的乘积，过程如图。

可见，先忽略符号位，单独计算数值的乘法，然后再给结果加上符号。然而，计算机却很难如此实现乘法运算。为了探求计算机作乘法运算的原理，我们先做如下推导。

$$\begin{aligned} M\times N &= M\times 0.1011 \\ &= M\times (0.1+0.00+0.001+0.0001) \\ &= 0.1M+0.00M+0.001M+0.0001M \\ &= 0.1M+0.00M+0.001(M+0.1M) \\ &= 0.1M+0.01[0M+0.1(M+0.1M)] \\ &= 0.1\{ M+0.1[0M+0.1(M+0.1M)] \} \\ &= 2^{-1}\{ M+2^{-1}[0M+2^{-1}(M+2^{-1}(M+0))] \} \end{aligned}$$

上述推导中，$2^{-1}$可以看作右移运算，因此，原始的竖式计算可以改进为如下算法：

输入：（二进制下）被乘数$M=0.m_1m_2\dots m_{k}$，乘数$N=0.n_1n_2\dots n_{k}$⁴

输出：M与N的乘积

1. 定义”部分积”，初始化为0；
2. 定义循环变量t=0；
3. 部分积 $\gets$ 部分积+被乘数M×乘数N的最后一位$n_{k}$；
4. 部分积和乘数均右移一位，且部分积右移的一位补充到乘数N小数点后第一位$n_1$；
5. t $\gets$ t+1；
6. 当t$\ge$k时，跳转至第7步，否则跳转至第3步；
7. 将当前部分积和乘数拼接起来，作为最终结果输出。

总的来说，改进后的乘法运算，是部分积不断加上被乘数和乘数末位、然后不断右移的过程。由于乘数一共有k位，这个过程（加、右移）循环执行k次，而乘数也会不断地右移，因此经过k次循环后，乘数的每一位（$n_i,i\in \{ k,k-1,\dots,1 \}$）都参与了与被乘数的运算。

接下来将介绍的内容包括原码一位乘法、原码二位乘法、补码一位乘法和Booth乘法，有兴趣者可以自行探究补码二位乘法。

原码一位乘法

对于原码一位乘法，只需单独将两个数的符号位作异或运算得到乘积符号位，两个数的数值部分（也即原乘数的绝对值）按上述过程作乘法运算即可。总结起来有如下特点：

1. 采取绝对值运算；
2. 用移位次数判定乘法是否结束；
3. 部分积和乘数均采取逻辑右移位；
4. 属于机器数乘法中最简单、最基础的一种

原码二位乘法

和一位乘法类似地，原码的二位乘法即每次用被乘数和乘数的最末两位作乘法，然后与部分积相加得到新的部分积。四种两位二进制数的情况见表1。

需要注意的是，加上三倍的被乘数操作并不易实现。因此，遇到11时，先减去一倍的被乘数，然后再加上四倍的被乘数。具体在运算时，需要考虑更高的两位——将当前减去的”一倍”交给更高的两位处理。我们仍以被乘数$M=0.m_1m_2\dots m_{k}$，乘数$N=0.n_1n_2\dots n_{k}$为例，并约定部分积用z表示，在表2中给出原码二位乘法的运算规则。

可见，原码二位乘法相比于一位乘法有几处细微的差异：首先，出现了减法，而之前在数据加减法中提过，将减法转化为补码加法，因此，参与原码二位乘法运算的操作数应该是绝对值的补码；而运算中的右移两位操作均遵循补码右移⁵规则。另外，部分积加上两倍的被乘数时，其绝对值可能大于2，因此采用三位符号位，才能保证运算结果无误（以最高位作为真正的符号位）。再者，对于乘数的符号位，如果乘数小数点后位数为奇数，则采用单符号位，且运算时最后部分积作加法运算后需要移位；反之则采用双符号位，最后一步部分积不移位。

因此，原码二位乘法特点总结如下：

1. 采取原操作数的绝对值的补码运算；
2. 用移位次数判断乘法是否结束；
3. 部分积和乘数均采取算术右移位（补码移位）。

补码一位乘法

补码一位乘法的运算规则基本和原码一位乘法相同。但是差异如下：

1. 如果乘数是正数，那么加法和移位均按照补码规则进行运算，且乘积的符号位自然形成，这一点和原码乘法极为不同；
2. 如果乘数是负数，那么将其符号位置0，然后按照正数如上处理，但是最后需要加上被除数的相反数的补码进行校正。

总结如下：

对于（二进制下补码）被乘数$M=m_0.m_1m_2\dots m_{k}$，乘数$N=n_0.n_1n_2\dots n_{k}$，

$[M\times N] = [M] \times [N] = [M] \times N, \mathbf{N>0}.$

$[M\times N] = [M] \times (0.n_1n_2\dots n_k) + [-M], \mathbf{N<0}$

我们以补码1.0101和0.1101作乘法运算进行演示。

Booth乘法

Booth乘法将补码一位乘法统一了起来。对于（二进制下补码）被乘数$M=m_0.m_1m_2\dots m_{k}$，乘数$N=n_0.n_1n_2\dots n_{k}$，对其补码乘法运算进行如下数学推导。注意，为了统一形式，我们给乘数N添加一位附加位$n_{k+1}=0$。

$$\begin{aligned} M\times N &= M\times(0.n_1n_2\dots n_k)-M\times n_0 \\ &=M\times (2^{-1}n_1+2^{-2}n_2+\dots+2^{-k}n_k) - M\times n_0 \\ &=M\times (-n_0+2^{-1}n_1+2^{-2}n_2+\dots+2^{-k}n_k) \\ &=M\times [-n_0+(n_1-2^{-1}n_1)+(2^{-1}n_2-2^{-2}n_2)+\dots+(2^{-(k-1)}n_k-2^{-k}n_k)] \\ &= M\times [(n_1-n_0) + 2^{-1}(n_2-n_1) + \dots + 2^{-(k-1)}(n_k-n_{k-1}) + 2^{-k}(0-n_k)] \\ &= M\times [(n_1-n_0) + 2^{-1}(n_2-n_1) + \dots + 2^{-k}(n_{k+1}-n_k)] \\ &=M\times \sum_{i=0}^{k}2^{-i}(n_{i+1}-n_i) \end{aligned}$$

可见，同样可以通过每次读取乘数的两位$n_{i+1},n_i$来求解部分积，并不断地迭代最终求出结果。迭代过程如下。

$$\begin{aligned} z_0 &= 0 \\ z_1 &= 2^{-1}[(n_{k+1} - n_k)M + z_0] \\ \vdots \\ z_k &= 2^{-1}[(n_2 - n_1)M + z_{k-1}] \\ result &= (n_1 - n_0)M + z_k \end{aligned}$$

可见，Booth乘法的最后一步部分积不需要进行移位，作加法运算之后直接得到最终结果。而考虑每一步读取的两位二进制数，各种情况以及操作见表。

最后以补码乘法x=+0.0011、y=-0.1011为例进行演示。

最后，关于补码二位乘法，此处不再赘述，各位不妨一试。

除法

再来看看除法。同样地，先从除法的竖式计算开始。

和乘法类似地，做竖式除法时，符号位单独考虑，具体的数值部分运算时，上商之后，余数不动，低位补0，且当上商为1时，需要减去右移一位的除数；而做机器除法时，余数左移一位，低位补0，然后减去除数。由于余数和除数参与减法操作，因此这两种处理实际上是等价的。

原码除法

给定原码形式下的被除数$[M]_{true}=m_0.m_1m_2\dots m_{k}$，除数$[N]_{true}=n_0.n_1n_2\dots n_{k}$，则原码做除法也是符号位单独计算、数值部分单独计算：

$$\displaystyle\left[\frac{M}{N}\right]_{true} = (m_0 \oplus n_0).\frac{|M|}{|N|}$$

而原码除法中，根据对余数处理方式的不同，又可以分为恢复余数法和不恢复余数法（加减交替法）。

关于恢复余数法，由于计算机无法如同人类直接看出每一位上商为0还是1，因此计算机总是预先上商为1，然后自然就是当前余数和除数（的一倍）做减法⁶。如果减法的结果为负，那么当前应该上商为0，并且给当前结果加上$|N|$以便恢复余数为正数，否则上商为1。上商结束后，余数需要作逻辑左移运算。

给出一个示例。$x=-0.1011$，$y=0.1101$，用恢复余数法给出运算$\displaystyle\left[\frac{x}{y}\right]_{true}$的详细过程。

关于不恢复余数法（也称”加减交替法”），实际上是对恢复余数法的一种改良。因为恢复余数法中每当余数为负时，都需要进行恢复，严重延长了机器运算时间，且在除法运算中显得操作不规则，容易造成线路复杂。为了方便推导不恢复余数法的数学原理，约定用$R$表示当前余数。恢复余数法中的运算规则总结见表。

因此我们得到不恢复余数法的运算规则，见表。

也给出一个示例。x=-0.1011，y=-0.1101，用不恢复余数法给出运算$\displaystyle \left[\frac{x}{y}\right]_{true}$的详细过程。

补码除法

补码除法相对而言不如原码除法那般直观，同样也分为恢复余数法和加减交替法。这里只介绍加减交替法。这一运算方法的关键有三处：确定商值、形成商符、获得新的余数。

第一，确定商值。这需要先比较被除数和除数的大小。但是补码形式的比较并不能直接使用$[M]_{com}-[N]_{com}$来判断，而是需要比较它们绝对值的大小。我们将比较算法总结如下。

确定了被除数和除数的大小之后，接下来确定商值。商符自动形成；由于商值同样也是补码，约定商的末位恒置1，故其余各位根据商的正负采取不同的上商规则：对于正商，按原码上商；对于负商，按反码上商。而关于获得新的余数，方式和原码的加减交替法极为相似。总结如下。

具体的算法过程总结如下。

给出一个示例。x=-0.1011，y=0.1101，用补码除法给出运算$\displaystyle\left[\frac{x}{y}\right]_{com}$的详细过程。

因此，$\displaystyle \left[\frac{x}{y}\right]_{com} = 1.0011$，$\displaystyle\frac{x}{y} = -0.1101$。

¹. 片选信号的形成有三方法。全译码：余下的高位地址线全部参与译码形成片选信号；部分译码：余下的高位地址线部分参与译码；线选法：余下的高位地址线，每一根选通一块芯片，直接形成该芯片的选通信号，思路很简单（不再需要译码器了），但是前提是处理器的地址线数量较多，不然根本不够用。 ↩

². 关于其中s=t+r的推导：事实上，s=m-q，而在直接映射部分得到m=t+c，另外组地址位数q=c-r。计算s时可以直接使用主存字块地址位数m减去组地址位数q。 ↩

³. 这个过程实际上和十进制下的数据转化为科学记数法形式的过程很类似。比如十进制$202.3 \times 10^6 = 2.023 \times 10^8$​，尾数右移两位（小数点左移两位），阶增大2。 ↩

⁴. 在四则运算乘法中，乘号前面的数字称为被乘数，乘号后面的数字称为乘数。注意不要混淆。 ↩

⁵. 补码右移规则回顾：对于正数，无论左移还是右移均补0；对于负数，左移补0，右移补1。例如补码1.0010>>2=1.11 ↩

⁶. 同样地，此处的减法运算也转化为补码加法运算，即加上除数真值相反数的补码$[-N]_{com}$​ ↩

赏