计组与操作系统融合精讲

0.1计算机只认识“开”和“关”

计算机里最小的零件是晶体管，你可以把它想成一个电灯开关：只有“通电”和“不通电”两种状态。我们把“通电”记作 1，“不通电”记作 0。

• 一个开关能记住 1 个 0 或 1，这叫 1 位（bit，简写 b）。
• 8 个开关排成一排，叫 1 字节（Byte，简写 B）。8 个开关一共有 2×2×…×2 = 2⁸ = 256 种开关组合，所以 1 字节能区分 256 种东西。
• n 位能表示 2ⁿ 种不同的组合——这是全书用得最多的一句话。

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

0.2十进制、二进制、十六进制

我们平时用的十进制，本质是“逢十进一”，每一位的权重是 1、10、100……。二进制就是“逢二进一”，权重是 1、2、4、8……。这几种进制之间怎么互相换算，就是教材里的进制转换。

二进制太长，人看着眼花，于是有了十六进制：逢十六进一，用 0~9 和 A(10)、B(11)、C(12)、D(13)、E(14)、F(15) 共 16 个符号。408 里十六进制数常在末尾写 H（如 2000H），C 语言里写 0x 前缀（如 0x2000），两种写法意思一样。

最重要的技巧：1 个十六进制位 = 4 个二进制位

因为 16 = 2⁴，所以十六进制和二进制可以四位四位直接对照，不用经过十进制。把下面这张表背熟（其实只要会数数）：

例：2F3AH → 2=0010，F=1111，3=0011，A=1010 → 0010 1111 0011 1010。反过来，二进制从右往左每 4 位一组（最左边不够 4 位就在前面补 0），每组换成一个十六进制位。

八进制，以及“任意进制 → 十进制”

八进制逢八进一，只用 0~7 八个符号。因为 8 = 2³，1 个八进制位 = 3 个二进制位，道理和十六进制完全一样，只是 3 位一组。C 语言里以 0 开头的整数是八进制（017 是十进制的 15，不是 17），教材里常在末尾写 O 或 Q（17O、17Q）。408 里八进制很少出现，会换就行。

任意 r 进制 → 十进制：按权展开。小数点左边第 0、1、2 位的权是 r⁰、r¹、r²……，小数点右边第 1、2、3 位的权是 r⁻¹、r⁻²、r⁻³……每一位“数码 × 权”再加起来：

带小数点的二进制换成十六进制（八进制）：从小数点出发，往两边分组。整数部分往左每 4 位（3 位）一组，最左边不够在左边补 0；小数部分往右每 4 位（3 位）一组，最右边不够在右边补 0。小数部分如果把 0 补在左边，就把 0.1 变成了 0.0001，值全变了。

十进制 → 二进制

• 整数部分：除 2 取余，倒着写。例：13 → 13÷2=6 余 1，6÷2=3 余 0，3÷2=1 余 1，1÷2=0 余 1 → 倒读 1101。更快的办法是“凑 2 的幂”：13 = 8+4+1 = 1101。
• 小数部分：乘 2 取整，正着写。例：0.25 → ×2=0.5 取 0，×2=1.0 取 1 → 0.01₂。
• 有的小数乘不尽：0.1 → 0.2(0)→0.4(0)→0.8(0)→1.6(1)→1.2(1)→0.4(0)… 无限循环 0.000110011…₂。所以0.1、0.2、1.2 这样的小数计算机存不精确；而 0.5、0.25、0.125、1.25 这类“分母是 2 的幂”的小数可以精确存。
• 换成八进制、十六进制也是同一套办法：整数部分“除 8（16）取余、倒着写”，小数部分“乘 8（16）取整、正着写”。但考场上更快、更不容易错的永远是先变成二进制，再 3 位（4 位）一组。

0.32 的幂与单位：408 计算题的“九九乘法表”

于是任何“2 的幂”都能口算：4KB = 2²×2¹⁰ B = 2¹² B；64MB = 2⁶×2²⁰ = 2²⁶ B；4GB = 2³² B。反过来，“2ⁿ 个东西需要 n 位编号”，记作 n = log₂(个数)。

为什么是 2ⁿ？每多一位，就是在原来所有编号前面分别写一个 0 和一个 1，编号的个数翻一倍：

两种“K”：存储用 2¹⁰，速度用 10³

真题里偶尔两者混在一个式子里（比如 “0.5MB/s 的设备，每次传 4B”）。408 的评分答案一般直接按题目数字算（0.5MB/4B = 125000 次/秒，把 M 当 10⁶），除非题目明确给了 2²⁰。遇到页面、块这种“容量”，一律按 2 的幂。

b 和 B、时间单位

• 小写 b = bit（位），大写 B = Byte（字节），1B = 8b。网络、总线的“Mbps”是兆位每秒；“MB/s”是兆字节每秒，差 8 倍。
• 时间：1 s = 10³ ms（毫秒）= 10⁶ μs（微秒）= 10⁹ ns（纳秒）= 10¹² ps（皮秒）。
• 频率和周期互为倒数：主频 500MHz → 时钟周期 = 1/(500×10⁶) s = 2 ns。

0.4地址：内存就是一排带门牌号的格子

主存（内存）可以想成一条很长的街，每个格子是一个存储单元，门牌号就是地址。CPU 要读写内存，必须先说出门牌号。

按字节编址 vs 按字编址

按字节编址：每个地址对应 1 个字节（现在几乎都是这样，408 大题也基本是）。按字编址：每个地址对应 1 个“字”（字长 16 位就是 2 字节一个地址）。同样 16 位地址，按字节编址能访问 2¹⁶ B = 64KB，按 16 位字编址能访问 2¹⁶×2B = 128KB。

练习：20 位地址、按字节编址 → 地址空间 2²⁰ B = 1MB，地址范围 00000H ~ FFFFFH（20 位 = 5 个十六进制位，全 1 就是 FFFFF）。一块 8KB 的区域从 0800H 开始，最后一个地址是 0800H + 2000H − 1 = 27FFH（8K = 2¹³ = 2000H；十六进制加法 0800H + 2000H = 2800H，再减 1）。

0.5逻辑运算与位运算

对一串位逐位做这些运算，就是“位运算”。它在 408 里主要有三个用途：

1. 取出某几位（掩码）：想要 x 的低 8 位，就算 x AND 0xFF（0xFF = 1111 1111，与 1 保留、与 0 清零）。
2. 移位 = 乘除 2 的幂：左移 1 位相当于 ×2，右移 1 位相当于 ÷2（取整）。所以“地址右移 12 位”就是“去掉低 12 位的页内偏移，只剩页号”。
3. 组合起来切字段：2013-46 让写二级页表的页目录号：(LA >> 22) & 0x3FF——先右移 22 位把低位扔掉，再和 10 个 1 做与运算只留 10 位。

下面这张图把“切字段”完整做一遍。它就是第 8 篇分页、Cache 题的第一步，先在这里练熟：

试试：输入 −9 选 16 位看它的补码 FFF7H；输入 134 选 8 位看它当有符号数是多少；输入 FFFFFFDFH 选 32 位。第 2 篇会解释这些结果为什么是这样。

0.6本讲义的记号约定

0.✎本篇真题闯关（1 题）

本篇各小节挂的真题全部在这里，按小节排好。可以展开后一道道做，也可以用弹窗模式连续做。做题记录（对/错）只保存在你这台电脑的浏览器里，小节标题下的题号会随之变绿或变红。

本篇学完

2.1无符号数和补码：用“时钟”理解负数

先认几个名词：真值、机器数、定点数

真值是带“+、−”号的数本身（如 −13、+0.625）；机器数是它在机器里的 0/1 编码，连正负号也用 0（正）、1（负）来表示。机器里还要约定小数点在哪：小数点位置固定不变的叫定点数，小数点位置随“阶码”浮动的叫浮点数（2.6 节）。定点数分两种：

无符号数最简单：n 位二进制直接按权重相加，范围 0 ~ 2ⁿ−1。8 位是 0~255，16 位是 0~65535。

负数怎么办？最直观的想法是拿最高位当符号（0 正 1 负），后面放绝对值，这叫原码。但原码有两个 0（+0 和 −0），而且加法电路要先比较符号，很麻烦。计算机真正用来存整数的是补码，它的想法来自钟表：

四种编码放在一起比一比

补码是主角，另外三种选择题会考“范围、0 有几个、怎么互相转换”。以 8 位的 −5 为例：

记三句话：① 正数的原、反、补码都一样；② 偏置为 2ⁿ⁻¹ 的移码 = 补码把符号位取反（−5：补码 1111 1011 → 移码 0111 1011）；③ 移码的好处是比大小可以直接按无符号比，所以浮点数的阶码用它。注意 IEEE 754 的偏置是 127 而不是 128（2.6 节），所以它的阶码不是“标准”移码。

定点小数的编码和四种编码的表示范围

定点小数的编码规则和整数一模一样，只是数值位的权重变成 2⁻¹、2⁻²……。例：x = −0.1011₂（= −0.6875），用 1 位符号 + 4 位数值：原码 1.1011；反码 1.0100；补码 1.0101（= 2 + x，“绕一圈”的圈长从 2ⁿ 变成了 2）。补码的符号位权重是 −1：1.0101 = −1 + 0.0101₂ = −1 + 0.3125 = −0.6875 ✓。

上表里 n 是数值位个数（总位数 n+1）。前面公式“n 位补码范围 −2ⁿ⁻¹ ~ 2ⁿ⁻¹−1”里的 n 是总位数，两种写法说的是同一件事，做题时先看清题目给的是总位数还是数值位数。

四种编码互相转换的速算法

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

2.2C 语言里的类型转换：位串到底变没变

这是真题最爱考的地方（2009、2012、2016、2019、2024、2025 都有选择题，2011-43、2017-43 是大题）。只要记住三条规则：

C 语言各类型占多少位（408 默认 32 位机器）

题目若另有规定（如 2011-43 的“8 位字长计算机”里 int 是 8 位），以题目为准。

整数和浮点数之间怎么转

有符号数与无符号数混用：比较结果会“反常”

C 规定：一个运算（包括比较）的两边一个是 int、一个是 unsigned int 时，先把 int 按位串不变转成 unsigned 再算。于是负数一下变成很大的正数：

以上结果都用 gcc 实测过。char、short 参与运算时先被提升成 int（“整型提升”），所以两个 short 相加不会在 16 位上溢出，而是先变成 int 再加。

跟我判：混合类型的表达式到底按什么类型算

问题引入：上面两张表分别讲了“整数 ↔ 浮点”和“有符号 ↔ 无符号”。真题常把它们揉进一个表达式：-1 > 1u 为什么是真？两个 short 比较为什么又不会“反常”？关键是先判断这个运算最终按哪种类型做。

大白话：C 语言做二元运算前，先把两边“拉到同一个类型”，而且总是往“能装下更多东西”的方向拉，像两个人对暗号前先统一用哪种语言。不像的地方：往 unsigned 拉的时候并不保证“装得下”负数——−1 会被硬读成 4294967295，这正是坑所在。

教材 / C 标准的说法（408 默认 32 位，int 与 long 都是 32 位）：① 整型提升：char、short（不论有无符号）参加运算前先变成 int；② 寻常算术转换：两边类型不同时，向下图中靠右的类型转换；③ 赋值时转换成左边变量的类型（可能截断、可能舍入）。

跟我判（32 位，结果全部 gcc 实测，程序见 verify/08/p02_mix.c）：

真题怎么考：2009-12（short 与 int 相加，y 先符号扩展）、2016-13 / 2019-13（等长换读法）、2017-43（无符号 n − 1 绕圈导致死循环）、2010-14（int、float、double 来回转）。判别法：先找出运算的最终类型，再决定是“位串不变换读法”“扩展”“截断”还是“舍入”。失效的情况：题目换了机器（如 2011-43 的 8 位机里 int 只有 8 位），类型位数要按题目改。

大题精讲：2011-43（8 位机上的有符号/无符号运算）

unsigned int x = 134;  unsigned int y = 246;
int m = x;  int n = y;
unsigned int z1 = x - y;  unsigned int z2 = x + y;
int k1 = m - n;  int k2 = m + n;

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

2.3移位：逻辑移位与算术移位

• 左移 1 位 = ×2，右移 1 位 = ÷2。算术右移对负数是向下取整：−513 算术右移 1 位 = −257（不是 −256）。16 位 −513 = FDFFH → FEFFH（2012-44 第 1 问）。
• 算术左移时，如果移出去的位和新的符号位不同，就溢出了（值超出范围）。
• 编译器常把“乘以常数”优化成移位和加法：x*2 → 左移 1 位；a[i] 的地址 = 首地址 + i×4 → 用 sll R4, R2, 2（左移 2 位）算 i×4（2014-44、2024-44）。

原码、反码、补码各自怎么算术移位

上面讲的“算术移位”是对补码而言的。教材还要求知道原码、反码的算术移位：规则是符号位不动，只移数值位，空出来的位补什么，取决于“补什么才能让值恰好 ×2 或 ÷2”：

红色是新补进来的位。三种码移位后分别是 −52、−13 的原码、反码、补码（已验算）。什么时候出错：左移时如果移出去的数值位不是“本该补进来的那个值”（正数移出 1；原码负数移出 1；反码、补码负数移出 0），结果就超出范围了（溢出）；右移时移出 1 只会丢精度（相当于舍入）。

循环移位：不带进位（小循环）与带进位（大循环）

问题引入：逻辑移位、算术移位都会把移出去的那一位“扔掉”。可如果想把一个 16 位数的高低字节对调，或者在 8 位机上把一个 16 位数整体左移一位，扔掉的那一位就必须“找回来”——这就要用循环移位。

跟我做一遍（已用 verify/08/p02_calc.py 验算）：

1. 交换高低字节：16 位 1234H 不带进位循环左移 8 位 → 3412H。高字节 12H 整个转到了低位——2.7 节大小端互换时，硬件或库函数就是这样做的。
2. 多字长移位：8 位机上把 16 位数 0001 0010 | 1011 0100 左移 1 位。先对低字节逻辑左移：1011 0100 → 0110 1000，移出的最高位 1 进入 CF；再对高字节做带进位循环左移：0001 0010 → 0010 0101（CF 的 1 补进最低位）。拼起来 0010 0101 0110 1000，和直接 16 位左移的结果一样。

真题怎么考：408 选择题考的多是逻辑移位和算术移位（2013-14、2018-16、2026-13），循环移位一般作为“移位类型”的概念出现。判别只看两件事：移出去的位去哪、空出来的位补什么。失效的情况：带进位循环移位的结果取决于原来的 CF，题目没给 CF 的值就不能确定最低（高）位。

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

2.4加减法电路与四个标志位

CPU 里只有一个加法器，减法 A − B 是这样做的：把 B 按位取反，再让最低位进位输入为 1，于是算的是 A + (~B) + 1 = A + [−B]补。运算完，电路顺手生成四个标志位存进标志寄存器（PSW），后面的条件跳转指令就靠它们判断大小。

补码加减法的公式与溢出判断的三种方法

补码加减法的全部规则就两条公式（都是“模 2ⁿ”，最高位的进位直接丢掉）：

符号位和数值位一起参加运算，不用单独处理符号——这就是计算机用补码的原因。（原码加减要先比较两数符号：同号相加、异号用大绝对值减小绝对值，结果取大者的符号，电路麻烦得多，所以只作了解。）

溢出：结果超出了 n 位补码的表示范围。只有同号相加（或异号相减）才可能溢出；异号相加的结果绝对值不会变大，永远不溢出。判断方法有三种，考研要求三种都会：

加法器是怎么搭起来的

大纲要求知道“加法器、ALU 的基本结构”。从最小的积木说起：一位全加器（FA）把两个加数的第 i 位 A_i、B_i 和低位送来的进位 C_i 相加，得到本位和 S_i 和向高位的进位 C_i+1。n 个全加器连起来就是 n 位加法器。

串行加法器、并行加法器和 ALU

结论记一句：并行加法器的速度主要取决于进位的传递速度；提高速度的关键是改进进位方式。“加法器的进位方式”属于计算机组成，不属于 ISA（2022-18 Ⅳ）。

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

2.5乘法和除法：原理和电路结构

大纲对乘除法只要求两件事：基本原理和电路的基本结构。真题怎么考？2020-43 问“没有乘法指令怎么算乘法、控制逻辑干什么、三种实现谁快”，2024-15 问“乘法能不能一个周期完成”，2025-44 直接画了一个除法器问寄存器初值和计数器在哪。所以不用背复杂的算法，把“竖式”搬到电路上就够了。

乘法 = 移位 + 加法（和小学竖式一模一样）

先用十进制回忆：123 × 45，就是“123 × 5”加上“123 × 4 再左移一位（×10）”。二进制更简单，因为乘数的每一位只可能是 0 或 1：这一位是 1，就把被乘数（左移到对应位置）加上；是 0，就什么都不加。

乘法器的基本结构：ALU + 移位 + 寄存器 + 控制逻辑

用图里的电路把 13 × 11 跑一遍（C 是加法产生的进位，右移时一起移进 P 的最高位）：

最后 P、Y 拼起来 1000 1111 = 143。乘数 Y 的位被一位一位“挤出去”，腾出的位置正好装积的低位——所以一个寄存器身兼两职。

三种实现方式谁快（2020-43 第 3 问、2024-15）

另外两条常考结论：变量乘以常数，编译器会优化成移位和加减（x*9 = (x<<3) + x，a[i] 的地址 i*4 = i<<2）；两个变量相乘也能编译成“移位+加法”的循环（就是 ①），所以 2024-15 的 D 说“无法”是错的。

带符号的数怎么乘：原码一位乘法、补码一位乘法

上面的电路算的是两个无符号数（或绝对值）。带符号数有两种办法：

积 = A、Q 拼起来 1111 0001 = −15 = 5 × (−3) ✓（已用程序验算）。为什么这样做是对的：乘数里一串连续的 1（如 0111 1000）等于“高一位的权 − 最低那个 1 的权”（1000 0000 − 0000 1000），所以只需在一串 1 的开始处减一次、结束处加一次——“10”正是一串 1 的开始，“01”正是结束。王道教材用的是定点小数写法（部分积用双符号位，共做 n+1 次加法、最后一次不移位），原理相同。

乘法溢出：积要 2n 位，只留低 n 位时怎么判断

直觉：有符号数的低 n 位最高位是“符号位”，如果高 n 位只是它的符号扩展，说明真值没超过 n 位补码能表示的范围。2019-45 第 5 问、2020-43 第 4 问都这样判。

真题怎么考：选择题（2010-13）直接给 8 位补码让你判断哪个乘法溢出——最快的办法是换成真值相乘、看是否超出 −128 ~ 127；大题（2019-45 第 5 问、2020-43 第 4 问）要你说出机器“怎么判断”，就答上面的规则。失效的情况：无符号乘法和有符号乘法的规则不同，同一个 2n 位积（如 008CH）当无符号不溢出、当有符号却溢出，先看清题目是哪种。

除法 = 移位 + 试减

除法同样照搬竖式：从高位开始，每次把余数左移一位、拉下一位被除数，然后试着减去除数——够减，商上 1、保留差；不够减，商上 0（再把减掉的加回来，或者下一步改做加法补偿）。

除法器（2025-44 的图就是它）：余数寄存器 R 和被除数/商寄存器 Q 连成 2n 位。开始时 2n 位被除数放在 R、Q 里（32 位有符号被除数要先符号扩展成 64 位：高 32 位进 R，低 32 位进 Q），除数放 Y。每一步 R、Q 一起左移一位，ALU 算 R − Y 或 R + Y，根据结果的正负在 Q 的最低位上商 0 或 1。循环 n 次后，Q 里是商，R 里是余数。所以 ALU 只要会加法和减法两种运算，计数器在控制逻辑里。

恢复余数法与加减交替法（不恢复余数法）

“试减”试错了怎么办？有两种处理方式：

商 Q = 0100 = 4，余数 A = 1，13 = 3 × 4 + 1 ✓（已用程序验算，恢复余数法得到同样结果）。带符号的原码除法同乘法：商的符号 = 两数符号异或，数值部分用绝对值相除；补码除法 拓展 规则类似，只是“商 1 还是商 0”要比较余数和除数的符号是否相同。

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

2.6浮点数 IEEE 754：计算机里的“科学计数法”

十进制科学计数法：−1234.5 = −1.2345 × 10³。二进制也一样：−8.25 = −1000.01₂ = −1.00001₂ × 2³。规格化后小数点前总是 1，所以这个 1 不用存（“隐藏位”），只存小数点后面的部分。

先看教材的一般格式：阶码 + 尾数

在讲 IEEE 754 之前，教材先讲一种“通用”的浮点格式，选择题（2009-13）和概念题都会用到。一个浮点数写成

阶码（含阶符）是定点整数，它的位数决定数的表示范围；尾数（含数符）是定点小数，它的位数决定精度；数符决定整个数的正负。

规格化：让尾数的最高位“有效”

同一个数有很多种写法：0.1×2³ = 0.01×2⁴ = 0.001×2⁵……后面几种白白在尾数最前面浪费了几个 0，精度变差。规格化就是规定尾数的最高数值位必须是有效数字，这样表示唯一、精度最高：

最大负数的尾数不能取 1.100…0（−1/2），因为那不是规格化数；往下一格是 1.011…1。

IEEE 754：今天真正在用的格式

IEEE 754 和上面的一般格式相比有三处不同：尾数用原码且规格化形式是 1.M（隐藏最前面的 1，多出一位精度）；阶码用移码但偏置是 127（不是 128）；阶码全 0、全 1 留作特殊用途。

float（单精度，32 位）。double（双精度，64 位）：1 + 11（偏置 1023）+ 52。

编码：十进制 → 机器数（四步走）

1. 定符号：正数 S = 0，负数 S = 1，后面只处理绝对值。
2. 化成二进制：整数部分除 2 取余，小数部分乘 2 取整（0.25 = 0.01₂，0.75 = 0.11₂，0.1 化不尽，只能近似）。
3. 规格化：把小数点移到第一个 1 的后面，写成 1.xxx × 2^k；阶码 E = k + 127，写成 8 位二进制。
4. 拼接：S | E（8 位）| 小数点后的 xxx（补 0 到 23 位，最前面的 1 不存），32 位每 4 位一组换十六进制。