CS110 计算机体系结构 1 “万物皆数”

前置数学知识

任何一门计算机课程都高低需要一些数学知识。不过还请读者放心，这门课的前置数学知识算是非常少的那一类，比人工智能，机器学习相关的课程好多了。

进位制

本课程中会用到的进位制有：二进制 bin，十进制 dec，十六进制 hex。这些进制数都有各自的前缀，不过在本课程中，一般只有二进制和十六进制会加前缀：0b00011001 0xDEADBEEF 这样的。如果不加前缀，默认为十进制用法。

进位制之间的转换上，对于向十进制的转换，直接用位权乘以数值求和即可；对于从十进制向其它进制的转换，用短除法倒序读取余数即可；对于二进制和十六进制的互相转换，使用“8421”大法即可。如果读者对以上内容有不理解之处，请自行搜索。

布尔逻辑

即一些简单的与或非相关化简。在本课程中，我们使用 + 表示或运算，什么都不写（即乘法省略乘号）表示与运算，符号上方加一横表示非运算。

举个例子，“(A或B)与(B或C)” 翻译成布尔逻辑即为

这样将与或运算向加法乘法映射的做法非常有道理，因为二者的运算逻辑非常类似，比如说都有类似的交换律、结合律和分配律。具体运算法则如下图所示：

最小项之和 sum-of-minterm

一种等效替代卡诺图 Karnaugh Map 的，化简布尔运算的方法。具体方法如下：

将所有输出为 1 的行的条件相加（即，“或”起来）；
使用布尔运算法则 Laws of Boolean Algebra 化简为不带括号的写法中变量总数最少的写法。

举个例子：

A	B	Output
0	0	1
0	1	1
1	0	0
1	1	0

第一步，把所有 Output 为 1 的行提取出来，得到

第二步，从第一步得到的式子中化简，得到最简形式

“万物皆数”

在计算机内，所有的信息都以二进制数的形式存在。众所周知，二进制数的一位只能是0或1，这样的一位被称为 1 bit，除此之外，以下为我们常用的存储空间单位：

1 nibble: 4 bit
1 byte 字节: 8 bit
1 word: 32 bit
1 KB：1000 bit
1 KiB： bit
1 MB： bit
1 MiB： bit

有时候，我们并不显式区分 KB 和 KiB、MB 和 MiB，毕竟二者差距不大。

整数表示法

对于无符号整数，我们会把它们直接转换为二进制来存储；那对于有符号整数呢？我们应该如何表示它们？

在最早的时候，我们使用的方法叫做 Sign-magnitude：二进制首位为符号位（0为正，1为负），其余位数均为数字位。但是这种方法计算起来非常麻烦，典型的问题就是有 2 个不同的零的表示方法，以及正数和负数的加法没有方便且优雅的实现方法，于是我们放弃了这个方法。

后来，出现了反码表示法 One’s-complement representation：二进制首位为符号位（0为正，1为负），其余位数均为数字位；但是负数的数字位需要逐位地取反（这将是为什么它被称为反码）。这种方法部分解决了计算麻烦的问题，但是还是有 2 个不同的零的表示方法，计算也不够优雅，所以还是被淘汰了。

在现代计算机中普遍使用的方法叫做补码表示法 Two’s-complement representation：二进制首位为符号位（0为正，1为负），其余位数均为数字位；但是负数的数字位需要逐位地取反，然后加一。这个加一的步骤虽然看上去简单，但是其背后是有数学逻辑在的：从 One’s-complement representation 思考，我们不难发现其存在按数字直接相加时存在 A + (-A) = 0 - 1 的性质（不考虑溢出的进退位），故调整负数的表示方法上加1，以符合 A + (-A) = 0 的性质。这样一来，零的表示也唯一了，正负数直接数值加和即可得到正确的计算结果（忽略溢出的情况）。

接下来我们考虑加法溢出 Overflow 的情况：首先，正负数相加，结果的绝对值一定小于其中任何一个加数的绝对值，因此不可能出现溢出；对于两个正数/两个负数相加的情况，我们只需要校验符号位（即最高位）是否发生变化即可：一旦最高位发生变化，则说明出现了溢出（毕竟两个正数不会加出来一个负数）。

当发现了溢出的情况，或者将两个不同二进制位数的数相加时，我们需要进行符号拓展：与无符号拓展直接补高位零不同，符号拓展是复制当前最高位填充高位：

例：4-bit 3 为 0011，拓展为 8-bit 3 为 0000 0011

例：4-bit -3 为 1101，拓展为 8-bit -3 为 1111 1101

小数表示法

对于二进制小数，我们可以将表示法粗浅地分类为定点数 Fixed-point numbers 和浮点数 Floating-point numbers 两类。

定点数 Fixed-point numbers

定点数，即小数点位置固定的数。和十进制小数一致，我们采用 P.Q 的形式表示小数点前 P 位，小数点后 Q 位的小数。例如：

在 4.4 定点数表示中，0010.1010 的十进制为，即 2.625

这种表示方法的加减法相对方便，乘除法需要小数点移位（这会导致定点数表示法发生变化，或者牺牲精度），但是很难在同一套定点数表示法（如6.10）中同时表示较大的数和较高精度的数。因此，这种表示法常常应用于定制化系统中，因为这里小数的数量级和精度不会经常发生变化。

浮点数 Floating-point numbers

对于我们常用的精度、数量级都会发生变化的场合，我们应该使用浮点数。类比一下，如果你需要把 1145140000 和 0.000114514 以一种统一的格式写在很小的答题框里，你会使用科学计数法：和。受到科学计数法的启发，计算机学家发明了浮点数。接下来我们介绍的浮点数以 FP32 为例，基于 IEEE 754 standard 规定的标准：

1	1位符号位 Sign + 8位指数位 Exponent + 23位尾数 Mantissa

其中，符号位0正1负；指数位为无符号整数，带 -127 的偏置 bias，即表示范围为，而0000 0000(E = -127) 或 1111 1111(E = 128) 是特殊规则处理的；尾数是指小数点后第一位开始数的数，省略了小数点前的1。也就是说，有：

实际符号为
实际指数为
实际小数位为
实际数值为

对于正常的浮点数和十进制数互化，我们各举一例：

32-bit 单精度浮点数 0 0111 1011 110 0000 0000 0000 0000 0000 转换为十进制

符号位为 0, 表示正数，

指数位为 0111 1011，表示

尾数为 110 0000 0000 0000 0000 0000, 表示小数位 $M = (1.110 0000 0000 0000 0000 0000)2 = (1.75){10}$

故原数为

0.09375 转换为32-bit单精度浮点数

0.09375 是正数，故符号位 Sign 为 0

0.09375 转换为二进制为（每步取小数部分乘2，依次取首位为小数点后第1,2,3,4,5位）

转换为二进制科学计数法表示：

确定偏移后指数位 Exponent：

确定去掉小数点前的1后的尾数：Mantissa = 100 0000 0000 0000 0000 0000 （末尾补0）

故浮点数表示为 0 0111 1011 100 0000 0000 0000 0000 0000

接下来是一些特殊表示规则：

特殊规则：0

规定的表达为：0/1 0000 0000 000 0000 0000 0000 0000 0000
符号位 S 表示正(0)负(1)
指数位 Exponent 为 0000 0000
尾数 Mantissa 为 000 0000 0000 0000 0000 0000

特殊规则：

拓展绝对值极大的数域
规定的表达为：0/1 1111 1111 000 0000 0000 0000 0000 0000
符号位 Sign 表示正(0)负(1)
指数位 Exponent 为 1111 1111
尾数 Mantissa 为 000 0000 0000 0000 0000 0000

特殊规则：非规格化数 Denorm / Subnormal

拓展绝对值极小的数域
符号位 Sign 表示正(0)负(1)
规定指数位 Exponent 为 0000 0000，而尾数 Mantissa 不全为 0
默认指数 E 表示 -126，小数位 M = 0.Mantissa 而不再添加首位 1
可拓展表示出和数域的数

非数字：NaN (Not a Number)

指数位 Exponent 为 1111 1111 , 而尾数 Mantissa 不全为 0
由 NaN 计算而来（这被称为quiet invalid operations），或由非法运算计算而来（, for , , ）

浮点数计算

浮点数计算的方式非常直观，具体流程如下：

加法

对齐移位 Preshift / Alignment shift：调整较小的数，使加数的指数相等
小数位相加 Add the significands：小数位 M 直接相加，但可能存在未规格化的小数位 M（即不是 1.*** 形式的小数位）
归一化移位 Normalization shift/postshift：把结果做规格化（即变为 1.*** 的形式）
舍入 Round：结果超过精度（超过23位）的尾数
如果舍入造成了未归一化，继续归一化后再重新舍入（最多再执行一次，必定归一化）

乘法

还原真实指数，并计算新的指数，加偏移再转换为 E（考虑偏置bias -127)
小数位相乘，可能存在未规格化的小数位 M
归一化移位
舍入
如果舍入造成了未归一化，继续归一化后再重新舍入（最多再执行一次，必定归一化）
计算符号位

对于舍入步骤，我们默认采用四舍六入五成双规则，但是也存在上取整、下取整、向0取整、四舍五入等其它取整方式。

至此，我们已经学会了前置的数学知识以及主流的底层数字存储格式。在接下来的课节中，我们将正式进入计算机体系结构的世界，从顶层的程序设计语言讲到最底层的二进制以及硬件结构。

回到目录

aaaaa online