Chapter 1: Number System 进制和数的表示

（共 70 页）

进制 Number System

基数（base / radix） 是指这个 number system 当中有多少种不同的数位，与集合当中的基数（cardinality）概念类似。所以十进制当中，基数就是 10。

十进制 Decimal
八进制 Octal
十六进制 Hexadecimal
二进制 Binary：计算机电路是由 双稳态晶体管元器件（bistable transistor） 构成的，所以计算机使用二进制表示数据。

二进制

least significant bit (LSB)，最低位，最右边的
most significant bit (MSB)，最高位，最左边的

二进制加减乘除

加法：列竖式直接计算，不管有没有小数点，标注好进位，可以转换成十进制进行验算。
减法：还是列竖式，标注好借位。
乘法：依然是列竖式，像十进制乘法竖式一样。如果有小数点，就先忽略，最后点上去。
除法：还是列竖式。

感觉用十进制验算比较简单。

小数的二进制转换

小数

例如，$(14.625)_{10}$，拆成整数和小数两部分考虑，即 $14$ 和 $0.625$。

整数部分直接口算得到 $(14)_{10} = (1110)_2$

小数部分，与短除法相反。这里不停的乘以 $2$，每次乘法之后取出并依次（从左往右）写下整数位。重复这个过程，直到小数部分变成 $0$。

即：$0.625 \rightarrow \textbf{1}.25$，$0.25\rightarrow \textbf{0}.5$，$0.5 \rightarrow \textbf{1}.0$。

故 $(14.625)_{10} = (1110.101)_2$。

这个例子并不太好，因为小数部分回文了。如果是 $(0.6875)_{10} = (0.1011)_2$，这个例子能体现出整数位被写下的顺序（依次）。

小数部分，从左到右，分别是 $2^{-1}$，$2^{-2}$，$2^{-3}$，以此类推

浮点数表示方法

根据 IEEE 754 的标准，浮点数存储分为三部分：符号位（sign）、指数位（exponent）、分数位（fraction/mantissa）。

精度	符号位	指数位	分数位
32 位	1	8	23
64 位	1	11	52

CS161 课程中的 IEEE 754 相关笔记附在下方：

IEEE 754

可以参考：
https://www.zhihu.com/question/46432979/answer/221485161
https://zh.wikipedia.org/wiki/IEEE_754
https://bartaz.github.io/ieee754-visualization/

在计算机中，根据 IEEE 754 标准，所有浮点数都存储为 $\text{1.xx} \times \text{2}^{\text{yy}} \times \text{±1}$ 的形式

类型	符号位 sign	指数位 exponent	分数位 fraction	固定偏移值 bias
float	1	8	23	127
double	1	11	52	1023

指数偏移值

IEEE 754 规定，设二进制浮点数的指数部分长度为 $e$，则 指数偏移值 的固定值是$2^{e-1}-1$。（一般，指数部分译作阶码。）因为指数部分取值实际上是 -126~127，-127 和 128 是特殊值。若指数实际值为 17，则存储为 144。

同时，采用指数的实际值加上固定的偏移值的办法表示浮点数的指数，还可以带来好处，如直接 使用字典序 比较浮点数大小：正数一定大于负数，无穷大于所有数，非数不能比较大小；除此之外，则可 按指数域和尾数域的字典序比较。

规约形式

规约，指用唯一确定的浮点形式去表示一个值。

若指数部分的编码值在 $[1, 2^e-2]$ 之间（00000000001 到 11111111110），且分数部分的最高有效位是 1（000…000 到 111…111（52 位）），则这个浮点数是规约形式的。

最小的规约数是 * - 0000 0001 - 000 0000 0000 0000 0000 0000
最大的规约数是 * - 1111 1110 - 111 1111 1111 1111 1111 1111

非规约形式

如果浮点数的指数部分的编码值是 0，分数部分非零，那么这个浮点数将被称为非规约形式的浮点数。

一般是某个数字 相当接近零时 才会使用非规约型式来表示。所有的非规约浮点数比规约浮点数更接近 0。

IEEE 754 规定，非规约形式的浮点数的指数偏移值比规约形式的浮点数的指数偏移值小 1。 举例来说，对于 float 类型，规约形式偏移值是 127，而非规约的偏移值是 126。

规约浮点数的尾数大于等于 1 且小于 2，而非规约浮点数的尾数小于 1 且大于 0（规约数的尾数是有隐含 1 的，而非规约数则没有）。

最小的非规约数是 * - 0000 0000 - 000 0000 0000 0000 0000 0001
中间大小非规约数 * - 0000 0000 - 100 0000 0000 0000 0000 0000
最大的非规约数是 * - 0000 0000 - 111 1111 1111 1111 1111 1111

总结

形式	指数部分	小数部分
正负零	0	0
非规约	0	大于 0 小于 1
规约	$[1, 2^e - 2]$	大于等于 1 小于 2
正负无穷	$2^e-1$	0
NaN	$2^e -1$	非零

精度

IEEE 规定中的小数部分实际上省略了小数点前面的 1，所以实际上 float 与 double 分别是 24、53 位。

float：$\lg{2^{23+1}} = 7.22$，7 位
double：$\lg{2^{52+1}} = 15.95$，15 位

浮点截断

IEEE 754 列出了四种方法，但默认情况下，舍入到最接近，偶数优先，意思是会将结果舍入为最接近且可以表示的值，但是当存在两个数一样接近的时候，则取其中的偶数（在二进制中是以 0 结尾的）。

四舍六入五成双

要求保留位数的后一位如果是 4，则舍去。例如 5.214 保留两位小数为 5.21。
如果保留位数的后一位如果是 6，则进上去。例如 5.216 保留两位小数为 5.22。
如果保留位数的后一位如果是 5，而且 5 后面不再有数，要根据应看尾数 “5” 的前一位决定是舍去还是进入：如果是奇数则进入，如果是偶数则舍去。例如 5.215 保留两位小数为 5.22； 5.225 保留两位小数为 5.22。
如果保留位数的后一位如果是 5，而且 5 后面仍有数。例如 5.2254 保留两位小数为 5.23，也就是说如果 5 后面还有数据，则无论奇偶都要进入。

特例：

对于这一段代码，5.225 和 2.225 的保留两位小数输出结果并不相同。

这是因为，根据 IEEE 754 标准，$5.225$ 和 $2.225$ 分别记作 $4 \times 1.30625$ 和 $2 \times 1.1125$，而 0.30625 和 0.1125 表示成二进制都是无限不循环小数，所以会出现浮点截断。截断后，分别是 5.22499999999999964 和 2.22500000000000008。此时再根据四舍六入五成双的规则，得到 5.22，2.23。

计算示例

例一、用 double 存储 78.375：

首先把 78.375 转化为二进制表示，得到 1001110.011，即 $1.001110011 \times 2^6$
那么，符号位是 0，小数位是 001110011 0000000…
6 加上固定偏移量 1023 是 1029，用二进制表示是 10000000101，这是指数位
所以合起来是，0 - 10000000101 - 001110011 - 00000…

例二、求 float 数据 0 10000010 01000100000000000000000 的十进制形式

正数
指数部分是 130，减去固定偏移值 127 得到实际偏移值 3
尾数部分是 1.010001，十进制表示为 1.265625，综合前面步骤得到 $1.265625 \times 2^3 = 10.125$

更多示例，在 L18.pptx

整数的表示

$n$ 位无符号整数，表示范围通常是 $\left[0, 2^n - 1 \right]$
$n$ 位有符号整数，表示范围通常是 $\left[-2^{n-1}, 2^{n-1}-1 \right]$

在计算机中，如果是有符号整数，通常用最高位表示符号，0 代表非负，1 代表负，剩下的 $n-1$ 位表示绝对值。

原码补码反码

原码，sign-magnitude
反码，1's complement，就是原码除了符号位，每一位都 flip 一下
补码，2's complement，就是反码的基础上，最低位 + 1

BCD（Binary Coded Decimal）码

就是把每一位十进制数用四位二进制数表示然后拼接起来。比如 12 用 BCD 表示就是，分别表示 1 和 2，即 0001 0010.

有时候 BCD 会省略掉前导零。所以 12 也可以写作 10010。只需要记得前面实际上还有 3 个 0 没写出来就好了。