欢迎来到计算机组成原理，也就是大家常说的“计组”。计组在$408$里属于那种“概念细、计算多、图还多”的科目：平时看书觉得都懂，一到做题就开始问自己“这个数到底怎么存”“这条指令到底取了几次内存”“这个流水线到底卡在哪”。所以这篇笔记还是走“一篇记所有”的路子，把计组的知识点、常考计算和大题思路尽量塞进同一篇里，方便后面反复翻。

计组总览

一条主线

计组研究的是“计算机硬件怎么把程序跑起来”。从最底层的门电路，到寄存器、存储层次、指令系统、$CPU$、总线，再到$I/O$接口，整本书其实都在回答三个问题：

数据怎么表示、怎么运算。
指令怎么取、怎么译码、怎么执行。
存储器、$CPU$和外设之间怎么把数据搬运起来。

复习时不要把这些章节当成互不相干的碎片。比如$Cache$要和存储层次、地址映射、替换算法一起看；指令周期要和$CPU$数据通路、控制器一起看；中断和$DMA$又要和$I/O$系统、总线一起看。

教材章节地图

章	标题	核心问题
第一章	计算机系统概述	计算机硬件由哪些部件组成，性能指标怎么算
第二章	数据的表示和运算	定点数、浮点数怎么表示，加减乘除和$ALU$怎么工作
第三章	存储系统	存储层次、$SRAM/DRAM$、$Cache$、虚拟存储怎么组织
第四章	指令系统	指令格式、寻址方式、$CISC/RISC$有什么区别
第五章	中央处理器	$CPU$的数据通路、控制器、指令周期和流水线
第六章	总线	总线分类、性能指标、仲裁和通信方式
第七章	输入/输出系统	$I/O$接口、中断、$DMA$、通道怎么工作

这张表按$408$大纲和常用教材的七章结构整理。不同教材的章节编号可能略有调整，复习时以自己手里那一版为准；但“数据表示—存储—指令—$CPU$—总线—$I/O$”这条硬件主线是不变的。

第一章计算机系统概述

1.1 计算机发展历程

这一节已经从大纲中删除，也不会有重新加进来的风险。

计算机系统由硬件和软件两部分组成。硬件是计算机的实体，软件是由程序、数据和相关文档组成的。硬件的发展经历了四代，划分依据是逻辑元件的变化：

代次	逻辑元件	主要特征
第一代	电子管	体积大、功耗高，使用机器语言编程，代表机器是$ENIAC$
第二代	晶体管	体积和功耗下降，出现高级语言（如$FORTRAN$），出现操作系统雏形
第三代	中小规模集成电路	元件集成到芯片上，高级语言迅速发展，出现分时操作系统
第四代	大规模、超大规模集成电路	出现微处理器和微型计算机，个人计算机开始普及

两个容易混的机器：

$ENIAC$：世界上第一台电子数字计算机，$1946$年诞生，靠手动接线控制计算。
$EDVAC$：第一台采用冯·诺依曼结构的计算机，核心是“存储程序”。

微型计算机的发展以微处理器技术为标志。机器字长也随着微处理器的发展不断提高，从早期的$8$位、$16$位，发展到$32$位、$64$位。

摩尔定律的内容是：集成电路上可容纳的晶体管数目大约每$18$个月翻一番，整体性能也随之提升。

计算机的发展趋势呈现两极分化：一端是微型计算机向微型化、网络化、高性能、多用途方向发展；另一端是巨型机向巨型化、超高速、并行处理、智能化方向发展。

1.2 计算机系统层次结构

1.2.1 计算机系统的基本组成

计算机系统由硬件系统和软件系统组成，两者缺一不可。

硬件系统：计算机的实体，包括主机、外设等。
软件系统：由具有各类特殊功能的程序组成，分为系统软件和应用软件。

系统软件负责管理整个计算机系统，为上层应用提供基础服务。常见的系统软件有：

操作系统（$OS$）
数据库管理系统（$DBMS$）
语言处理程序，如编译程序、汇编程序、解释程序
标准程序库
网络软件
服务性程序

应用软件是用户为了解决某个应用领域的问题而编制的程序，比如科学计算程序、数据处理程序、过程控制程序、事务管理程序、游戏、办公软件等。

易错点：数据库管理系统（$DBMS$）是系统软件；而一个具体的数据库应用系统属于应用软件。不要看到“数据库”三个字就一律归到应用软件。

对于某一个特定功能，既可以用硬件实现，也可以用软件实现，在逻辑上二者是等效的，这叫软/硬件逻辑功能的等效性。它是计算机系统设计的重要依据。

硬件实现：速度快、成本高、灵活性差。
软件实现：速度慢、成本低、灵活性好。

比如乘法运算，既可以用专门的乘法器实现，也可以用加法、移位组成的程序实现；加密算法既可以用硬件加速器实现，也可以用软件实现。所谓“逻辑等效”是指功能可以互相替代，不是说性能和成本完全一样。

1.2.2 计算机硬件的基本组成

早期冯·诺依曼机

冯·诺依曼在研究$EDVAC$时提出了“存储程序”的概念。存储程序是指：把指令以二进制代码的形式事先输入计算机的主存储器，然后按其在存储器中的首地址执行程序的第一条指令，之后按程序规定的顺序执行其他指令，直到程序执行结束。

冯·诺依曼机有六个经典特点：

计算机硬件系统由运算器、存储器、控制器、输入设备、输出设备五大部件组成。
指令和数据以同等地位存储在存储器中，形式上没有区别，但可以按地址寻访。
指令和数据都用二进制代码表示。
指令由操作码和地址码组成：操作码指出操作类型，地址码指出操作数地址。
采用“存储程序”的工作方式。
早期冯·诺依曼机以运算器为中心，输入/输出设备与存储器之间的数据传送都要通过运算器完成。

这里的“以运算器为中心”是早期结构的特点。它的基本工作方式是控制流驱动：先有指令，再由指令去访问数据。与之相对的是数据流驱动：数据准备好后再触发指令执行。

高频陷阱：冯·诺依曼机最根本的特征是“存储程序”，不是“五大部件”，也不是“以运算器为中心”。后者只是早期结构的特点。

现代计算机的结构

现代计算机已经转为以存储器为中心。运算器和控制器被集成到同一个芯片上，合称为中央处理器（$CPU$）。$CPU$和主存储器共同构成主机，除主机以外的硬件装置（外存、输入设备、输出设备等）统称为外部设备，简称外设。

现代计算机的硬件组成可以这样看：

主机
- $CPU$
  - 运算器
  - 控制器
- 主存储器
外设
- 辅助存储器
- 输入设备
- 输出设备

为什么要从“以运算器为中心”变成“以存储器为中心”？因为早期计算机需要处理的信息量小，存储器容量也小，让所有数据都经过运算器还能接受；后来$I/O$设备越来越多，$I/O$速度和$CPU$速度差距越来越大，如果还让$I/O$数据绕经运算器，就会严重拖慢系统。改成以存储器为中心后，$I/O$设备可以和主存直接交换数据，尽量减少对$CPU$的占用，提高整体效率。

1.2.3 各个硬件的工作原理

主存储器

主存储器简称主存，又叫内存，用来存放计算机运行期间所需的程序和数据。$CPU$可以直接随机访问主存，主存也可以和高速缓冲存储器、辅助存储器交换数据。

主存的基本组成包括存储体、地址寄存器（$MAR$）和数据寄存器（$MDR$）。现代计算机通常把$MAR$和$MDR$集成在$CPU$中，但它们在逻辑上仍属于主存。

存储体：由许多存储单元组成，用来存放二进制信息。
存储单元：每个存储单元存放一串二进制代码，每个存储单元有一个地址。
存储字：一个存储单元中二进制代码的组合。
存储字长：一个存储单元中二进制代码的位数。
存储元：存放一位二进制代码的电子元件，每个存储元存$1$位。

$MAR$用来存放要访问的存储单元地址。$MAR$的位数决定了存储单元的个数：如果$MAR$有$n$位，就可以表示$2^n$个不同的地址，也就是最多有$2^n$个存储单元。

$MDR$用来暂存要从存储器读出或写入的数据。$MDR$的位数等于存储字长，也就是每个存储单元能存放的二进制位数。

主存容量的计算公式是：

$$ \text{主存容量}=\text{存储单元个数}\times\text{存储字长}\ \mathrm{bit} $$

如果要把单位换成字节，再除以$8$：

$$ \text{主存容量}=\frac{\text{存储单元个数}\times\text{存储字长}}{8}\ \mathrm{B} $$

例如，$MAR$为$32$位，$MDR$为$8$位，则存储单元个数为$2^{32}$，每个存储单元$8$位，所以

$$ \text{主存容量}=2^{32}\times8\ \mathrm{bit}=2^{32}\ \mathrm{B}=4\ \mathrm{GB}. $$

再比如，$MAR$为$16$位，$MDR$为$32$位，则主存容量为

$$ 2^{16}\times32\ \mathrm{bit}=64\mathrm{K}\times32\ \mathrm{bit}=256\ \mathrm{KB}. $$

注意：$MAR$的位数反映“有多少个存储单元”，$MDR$的位数反映“每个存储单元有多大”。题目如果只说“按字节编址”，每个地址对应的就是一个字节；如果“按字编址”，每个地址对应的就是一个字。编址单位不同，算出来的容量表示也不同。

运算器

运算器用来完成算术运算和逻辑运算，核心部件是算术逻辑单元（$ALU$）。运算器中通常包含若干寄存器，常见的有：

累加器（$ACC$）：存放操作数或运算结果。
乘商寄存器（$MQ$）：在乘、除法运算中存放乘数、商或相关结果。
通用操作数寄存器（$X$）：存放另一个操作数。
算术逻辑单元（$ALU$）：完成加、减、乘、除、与、或、非等运算。

早期冯·诺依曼机以运算器为中心，所以运算器不仅负责运算，还要中转$I/O$与存储器之间的数据。现代计算机以存储器为中心，运算器的主要职责就回归到“算”本身。

控制器

控制器是计算机的指挥中心，负责协调各部件自动工作。它的基本组成包括：

程序计数器（$PC$）：存放下一条要执行的指令地址，具有自动加$1$的功能。这里的“$1$”指的是一条指令的长度，不是固定的一字节。
指令寄存器（$IR$）：存放当前正在执行的指令。指令的操作码送到控制单元（$CU$）分析，地址码送到$MAR$去取操作数。
控制单元（$CU$）：分析指令，产生各种微操作命令，控制其他部件完成指令。

几个寄存器的分工如下：

寄存器	所在部件	主要作用	位数
$PC$	控制器	存放下一条指令地址	通常与$MAR$位数相同
$IR$	控制器	存放当前指令	与指令字长有关
$MAR$	主存/现代$CPU$	存放访存地址	决定存储单元个数
$MDR$	主存/现代$CPU$	暂存读写数据	等于存储字长
$ACC$	运算器	存放操作数或结果	通常等于机器字长
$MQ$	运算器	存放乘数、商等	通常等于机器字长
$X$	运算器	存放操作数	通常等于机器字长

高频辨析：$PC$存的是“下一条指令的地址”，$IR$存的是“当前指令本身”，$MAR$存的是“要访问的存储单元地址”，$MDR$存的是“从存储单元读出或写入的数据”。四个寄存器不要混。

计算机的工作过程

计算机执行程序的过程，就是周而复始地取指令、分析指令、执行指令的过程。

程序执行前，先把程序和数据装入主存，并把第一条指令的地址送到$PC$。
取指令：把$PC$的内容送到$MAR$，通过地址总线访问主存；主存把读出的指令送到$MDR$，再送到$IR$；同时$PC$自动加上当前指令的长度，指向下一条指令。
分析指令：$CU$对$IR$中的操作码进行译码，判断这条指令要做什么。
执行指令：根据地址码计算操作数地址，取操作数，送入运算器运算，再把结果写回寄存器或主存。
如果当前指令是顺序指令，下一条指令就是$PC$指向的指令；如果是转移指令，就把转移目标地址送到$PC$，改变执行顺序。

$CPU$区分指令和数据的依据不是存储单元的地址，也不是二进制内容本身，而是指令周期的不同阶段：取指周期取出的一定是指令，执行周期取出的可能是数据。因为指令和数据在存储器中都是以二进制形式存放的，形式上没有区别。

1.2.4 计算机软件与语言层次

计算机软件分为系统软件和应用软件。系统软件负责管理硬件资源，并为上层应用提供基础服务；应用软件面向具体应用问题。这个分类在上一节已经说过，这里重点看语言和翻译程序。

按照语言级别，可以把程序分成三类：

语言	形式	硬件能否直接执行	需要什么程序翻译
机器语言	二进制代码	能	不需要
汇编语言	助记符	不能	汇编程序
高级语言	接近人类语言	不能	编译程序或解释程序

机器语言是计算机唯一可以直接识别和执行的语言。汇编语言用英文单词或缩写代替二进制指令代码，本质上和机器语言一一对应，但必须经过汇编程序翻译成机器语言后才能执行。高级语言方便人编写，但需要编译程序或解释程序翻译。

几个翻译程序的区别：

预处理程序：处理以#开头的预处理指令，比如#include、#define、#ifdef，完成头文件展开、宏替换、条件编译和删除注释，输出预处理后的高级语言源程序，不生成目标代码。
汇编程序：把汇编语言源程序翻译成机器语言目标程序。
编译程序：把高级语言源程序整体翻译成汇编语言或机器语言目标程序，翻译一次，之后直接执行目标程序。
解释程序：把源程序的一条语句翻译成机器语言并立即执行，不生成完整的目标程序，下一次执行还要重新解释。
链接程序：把多个目标文件和库函数组合成一个可执行文件，它本身不是语言翻译程序。

从$C$语言源程序到可执行文件，大致经过：

阶段	输入	处理程序	输出
预处理	高级语言源程序	预处理程序	预处理后的源程序
编译	预处理后的源程序	编译程序	汇编语言程序或目标代码
汇编	汇编语言源程序	汇编程序	目标文件
链接	多个目标文件和库	链接程序	可执行文件

预处理严格来说发生在编译之前，不属于编译程序的核心阶段。它只做文本级的头文件展开、宏替换、条件编译和注释删除，输出仍然是高级语言代码；真正把高级语言翻译成汇编语言或机器代码的是编译程序。

高频辨析：编译程序是“整体翻译，生成目标程序”；解释程序是“逐条翻译，边翻译边执行，不生成目标程序”。汇编程序只负责汇编语言到机器语言的翻译，不要和编译程序混为一谈。

1.2.5 计算机系统的多级层次结构

计算机系统可以按功能划分为五层，从下到上依次是：

层次	名称	性质	主要功能
$M_4$	高级语言机器	虚拟机器	执行高级语言，由编译程序或解释程序支持
$M_3$	汇编语言机器	虚拟机器	执行汇编语言，由汇编程序支持
$M_2$	操作系统机器	虚拟机器	向上提供广义指令，也就是系统调用
$M_1$	传统机器	实际机器	执行机器语言指令，由微程序解释
$M_0$	微程序机器	实际机器	由硬件直接执行微指令

下层是上层的基础，上层是下层的扩展。$M_2$到$M_4$是由软件实现的虚拟机器；$M_0$和$M_1$是实际机器。没有配备任何软件的纯硬件系统称为裸机。

计算机组成原理主要研究$M_0$和$M_1$，也就是微程序机器和传统机器；操作系统、汇编语言、高级语言则更多属于软件层次。但各层不是孤立的，软件最终都要落到硬件上执行。

软件和硬件之间的界面是指令集体系结构（$ISA$）。$ISA$定义了一台计算机可以执行的所有指令的集合，包括指令格式、数据类型、寄存器、寻址方式、$I/O$机制等。$ISA$是软件能感知到的部分，也叫软件可见部分。

计算机体系结构和计算机组成是两个容易混的概念：

计算机体系结构：机器语言程序员所见到的计算机系统属性，比如指令系统、数据类型、寻址技术、$I/O$机理。它回答“软件和硬件之间的接口怎么设计”。
计算机组成：实现体系结构所体现的属性，对程序员透明，比如$ALU$的具体电路、控制器的时序、乘法器用硬件还是移位加法实现。它回答“这个接口用硬件怎么实现”。

对比项	计算机体系结构	计算机组成
关注点	程序员可见的属性	具体硬件实现
典型内容	指令格式、寻址方式、数据表示	$ALU$电路、控制器时序、乘法器实现
是否对程序员透明	不透明，程序员需要知道	通常透明，程序员不需要知道

系列机是同一体系结构的不同实现，它们具有相同的$ISA$，但可以采用不同的组成方式。系列机通常保证软件向后兼容，也就是新机器能运行旧机器上的程序。

“透明”是一个方向性很强的词：说“某细节对某层程序员透明”，意思是该层程序员看不见、也不用关心这个细节。比如$Cache$、流水线、微程序对高级语言程序员是透明的；但不能笼统地说“下层对上层透明”。

1.2.6 计算机系统的工作原理

“存储程序”工作方式的核心是：程序和数据一起存放在主存中，计算机按地址访问主存，自动、连续地取出指令并执行。程序执行前，第一条指令的地址被送到$PC$；之后每执行完一条指令，$PC$指向下一条指令。

一条指令的执行可以概括为：

取指：$PC\rightarrow MAR$，读主存，指令$\rightarrow MDR\rightarrow IR$，$PC$加上当前指令长度。
译码：$CU$分析$IR$中的操作码。
执行：根据地址码取操作数，送入$ALU$运算，结果写回寄存器或主存。
更新$PC$：顺序执行时$PC$已经指向下一条指令；转移执行时把目标地址送入$PC$。

高级语言程序最终要变成机器语言程序才能被硬件执行。典型过程是：

高级语言源程序先经过预处理程序处理，展开头文件、替换宏、处理条件编译并删除注释，得到预处理后的源程序。
预处理后的源程序经过编译程序翻译成汇编语言程序或目标代码。
汇编语言程序经过汇编程序翻译成机器语言目标文件。
多个目标文件和库经过链接程序组合成可执行文件。
操作系统把可执行文件装入主存，$CPU$从入口地址开始取指执行。

所以，硬件真正执行的是机器指令序列；高级语言、汇编语言、操作系统提供的系统调用，最终都要转换成机器指令。

1.3 计算机性能指标

性能指标是第一章最重要的计算考点。不要只背公式，要先分清每个指标衡量的到底是什么：容量、字长、时间、频率、吞吐量还是响应时间。

1.3.1 主存容量

主存容量表示主存能存储的最大信息量，常用两种写法：

$$ \text{主存容量}=\text{存储单元个数}\times\text{存储字长}\ \mathrm{bit} $$

$$ \text{主存容量}=\frac{\text{存储单元个数}\times\text{存储字长}}{8}\ \mathrm{B} $$

$MAR$的位数决定存储单元个数：$MAR$有$n$位，就有$2^n$个存储单元。$MDR$的位数等于存储字长：$MDR$有$m$位，每个存储单元就存放$m$位。

例如：

$MAR$为$32$位，$MDR$为$8$位：容量为$2^{32}\times8\ \mathrm{bit}=4\ \mathrm{GB}$。
$MAR$为$16$位，$MDR$为$32$位：容量为$2^{16}\times32\ \mathrm{bit}=64\mathrm{K}\times32\ \mathrm{bit}=256\ \mathrm{KB}$。
$MAR$为$20$位，$MDR$为$16$位：容量为$2^{20}\times16\ \mathrm{bit}=2\ \mathrm{MB}$。

如果题目说“按字节编址”，每个地址对应$1$字节；如果说“按字编址”，每个地址对应一个字。编址单位不同，$MAR$位数和容量之间的对应关系也不同。

1.3.2 字长

字长是第一章最容易混的一组概念，至少分清三个：

名称	定义	典型关系
机器字长	$CPU$一次整数运算能处理的二进制位数	通常等于通用寄存器宽度、整数运算部件宽度
指令字长	一条指令中包含的二进制代码位数	通常取存储字长的整数倍，可以变长
存储字长	一个存储单元中存储的二进制代码位数	等于$MDR$位数，通常是字节的整数倍

机器字长反映计算机一次能处理多少位数据，影响运算精度和数的表示范围。我们常说“$32$位机器”“$64$位机器”，这里的$32$、$64$通常指机器字长。

指令字长和存储字长不一定相等。如果指令字长等于存储字长的$2$倍，那么取一条指令需要$2$次访存，取指周期也会相应变长；如果二者相等，取一条指令只需要$1$次访存。

存储字长等于$MDR$的位数，也等于每个存储单元的大小。它和机器字长可以不同：比如一台机器的机器字长是$64$位，但主存可能按$32$位一个字来组织。

另外还有一个“数据字长”或“数据通路带宽”的概念，通常指数据总线一次能并行传送的位数。它不一定等于机器字长，也不一定等于存储字长。考试如果问“数据总线宽度”，不要直接拿机器字长去套。

1.3.3 $CPU$性能指标

主频与时钟周期

主频也叫时钟频率，是$CPU$内数字脉冲信号振荡的频率，单位是赫兹（$\mathrm{Hz}$）。主频越高，时钟周期越短。

$$ T_c=\frac{1}{f} $$

其中$T_c$是时钟周期，$f$是主频。时钟周期是$CPU$中最小的时间单位，执行指令的每个动作至少需要一个时钟周期。

常用频率单位按$10$的幂次换算：

$$ 1\ \mathrm{kHz}=10^3\ \mathrm{Hz},\qquad 1\ \mathrm{MHz}=10^6\ \mathrm{Hz},\qquad 1\ \mathrm{GHz}=10^9\ \mathrm{Hz}. $$

$CPI$

$CPI$是执行一条指令所需的时钟周期数。不同指令的$CPI$不同，甚至同一条指令在不同情况下$CPI$也可能不同，所以通常说“平均$CPI$”。

如果一个程序由$k$类指令组成，第$i$类指令的$CPI$为$CPI_i$，在程序中所占比例为$p_i$，则

$$ CPI=\sum_{i=1}^{k}CPI_i\times p_i, \qquad \sum_{i=1}^{k}p_i=1. $$

也可以直接用总时钟周期数除以指令条数：

$$ CPI=\frac{\text{总时钟周期数}}{\text{指令条数}}. $$

$CPU$执行时间

$CPU$执行时间就是运行一个程序所花费的时间：

$$ T_{CPU}=\text{指令条数}\times CPI\times T_c =\frac{\text{指令条数}\times CPI}{f} =\frac{\text{总时钟周期数}}{f}. $$

所以$CPU$性能取决于三个要素：

指令条数$IC$：程序编译后有多少条指令。
平均$CPI$：每条指令平均需要多少个时钟周期。
主频$f$：每秒有多少个时钟周期。

这三个因素相互制约。比如复杂指令集可能减少指令条数，但会增加$CPI$；提高主频可能带来更长的访存延迟，从而影响$CPI$；编译优化可能减少指令条数，但也可能让剩下的指令更复杂，导致$CPI$上升。因此不能只看某一个指标。

$IPS$与$MIPS$

$IPS$表示每秒执行的指令条数：

$$ IPS=\frac{f}{CPI}. $$

$MIPS$表示每秒执行多少百万条指令：

$$ MIPS=\frac{\text{指令条数}}{T_{CPU}\times10^6} =\frac{f}{CPI\times10^6}. $$

如果主频$f$用$\mathrm{MHz}$作单位，则可以直接写成

$$ MIPS=\frac{f(\mathrm{MHz})}{CPI}. $$

注意$MIPS$里的“$M$”是$10^6$，不是$2^{20}$。同样，$KIPS$、$GIPS$等也是按$10$的幂次换算。

$MIPS$只能衡量“每秒执行多少条指令”，不能直接比较不同指令集的机器。因为不同机器的指令功能不同，一条指令可能相当于另一台机器的多条指令；即使$MIPS$相同，实际程序运行时间也可能差很多。

$FLOPS$

$FLOPS$表示每秒执行的浮点运算次数：

$$ FLOPS=\frac{\text{浮点操作次数}}{T_{CPU}}. $$

常用单位按$10$的幂次换算：

单位	含义	数量级
$MFLOPS$	每秒百万次浮点运算	$10^6$
$GFLOPS$	每秒十亿次浮点运算	$10^9$
$TFLOPS$	每秒万亿次浮点运算	$10^{12}$
$PFLOPS$	每秒千万亿次浮点运算	$10^{15}$
$EFLOPS$	每秒百京次浮点运算	$10^{18}$
$ZFLOPS$	每秒十万京次浮点运算	$10^{21}$

$MIPS$统计的是指令条数，$FLOPS$统计的是浮点运算次数，两者不要混。浮点运算速度通常用$FLOPS$系列指标描述，指令执行速度用$MIPS$系列指标描述。

主频高不一定快

主频只是$CPU$性能的一个因素。比如：

机器$A$：主频$2\ \mathrm{GHz}$，平均$CPI=10$，每秒执行$2\times10^8$条指令。
机器$B$：主频$1\ \mathrm{GHz}$，平均$CPI=1$，每秒执行$10^9$条指令。

虽然$A$的主频更高，但$B$每秒执行的指令更多，实际程序不一定慢。

即使两台机器的平均$CPI$相同，也不能直接说主频高的那台一定快。因为不同机器的指令集不同，完成同一个任务所需的指令条数可能不同。比如一台机器不支持乘法指令，只能用多次加法实现乘法，指令条数会明显增加。

基准程序

基准程序是用来测量计算机处理速度的一类实用程序，也就是常说的“跑分软件”。它通过运行一组有代表性的程序，比较不同机器的性能。

基准程序也有局限：程序中的语句频度不同，编译器优化不同，$I/O$和操作系统开销也会影响结果，所以跑分高不一定代表所有实际应用都更快。

1.3.4 系统整体的性能指标

数据通路带宽

数据通路带宽是指数据总线一次所能并行传送信息的位数。它反映的是部件之间传送数据的能力，不等于机器字长，也不等于存储字长。比如机器字长是$64$位，外部数据总线可能只有$32$位。

吞吐量

吞吐量是指系统在单位时间内处理请求的数量。它取决于信息能多快地输入主存、$CPU$能多快地取指令、数据能多快地从主存读出或写入，以及结果能多快地送给外部设备。

这些步骤几乎都和主存有关，所以系统吞吐量主要取决于主存的存取周期。提高主存速度、增加$Cache$、采用多模块存储器、使用更宽的数据通路，都可以改善吞吐量。

响应时间

响应时间是指从用户向计算机发送一个请求，到系统对该请求做出响应并获得所需结果的时间。它通常包括：

$CPU$时间：运行程序本身所花费的时间。
等待时间：磁盘访问、存储器访问、$I/O$操作、操作系统开销等时间。

吞吐量和响应时间关注的不是同一个东西：吞吐量看“单位时间能处理多少请求”，响应时间看“一个请求要等多久”。提高吞吐量的措施不一定缩短单个请求的响应时间，反过来也一样。

1.3.5 单位与换算

存储容量、文件大小通常按$2$的幂次换算：

单位	换算关系
$1\ \mathrm{B}$	$8\ \mathrm{bit}$
$1\ \mathrm{KB}$	$2^{10}\ \mathrm{B}$
$1\ \mathrm{MB}$	$2^{20}\ \mathrm{B}$
$1\ \mathrm{GB}$	$2^{30}\ \mathrm{B}$
$1\ \mathrm{TB}$	$2^{40}\ \mathrm{B}$
$1\ \mathrm{PB}$	$2^{50}\ \mathrm{B}$

频率、速率通常按$10$的幂次换算：

单位	换算关系
$1\ \mathrm{kHz}$	$10^3\ \mathrm{Hz}$
$1\ \mathrm{MHz}$	$10^6\ \mathrm{Hz}$
$1\ \mathrm{GHz}$	$10^9\ \mathrm{Hz}$
$1\ \mathrm{THz}$	$10^{12}\ \mathrm{Hz}$

这是本章最常见的单位陷阱：$MIPS$、$MFLOPS$里的$M$是$10^6$；$MB$、$GB$里的$M$、$G$是$2^{20}$、$2^{30}$。做题时先看题目问的是容量还是速率。

1.4 本章例题

例$1$：主存容量与$MAR/MDR$

某机$MAR$为$20$位，$MDR$为$16$位，按字编址。求该机主存容量。

解：

$MAR$为$20$位，说明有$2^{20}$个存储单元；$MDR$为$16$位，说明每个存储单元存放$16$位。因此

$$ \text{主存容量}=2^{20}\times16\ \mathrm{bit} =2^{20}\times2\ \mathrm{B} =2\ \mathrm{MB}. $$

所以主存容量为$2\ \mathrm{MB}$。

如果题目改成“按字节编址”，每个地址对应$1$字节，那么$MAR$的$20$位就对应$2^{20}$字节，即$1\ \mathrm{MB}$。做题时一定要看清编址单位。

例$2$：$CPU$执行时间与$MIPS$

某$CPU$主频为$2\ \mathrm{GHz}$，某程序包含$10^8$条指令，平均$CPI=2.5$。求该程序在该$CPU$上的执行时间和该$CPU$的$MIPS$。

解：

执行时间：

$$ T_{CPU}=\frac{\text{指令条数}\times CPI}{f} =\frac{10^8\times2.5}{2\times10^9} =0.125\ \mathrm{s}. $$

$MIPS$：

$$ MIPS=\frac{f}{CPI\times10^6} =\frac{2\times10^9}{2.5\times10^6} =800. $$

所以程序执行时间为$0.125\ \mathrm{s}$，该$CPU$的$MIPS$为$800$。

例$3$：平均$CPI$、$MIPS$与执行时间

某$CPU$主频为$40\ \mathrm{MHz}$，运行一个基准程序，指令混合比例如下表：

指令类型	$CPI$	指令比例
算术逻辑指令	$1$	$60\%$
转移指令	$4$	$12\%$
$Cache$命中的访存指令	$2$	$18\%$
$Cache$失效的访存指令	$8$	$10\%$

求该程序的平均$CPI$、机器的$MIPS$，以及程序包含$I$条指令时的执行时间。

解：

平均$CPI$：

$$ CPI=1\times60\%+4\times12\%+2\times18\%+8\times10\% =0.6+0.48+0.36+0.8=2.24. $$

$MIPS$：

$$ MIPS=\frac{40\times10^6}{2.24\times10^6}\approx17.86. $$

程序包含$I$条指令时：

$$ T_{CPU}=I\times CPI\times T_c =I\times2.24\times\frac{1}{40\times10^6} =5.6\times10^{-8}I\ \mathrm{s}. $$

所以平均$CPI$为$2.24$，$MIPS$约为$17.86$，执行时间为$5.6\times10^{-8}I$秒。

例$4$：局部加速后的执行时间

某基准程序在计算机上运行的总时间为$100\ \mathrm{s}$，其中$CPU$时间为$90\ \mathrm{s}$，$I/O$时间为$10\ \mathrm{s}$。如果$CPU$速度提高$50\%$，$I/O$速度不变，求新的总运行时间。

解：

$CPU$速度提高$50\%$，意味着新的$CPU$时间变为原来的

$$ \frac{1}{1+50\%}=\frac{1}{1.5}=\frac{2}{3}. $$

所以新的$CPU$时间为

$$ 90\times\frac{2}{3}=60\ \mathrm{s}. $$

$I/O$时间不变，仍为$10\ \mathrm{s}$。因此新的总时间为

$$ 60+10=70\ \mathrm{s}. $$

这类题的关键是：加速只作用于被加速的那一部分，不能把总时间直接除以$1.5$。

1.5 易错点与概念辨析

易混点	正确理解
冯·诺依曼机以谁为中心	早期以运算器为中心，现代计算机以存储器为中心
冯·诺依曼机的根本特征	是“存储程序”，不是五大部件，也不是以运算器为中心
指令和数据的区分依据	指令周期阶段，不是地址，也不是二进制内容
机器字长与存储字长	机器字长是$CPU$一次处理的位数；存储字长是一个存储单元的位数，等于$MDR$位数
指令字长与存储字长	指令字长可以是存储字长的整数倍；为$2$倍时需要$2$次访存取指
$MAR$与$MDR$	$MAR$决定存储单元个数，$MDR$决定每个存储单元的大小
$PC$与$IR$	$PC$存下一条指令地址，$IR$存当前指令
系统软件与应用软件	$OS$、$DBMS$、语言处理程序是系统软件；具体应用系统是应用软件
编译程序与解释程序	编译整体翻译并生成目标程序；解释逐条翻译并立即执行，不生成完整目标程序
汇编程序与编译程序	汇编程序处理汇编语言；编译程序处理高级语言
体系结构与组成	体系结构是程序员可见属性；组成是具体硬件实现
$MIPS$与$MFLOPS$	$MIPS$统计指令条数；$FLOPS$统计浮点运算次数
容量单位与速率单位	容量用$2$的幂次；速率、频率用$10$的幂次
吞吐量与响应时间	吞吐量看单位时间处理多少请求；响应时间看一个请求等多久
主频与性能	主频高不一定快，还要看$CPI$和指令条数
透明性	说“某细节对某层程序员透明”，是指该层程序员看不见、不用关心

还有两个小点：软硬件是“逻辑等效”，不是性能和成本完全等价；系列机是“同一体系结构、不同组成”，通常保证软件向后兼容。

第二章数据的表示和运算

2.1 数制与编码

这一节按当前$408$范围整理：进位计数制、真值和机器数、原码/反码/补码/移码、整数表示、$C$语言整数类型转换；$ASCII$码只保留基本码值作常识。

2.1.1 进位计数制及其相互转换

各种进位计数制大家平时见过、用过不少，这里主要讲清楚基数、位权和几种转换方法。

基数、位权和$r$进制

基数：一种计数制中每个数位所能使用的不同数码的个数。$r$进制的基数就是$r$。
位权：某个数位上的数码所代表的实际权重。小数点左边第$n$位的位权是$r^n$，小数点右边第$m$位的位权是$r^{-m}$。
$r$进制：逢$r$进$1$，每个数位只能出现$0\sim r-1$中的数码。

一个$r$进制数可以按权展开：

$$ N=K_nr^n+K_{n-1}r^{n-1}+\cdots+K_0r^0+K_{-1}r^{-1}+\cdots+K_{-m}r^{-m}. $$

常用进制的基数和数码如下：

进制	基数	数码	常见写法
二进制	$2$	$0,1$	后缀`B`
八进制	$8$	$0\sim7$	后缀`O`或`Q`
十进制	$10$	$0\sim9$	后缀`D`，通常省略
十六进制	$16$	$0\sim9$、$A\sim F$	后缀`H`或前缀`0x`

计算机采用二进制，主要有三个原因：

二进制只有$0$和$1$两个状态，容易用两个稳定状态的物理器件表示。
$0$和$1$正好对应逻辑假和逻辑真，方便实现逻辑运算。
二进制的算术运算规则简单，容易用逻辑电路实现。

任意进制转十进制

方法是按权展开，再把各项相加。例如：

$$ (1101.101)_2=1\times2^3+1\times2^2+0\times2^1+1\times2^0+1\times2^{-1}+0\times2^{-2}+1\times2^{-3}=13.625. $$

十六进制转十进制同理，只是把基数换成$16$，并把$A\sim F$分别看成$10\sim15$。

二进制与八进制、十六进制互转

二进制转八进制：以小数点为界，整数部分从右往左每$3$位一组，小数部分从左往右每$3$位一组，不足$3$位的补$0$，每组对应一个八进制数码。

二进制转十六进制：同样分组，只是每$4$位一组。

例如：

$$ (1011010.1011)_2=(132.54)_8=(5A.B)_{16}. $$

反过来，八进制转二进制时，把每一位八进制数码写成$3$位二进制；十六进制转二进制时，把每一位十六进制数码写成$4$位二进制。整数部分高位补$0$，小数部分低位补$0$。

十进制转任意进制

整数部分和小数部分要分开处理：

整数部分：除基取余，直到商为$0$，然后把余数逆序排列。
小数部分：乘基取整，直到小数部分为$0$或达到题目要求的精度，然后把取出的整数部分顺序排列。

例如把$(75.6875)_{10}$转成二进制：

整数部分$75$：$75=64+8+2+1$，所以$75=(1001011)_2$。
小数部分$0.6875$：$0.6875=0.5+0.125+0.0625$，所以$0.6875=(0.1011)_2$。

因此

$$ (75.6875)_{10}=(1001011.1011)_2. $$

也可以用“拼凑法”做十进制转二进制：把整数拆成$2$的幂之和，把小数拆成$2^{-1},2^{-2},\ldots$之和。比如$75=64+8+2+1$，$0.6875=0.5+0.125+0.0625$，直接就能写出结果。

注意两个方向：整数部分“先得到的余数是低位”，小数部分“先得到的整数是高位”。另外，不是所有十进制小数都能用有限位二进制精确表示，比如$(0.1)_{10}$就是无限循环二进制小数。

2.1.2 真值和机器数

真值是符合人类书写习惯、带正负号的数，比如$+15$、$-8$。机器数是把符号也数字化后，真正存进计算机里的二进制编码。

在机器数中，通常用最高位表示符号位：$0$表示正，$1$表示负；其余位表示数值。比如：

真值	$8$位原码	$8$位补码
$+15$	`00001111`	`00001111`
$-8$	`10001000`	`11111000`

同样是$-8$，用原码表示是10001000，用补码表示是11111000。所以“机器数”不是某一个固定编码的同义词，必须和具体编码规则一起看。

2.1.3 定点数的编码表示

定点数是指小数点的位置固定的数：

定点整数：小数点约定在最低位之后，也就是纯整数。
定点小数：小数点约定在符号位之后、最高数值位之前，也就是纯小数。

机器里并没有真正的小数点，只是人为约定位置。因此定点数的编码和运算主要看符号位和数值位。

下面按王道常用写法：机器数共$n+1$位，最高位是符号位，其余$n$位是数值位。

原码

原码用最高位表示符号，其余位表示数的绝对值。

正数的符号位为$0$。
负数的符号位为$1$，数值位不变。

若字长为$n+1$位，原码整数的表示范围是

$$ -(2^n-1)\le x\le 2^n-1. $$

原码的零有两种表示：$+0$和$-0$。例如$8$位原码中，$+0$是00000000，$-0$是10000000。

原码的优点是直观、和真值转换简单，乘除运算也方便；缺点是零不唯一，加减运算要先判断符号和绝对值大小，电路复杂。

反码

反码的规则是：

正数的反码与原码相同。
负数的反码：符号位不变，数值位按位取反。

反码的表示范围与原码相同，零也有$+0$和$-0$两种表示。例如$8$位反码中，$+0$是00000000，$-0$是11111111。

反码在计算机中很少直接使用，通常只作为原码转补码的中间形式。

补码

补码的规则是：

正数的补码与原码相同。
负数的补码等于反码末位加$1$，也就是原码数值位按位取反后再加$1$。

若字长为$n+1$位，补码整数的表示范围是

$$ -2^n\le x\le 2^n-1. $$

补码比原码和反码多表示一个最小负数。$8$位补码中，10000000表示$-128$，不是$-0$。

补码的零只有一种表示：00000000。补码最大的优点是加减法统一成加法，符号位可以直接参加运算，因此现代计算机中的有符号整数都用补码存储。

已知$[x]{\text{补}}$求$[-x]{\text{补}}$：把$[x]_{\text{补}}$连同符号位全部取反，末位加$1$。

移码

移码通常用于表示浮点数的阶码，只能表示整数。它的定义是给真值加上一个偏置值，常用偏置值为$2^n$：

$$ [x]_{\text{移}}=2^n+x. $$

在补码的基础上，把符号位取反就得到移码；反过来，把移码的符号位取反就得到补码。

移码的特点：

表示范围与补码相同。
零的表示唯一。
移码保持了真值的大小顺序，移码大，真值就大。
移码的符号位为$1$表示非负数，为$0$表示负数，和原码、反码、补码的符号位含义相反。

四种码对比

$n+1$位机器数的表示范围：

编码	定点整数范围	定点小数范围
原码	$-(2^n-1)\le x\le 2^n-1$	$-(1-2^{-n})\le x\le 1-2^{-n}$
反码	$-(2^n-1)\le x\le 2^n-1$	$-(1-2^{-n})\le x\le 1-2^{-n}$
补码	$-2^n\le x\le 2^n-1$	$-1\le x\le 1-2^{-n}$
移码	$-2^n\le x\le 2^n-1$	不用于小数

零的表示：

编码	$+0$	$-0$	零是否唯一
原码	`000...0`	`100...0`	否
反码	`000...0`	`111...1`	否
补码	`000...0`	`000...0`	是
移码	`100...0`	`100...0`	是

$8$位机器数的例子：

真值	原码	反码	补码	移码
$+15$	`00001111`	`00001111`	`00001111`	`10001111`
$-8$	`10001000`	`11110111`	`11111000`	`01111000`
$+0$	`00000000`	`00000000`	`00000000`	`10000000`
$-0$	`10000000`	`11111111`	`00000000`	`10000000`
$-128$	无法表示	无法表示	`10000000`	`00000000`

几个转换关系：

原码转反码：负数符号位不变，数值位取反。
反码转补码：末位加$1$。
补码转原码：负数数值位取反后加$1$，符号位不变；或者也可以负数源码数值位从头开始到第一个1之前为止的位数全部取反。
补码转移码：符号位取反。
移码转补码：符号位取反。

2.1.4 整数的表示

无符号整数

无符号整数的全部二进制位都是数值位，没有符号位。$n$位无符号整数的范围是

$$ 0\le x\le 2^n-1. $$

无符号整数常用于地址运算、指针、计数器等不需要负数的场景。相同字长下，无符号整数能表示的最大值比有符号整数大。

有符号整数

有符号整数把最高位作为符号位，其余位作为数值位。虽然原码、反码、补码、移码都能表示有符号整数，但现代计算机中的有符号整数统一用补码存储。

$n$位补码整数的范围是

$$ -2^{n-1}\le x\le 2^{n-1}-1. $$

同一个位串按无符号和按补码解释，结果可能完全不同：

位串	无符号解释	补码解释
`11111111`	$255$	$-1$
`10000000`	$128$	$-128$
`01111111`	$127$	$127$

补码成为现代计算机标准，主要因为：

零的表示唯一。
加法和减法可以统一成加法，符号位能直接参加运算。
比原码、反码多表示一个最小负数。

2.1.5 $C$语言整数类型与类型转换

常见整数类型

$C$语言中的整型数据本质上就是定点整数。常见类型和典型位宽如下：

类型	典型字节数	典型位宽	有符号范围	无符号范围
`char`	$1$	$8$	$-128\sim127$	$0\sim255$
`short`	$2$	$16$	$-32768\sim32767$	$0\sim65535$
`int`	$4$	$32$	$-2^{31}\sim2^{31}-1$	$0\sim2^{32}-1$
`long`	$4$或$8$	$32$或$64$	视平台	视平台
`long long`	$8$	$64$	$-2^{63}\sim2^{63}-1$	$0\sim2^{64}-1$

char的符号性由实现决定，$C$标准没有规定它一定是有符号还是无符号。short/int/long不写signed/unsigned时默认是有符号类型。

$C$语言中的有符号整数用补码存储，无符号整数用纯二进制存储。类型转换不会改变原变量，只会产生一个按目标类型解释的新值。

同字长有符号数与无符号数转换

同字长转换时，位串不变，只改变解释方式。

short x = -4321;                    // 0xEF1F
unsigned short y = (unsigned short)x; // 0xEF1F，按无符号读为 61215

unsigned short x = 65535;           // 0xFFFF
short y = (short)x;                 // 0xFFFF，按补码读为 -1

所以：

有符号负数转无符号数，符号位变成数值位，值通常会变大。
无符号数转有符号数，最高位变成符号位，值可能变成负数。

大字长转小字长：字截断与位截断

大字长变量转小字长变量时，系统直接丢弃高位，保留低位，然后按目标类型解释。这个操作不会报错。

字截断：按目标字长截断，比如int转short保留低$16$位，short转char保留低$8$位。
位截断：从位串角度看，就是只保留低$n$位；等价于先对$2^n$取模，再按目标类型解释。

int x = 165537;                     // 0x000286A1
short y = (short)x;                 // 0x86A1，按 short 读为 -31071

int u = -34991;                     // 0xFFFF7751
short v = (short)u;                 // 0x7751，按 short 读为 30545

再看一个同时体现字截断和位截断的例子：

int n = 0x123456F8;
short s = (short)n;                 // 0x56F8，值为 22264
unsigned char c = (unsigned char)n; // 0xF8，值为 248

如果把c声明成signed char，0xF8按补码读就是$-8$。所以截断后的值取决于目标类型是有符号还是无符号。

小字长转大字长：符号扩展与零扩展

小字长变量转大字长变量时，需要把高位补齐：

源类型是无符号数：高位补$0$，叫零扩展。
源类型是有符号数：高位补符号位，叫符号扩展。

short x = -4321;                    // 0xEF1F
int y = x;                          // 0xFFFFEF1F，值仍为 -4321

unsigned short u = 61215;           // 0xEF1F
unsigned int v = u;                 // 0x0000EF1F，值仍为 61215

符号扩展不会改变有符号数的值，零扩展不会改变无符号数的值。

宽度和符号性同时变化

如果宽度和符号性同时变化，顺序是固定的：

先按源类型的符号性做扩展或截断，把位串变成目标宽度。
再按目标类型的符号性解释这个位串。

short si = -32767;                  // 0x8001
unsigned int ui = si;               // 0xFFFF8001，值为 4294934529

这里先因为源类型short是有符号数，做符号扩展得到0xFFFF8001；再因为目标类型unsigned int是无符号数，把它读成$4294934529$。

记忆方法：补位问源类型，读数问目标类型。

此外，char、short参与运算时通常会先进行整型提升，转换成int。考试里遇到混合类型表达式，先做整型提升，再判断有没有无符号数参与。

2.1.6 $ASCII$码（了解）

$ASCII$码虽然不是现在的重点，但常见码值有点用。它用$7$位二进制表示$128$个字符，存入内存时通常占$1$字节，最高位补$0$。

字符	十进制	十六进制	二进制
`'0'`	$48$	`30H`	`0011 0000`
`'9'`	$57$	`39H`	`0011 1001`
`'A'`	$65$	`41H`	`0100 0001`
`'Z'`	$90$	`5AH`	`0101 1010`
`'a'`	$97$	`61H`	`0110 0001`
`'z'`	$122$	`7AH`	`0111 1010`

常见规律：

数字字符'0'到'9'的$ASCII$码值连续，'0'是$48$，不是$0$。
大写字母'A'到'Z'、小写字母'a'到'z'分别连续。
小写字母比对应的大写字母大$32$，比如'a'$=97$，'A'$=65$。

运算方法和运算电路

基本运算部件

运算器由算术逻辑单元（$ALU$）、移位器、状态寄存器（$PSW$）和通用寄存器组成。$ALU$的核心是加法器，算术运算最终都可以归结为加法。

$ALU$完成算术运算和逻辑运算：算术运算包括加、减、乘、除，逻辑运算包括与、或、非、异或。运算结果送回寄存器，同时产生$OF$、$SF$、$ZF$、$CF$等标志位。

一位全加器

一位全加器有三个输入：$A_i$、$B_i$和来自低位的进位$C_{i-1}$；两个输出：本位和$S_i$、向高位的进位$C_i$。

$$ S_i=A_i\oplus B_i\oplus C_{i-1} $$

$$ C_i=A_iB_i+(A_i\oplus B_i)C_{i-1} $$

其中$A_iB_i$是进位生成项，$A_i\oplus B_i$是进位传播项。令

$$ G_i=A_iB_i,\qquad P_i=A_i\oplus B_i, $$

则进位可以写成

$$ C_i=G_i+P_iC_{i-1}. $$

真值表：

$A_i$	$B_i$	$C_{i-1}$	$S_i$	$C_i$
$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$1$	$0$
$0$	$1$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$1$	$0$
$1$	$0$	$1$	$0$	$1$
$1$	$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

串行进位加法器

把$n$个一位全加器级联，低位的进位输出直接接到高位的进位输入，就得到$n$位串行进位加法器。进位从低位向高位逐级传递，所以又叫行波进位加法器。

设一位全加器的进位延迟为$t_c$，和延迟为$t_s$，则$n$位串行进位加法器的最坏进位延迟约为$n t_c$，和的最坏延迟约为$n t_c+t_s$。

串行进位加法器结构简单，但位数多时进位传递很慢。位数较多时通常采用先行进位，让各位的进位并行产生。

带标志加法器

在$n+1$位加法器（$1$位符号位加$n$位数值位）上增加标志位逻辑，就得到带标志加法器。设结果位为$F_nF_{n-1}\cdots F_0$，$C_n$是最高数值位向符号位的进位，$C_{n+1}$是符号位向外的进位。

标志	名称	产生条件	含义
$OF$	溢出标志	$OF=C_n\oplus C_{n+1}$	有符号数溢出
$SF$	符号标志	$SF=F_n$	结果的正负
$ZF$	零标志	结果所有位为$0$时$ZF=1$	结果是否为$0$
$CF$	进位/借位标志	加法时$CF=C_{n+1}$；减法时$CF=C_{n+1}\oplus1$	无符号数溢出或借位

$OF=1$表示最高数值位向符号位的进位与符号位向外的进位不同，结果溢出。$CF$只用于无符号数：加法时$CF=1$表示进位，减法时$CF=1$表示借位。

定点数的移位运算

移位运算分为逻辑移位和算术移位。逻辑移位把操作数看成无符号数；算术移位把操作数看成有符号数，符号位要保持不变。

逻辑移位

左移：高位移出，低位补$0$。若移出的高位中有$1$，则无符号数溢出。
右移：低位移出，高位补$0$。移出的低位会影响精度。

左移一位相当于乘以$2$，右移一位相当于除以$2$。

算术移位

算术移位保持符号位不变，只移动数值位。不同编码的补位规则如下：

编码	正数左移	正数右移	负数左移	负数右移
原码	低位补$0$	高位补$0$	低位补$0$	高位补$0$
反码	低位补$0$	高位补$0$	低位补$1$	高位补$1$
补码	低位补$0$	高位补$0$	低位补$0$	高位补$1$

表中的补位都指数值位，符号位不参加移动。实际计算机中的有符号整数用补码，所以重点掌握补码：左移时低位补$0$，右移时高位补符号位。

补码算术左移一位时，若左移后的符号位与原符号位不同，则溢出；等价于原数最高两位不同，即01...或10...。一次左移$k$位时，不能只看符号位，要看最高$k+1$位是否全等于原符号位，或者直接用结果是否超出表示范围判断。

原码和反码的算术左移，符号位本身不变，溢出要看数值位是否超出范围。算术右移不会溢出，但会丢掉低位；负的补码右移一位相当于向下取整除以$2$。

运算	$8$位补码	真值
$+5$左移一位	`00001010`	$+10$
$-5$左移一位	`11110110`	$-10$
$-5$右移一位	`11111101`	$-3$
$+64$左移一位	`10000000`	溢出

定点数的加减法运算

补码加减运算

设字长为$n+1$位，即$1$位符号位加$n$位数值位，则

$$ [A+B]_{\text{补}}=[A]_{\text{补}}+[B]_{\text{补}}\pmod{2^{n+1}} $$

$$ [A-B]_{\text{补}}=[A]_{\text{补}}+[-B]_{\text{补}}\pmod{2^{n+1}} $$

符号位和数值位一起参加运算，结果的符号位由运算得出。运算结果自动截断为$n+1$位，最高位的进位丢弃，结果仍然用补码表示。

例如，$8$位补码中：

$+12$是00001100，$-7$是11111001，相加得到00000101，即$+5$。
$-5$是11111011，$-9$是11110111，相加得到11110010，即$-14$。
$+5-7$用$+5$加$-7$的补码：00000101加11111001得到11111110，即$-2$。

溢出判别方法

补码加减运算只在同号相加或异号相减时可能溢出。常用的判别方法有三种。

一位符号位判断

设两个操作数的符号位分别为$A_S$、$B_S$，结果符号位为$S_S$，则溢出条件为

$$ V=A_SB_S\bar{S_S}+\bar{A_S}\bar{B_S}S_S. $$

也就是说，两个正数相加得到负数，或者两个负数相加得到正数，就发生溢出。

进位判断

设$C_n$是最高数值位向符号位的进位，$C_{n+1}$是符号位向外的进位，则

$$ V=C_n\oplus C_{n+1}. $$

最高数值位的进位和符号位的进位不同，说明结果溢出。

双符号位判断

双符号位也叫变形补码，用$S_{s1}S_{s2}$表示两个符号位，其中$S_{s1}$是高位符号位。两个符号位不同就表示溢出：

$S_{s1}S_{s2}$	含义
`00`	结果为正，无溢出
`01`	正溢出
`10`	负溢出
`11`	结果为负，无溢出

溢出表达式为

$$ V=S_{s1}\oplus S_{s2}. $$

例如，$+100$的$8$位补码是01100100，两个$+100$相加得到11001000，符号位由$0$变成$1$，说明溢出。

加减运算电路

加减运算电路在加法器的基础上增加控制信号$Sub$：$Sub=0$时做加法，$Sub=1$时把减数各位取反，并在最低位加$1$，从而把减法变成加法。

减法时借位标志为

$$ CF=C_{\text{out}}\oplus Sub. $$

因此，加法时$CF=C_{\text{out}}$；减法时$CF=C_{\text{out}}\oplus1$，$CF=1$表示有借位。

执行$A-B$后，可以用标志位比较大小：

比较	无符号数	有符号数
$A=B$	$ZF=1$，$CF=0$	$ZF=1$
$A>B$	$ZF=0$，$CF=0$	$ZF=0$，$SF\oplus OF=0$
$A<B$	$ZF=0$，$CF=1$	$ZF=0$，$SF\oplus OF=1$

无符号数比较看$CF$，有符号数比较看$SF\oplus OF$。

定点数的乘除运算

乘法运算

乘法本质上是被乘数根据乘数每一位的值进行“移位—相加”。$n$位无符号数相乘得到$2n$位乘积；有符号数还要额外处理符号。

原码一位乘法

原码乘法的符号位和数值位分开处理：

乘积的符号位等于两个乘数符号位的异或。
乘积的数值位等于两个乘数绝对值相乘，也就是两个无符号数相乘。

原码一位乘法的步骤是：

部分积初始化为$0$。
看乘数末位：为$1$时部分积加被乘数，为$0$时加$0$。
部分积和乘数一起右移一位。
重复$n$次，最后把部分积和乘数拼接起来，得到$2n$位数值位，再补上符号位。

例如，$x=-0.1101$，$y=+0.1011$。符号位为$1$，数值位做无符号乘法：

两个乘数的小数部分共有$8$位，所以数值位为$0.10001111$，结果为

$$ [x\cdot y]_{\text{原}}=1.10001111. $$

乘法电路基本结构

顺序乘法器由被乘数寄存器、乘积寄存器、加法器、移位器和控制逻辑组成。它每次判断乘数末位，决定部分积加被乘数还是加$0$，然后右移，$n$位乘法需要$n$次加法和移位。

阵列乘法器用组合逻辑并行产生所有部分积并求和，速度快，但需要的门电路多、面积大。

除法运算

除法是乘法的逆运算，基本思想是“比较—减—上商—移位”。在运算之前，先对被除数和除数的取值进行讨论：

被除数为$0$，除数不为$0$，或$\lvert\text{被除数}\rvert<\lvert\text{除数}\rvert$时，商为$0$，余数等于被除数。
被除数不为$0$，除数为$0$时，发生“除$0$”异常。
被除数和除数同时为$0$时，发生除法错误异常。
被除数和除数均不为$0$，且$\lvert\text{被除数}\rvert\ge\lvert\text{除数}\rvert$时，进入除法计算。

定点小数除法通常要求$\lvert\text{被除数}\rvert<\lvert\text{除数}\rvert$，否则商可能超出定点小数的表示范围；整数除法允许两者相等，此时商为$1$，余数为$0$。

原码除法

原码除法的符号位和数值位也分开处理：商的符号位等于被除数和除数符号位的异或，数值位用无符号数除法。

恢复余数法的步骤是：

余数寄存器初值放被除数，除数寄存器放除数，商寄存器清$0$。
余数左移一位，减除数。
若余数大于等于$0$，商上$1$；若余数小于$0$，商上$0$，并把除数加回去，恢复原来的余数。
重复$n$次，得到$n$位商。

加减交替法又叫不恢复余数法。它根据上一次余数的符号决定下一步是加除数还是减除数，不需要把除数加回去，因此速度更快。

除法电路基本结构

除法电路通常由被除数/余数寄存器、除数寄存器、商寄存器、加法器、移位器和控制逻辑组成。恢复余数法需要额外的恢复余数操作；加减交替法直接把恢复余数合并到下一步的加/减中，控制更简单，速度也更快。

浮点数的表示和运算

$\mathrm{IEEE}\ 754$标准浮点数

格式

$\mathrm{IEEE}\ 754$浮点数把数分成符号位、阶码和尾数三部分。单精度和双精度的格式如下：

类型	总位数	符号位$S$	阶码$E$	尾数$M$	偏置值
单精度	$32$	$1$	$8$	$23$	$127$
双精度	$64$	$1$	$11$	$52$	$1023$

符号位$S=0$表示正数，$S=1$表示负数。规格化浮点数的真值为

$$ (-1)^S\times1.M\times2^{E-\text{偏置值}}. $$

其中$1.M$表示尾数隐藏了最高位的$1$，实际存储的只有小数点后的$M$。阶码用移码表示，但$\mathrm{IEEE}\ 754$的偏置值是$2^{k-1}-1$，不是$2^{k-1}$。

阶码和尾数的特殊组合表示特殊值：

阶码$E$	尾数$M$	含义
全$0$	全$0$	$\pm0$
全$0$	非$0$	非规格化数
全$1$	全$0$	$\pm\infty$
全$1$	非$0$	$\mathrm{NaN}$

非规格化数没有隐藏的$1$，真值为

$$ (-1)^S\times0.M\times2^{1-\text{偏置值}}. $$

例如，把$-12.75$写成单精度浮点数：

$$ -12.75=-1100.11_2=-1.10011\times2^3. $$

符号位$S=1$，阶码$E=3+127=130=(10000010)_2$，尾数$M=10011$后面补$18$个$0$，得到

1 10000010 10011000000000000000000

即十六进制C14C0000H。

范围

单精度的阶码为$8$位，偏置值为$127$：

最大阶码为$254-127=127$，最大正数为$(2-2^{-23})2^{127}$。
最小规格化正数为$1.0\times2^{-126}=2^{-126}$。
最小非规格化正数为$2^{-149}$。

双精度的阶码为$11$位，偏置值为$1023$：

最大阶码为$2046-1023=1023$，最大正数为$(2-2^{-52})2^{1023}$。
最小规格化正数为$2^{-1022}$。
最小非规格化正数为$2^{-1074}$。

类型	最小正规格化数	最小正非规格化数	最大正数
单精度	$2^{-126}$	$2^{-149}$	$(2-2^{-23})2^{127}$
双精度	$2^{-1022}$	$2^{-1074}$	$(2-2^{-52})2^{1023}$

浮点数的范围由阶码位数决定，精度由尾数位数决定。单精度大约有$7$位十进制有效数字，双精度大约有$15\sim16$位十进制有效数字。

超过最大正数的范围会发生上溢；小于最小非规格化正数时会下溢为$0$；落在非规格化范围内时，数值仍能表示，但有效位数会减少。

浮点数的加减运算

对阶

使两个操作数的小数点位置对齐，即令它们阶码相等。原则是小阶向大阶看齐，即将阶码较小的数的尾数右移，右移位数等于两阶码差的绝对值。对阶时需要进行移码减法运算以求得阶码差。尾数右移时，符号位不参与移动；对于规格化数，隐藏位1会随着尾数右移进入小数部分，空出的高位补0。移出的尾数不应丢弃，而应保留并参与后续运算。

$A_i$	$B_i$	$C_{i-1}$	$S_i$	$C_i$
$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$1$	$0$
$0$	$1$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$1$	$0$
$1$	$0$	$1$	$0$	$1$
$1$	$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

$A_i$	$B_i$	$C_{i-1}$	$S_i$	$C_i$
$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$1$	$0$
$0$	$1$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$1$	$0$
$1$	$0$	$1$	$0$	$1$
$1$	$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$