CSAPP Lecture 02

Niebelungen 收录于类别 Pwning

2021-01-20 2021-01-20 约 2665 字预计阅读 6 分钟

Lecture 02: Floating point

浮点数

二进制小数

与整数一样，个位代表$2^0$,那么小数点后的k位数就是$2^{-k}$。

对于$0.111…111_2$这样刚好小于1的数，使用简单的$1.0-\varepsilon$。

但是对于$\frac{1}{3}$这样的数就不能表示，只能近似。

IEEE浮点表示

IEEE浮点标准用$V=(-1)^s×M×2^E$的形式表示一个数：

符号（sign）

s决定这数是负数（s=1）还是正数（s=0）。
尾数（significand）

M是一个二进制小数，它的范围是1~2-$\varepsilon$,或0~1-$\varepsilon$
阶码（exponent）

E的作用是对浮点数加权，这个权重是2的E次幂（可能是负数）

将浮点数的位表示划分为三个字段：

一个单独的符号位s
k位的阶码字段$exp=e_{k-1}e_{k-2}…e_0$编码阶码E
n位小数字段$frac=f_{n-1}f_{n-2}…f_0$,编码尾数M，其真实值与E的编码有关

对于这些字段的位置有精度的划分：

c语言float中，s、exp和frac字段分别为1位、k=8位和23位，共32位。

c语言double中，s、exp和frac字段分别为1位、k=11位和52位，共64位。

单精度的格式也分为几种情况：

规格化的

s（31）	exp（30：23）	frac（22：0）
0或1	≠0&≠255	~

这种情况阶码的值是E=e-Bias，其中e是无符号数，其位表示为$e_{k-1}e_{k-2}…e_0$，而Bias是一个等于$2^{k-1}-1$的偏置值。

f的位表示为$0.f_{n-1}f_{n-2}…f_0$，尾数的定义为M=1+f。即在规格化的格式中无法表示0这个数，那么既然不能表示，1也没有必要写在开头变成$1.f_{n-1}f_{n-2}…f_0$，这种就是隐含的以1开头。

非规格化的

s（31）	exp（30：23）	frac（22：0）
0或1	全为0	~

这种情况阶码的值是E=1-Bias，尾数的定义为M=f。这样我们就可以表示0，和非常接近0的数。

特殊的

无穷大：

s（31）	exp（30：23）	frac（22：0）
0或1	全为1	全为0

NaN（not a number）

s（31）	exp（30：23）	frac（22：0）
0或1	全为1	≠0

下面用一个例子来做演示：

6.91，其二进制表示为$110.111010001111010111000_2$

将其规格化，$6.91=(-1)^0×1.10111010001111010111000_2×2^2$

这样三个字段的值就得到了：

s=0

exp=E+Bias=$2+(2^{8-1}-1)$=129(十进制)=$1000 0001_2$

frac=10111010001111010111000

s（31）	exp（30：23）	frac（22：0）
0	10000001	10111010001111010111000

0100	0000	1101	1101	0001	1110	1011	1000
4	0	D	D	1	E	B	8

舍入

methods	1.40	1.60	1.50	2.50	-1.50
向偶数舍入	1	2	2	2	-2
向零舍入	1	1	1	2	-1
向下舍入	1	1	1	2	-2
向上舍入	2	2	2	3	-1

一般采用向偶数舍入，因为在大多数情况下它总是有效的。对于二进制小数，将最低有效位的值0认为是偶数，值1认为是奇数。一般在$0.xxxxx…x100$的情况下这种规则才适用，100为要舍弃的位。

Value	Binary	Rounded	Action	Rounded Value
2 3/32	10.00011	10.00	（<1/2–down）	2
2 3/16	10.00110	10.01	(>1/2–up)	2 1/4
2 7/8	10.11100	11.00	(1/2–up)	3
2 5/8	10.10100	10.10	(1/2–down)	2 1/2

对于上面的例子书上解释为：①与②不可能为两个可能值的中间值，而③和④可能，且我们倾向于使最低有效位为零。

浮点数乘法

浮点数运算无法直接通过在位向量上运算得到。

对于两个浮点数$(-1)^{s_1}×M_1×2^{E_1}$和$(-1)^{s_2}×M_2×2^{E_2}$，计算结果为$(-1)^{s}×M×2^{E}$，其中$s=s_1XORS_2$，$M=M_1×M_2$，$E=E_1+E_2$。

如果 [公式] ，就将frac右移一位，并对E加一。
如果E超过了表示范围，就发生了溢出。
如果M超过了表示范围，对frac进行舍入。

数学性质：

可交换
不可结合：可能出现溢出和不精确的舍入，比如$1e20*(1e201e-20)-1e20$，而$(1e201e20)*1e-20=INF$ 。
不可分配：如果分配了可能会出现NaN，比如$1e20*(1e20-1e20)=0$，而$1e201e20-1e201e20=NaN$ 。
保证，只要$a≠NaN$，则$a*^ta≥0$。

浮点数加法

对于两个浮点数$(-1)^{s_1}×M_1×2^{E_1}$和$(-1)^{s_2}×M_2×2^{E_2}$，计算结果为$(-1)^{s}×M×2^{E}$，其中s，M是对其后的运算结果，$E=max(E_1,E_2)$。

如果$M≥2$，则frac右移一位，并对E加1。
如果$M<1$ ，则frac左移一位，并对E减1。
如果E超过表示范围，就发生溢出。
如果M超过表示范围，就对frac进行舍入。