# CSAPP 第二章 信息的表示和处理

第二章 信息的表示和处理

计算机使用二值信号存储和表示信息

当计算结果太大以至于不能表示时，就会产生溢出。

浮点数表示的精度有限，因而浮点运算是不可结合的。

整数的表示范围小但是精确，浮点数表示的范围大但是是近似的。

许多安全漏洞是由算术运算的微妙细节导致的。

# 2.1 信息存储

计算机一般使用字节作为最小的可寻址的内存单位。

在机器级程序中不包含关于数据类型的信息。

指针的值是某个存储块的第一个字节的虚拟地址。

每个程序对象可以视为一个字节块。

# 2.1.1 十六进制表示法

十六进制以 0x 开头。

A：10；C:12；F：15

# 2.1.2 字数据大小

每个计算机有对应的字长，虚拟地址用一个字来编码，所以字长决定了虚拟地址空间的大小。64 位机器的指针类型长度为 8 字节

32位机器的虚拟地址空间为 4GB，64 位字长的虚拟地址空间位 16 EB。

int32_t 和 int64_t 类型分别为 4 字节和 8 字节，不受机器影响。使用确定大小的整数类型很有用。

对 32 位和 64 位机器而言，char、short、int、long long 长度都是一样的，为 1，2，4，8。long 的长度不一样。

float 和 double 的长度一样，分别为 4，8

程序对 char 有无符号一般不敏感。

# 2.1.3 寻址和字节顺序

对于跨越多字节的对象，它的地址是它所用字节中的最小地址。

两种字节存储法：

小端法：数字的低位在前（前就是最小地址）

大端法：数字的高位在前

大多数 Intel 都是小端法，不是所有。

# 2.1.4 表示字符串

C 语言字符串是以 null 字符结尾的字符数组，即 '\0'

ASCII 字符适合编码英文文档。

Unicode（UTF-8）使用 4 字节表示字符，一些常用的字符只需要 1 或 2 个字节。所有 ASCII 字符在 UTF-8 中是一样的。

JAVA 使用 UTF-8 来编码字符串。

# 2.1.5 表示代码

二进制代码是不兼容的，一般无法在不同机器间移植。

从机器的角度看，程序就是一个字节序列。

# 2.1.6 布尔代数

布尔代数是在 0 和 1 基础上的定义

可以把字节看作是一个长为 8 的位向量。

位向量的一个应用是表示有限集合。如位向量 [0110 1001] 表示集合 A = {0,3,5,6}。

# 2.1.7 C 语言中的位级运算

位运算的常见应用是实现掩码。掩码表示从一个字中选出的位的集合，如掩码 0xFF 表示一个字的低 8 位。

表达式 ~0 可以生成一个全 1 的掩码，不管机器的字大小是多少。

# 2.1.8 C 语言中的逻辑运算

逻辑运算符 && 和 || 如果第一个参数就能确定结果，就不再计算第二个参数

# 2.1.9 C 语言中的移位运算

左移 k 位丢掉最高的 k 位，并在右端补 k 个 0。

右移分为逻辑右移和算术右移。逻辑右移左端补 0，算术右移左端补最高有效位的值。

一般都对有符号数使用算术右移，即补符号位的值。无符号数，只能是逻辑右移，即补 0

# 2.2 整数表示

无符号表示与补码表示

有符号数到无符号数的转换会产生漏洞，避免错误的方法之一是绝不使用无符号数。

除了 C 以外很少有语言支持无符号整数，Java 就只支持有符号数

# 2.2.1 整数数据类型

在 64 位系统上

int：4字节，可表示十进制数字位数：10位（-20~20亿以内）

long long：8字节，可表示十进制数字位数：19位（千亿亿级）

long：8字节

double：8字节，精度15位，可表示十进制数字位数308位

float：4字节，精度6位，可表示十进制数字38位

char： -128~127

java 只支持有符号数。

# 2.2.2 无符号数的编码

无符号表示、补码表示与数据的映射都是双射，即一一对应。

# 2.2.3 补码编码

补码的定义实际就是将符号位解释为负权。

C 库头文件 <limit.h> 定义了一组常量来限定不同整数数据类型的取值范围。INT_MAX、INT_MIN、UINT_MAX

C 库头文件 <stdint.h> 中定义了 uint16_t, int32_t 等类型，用于声明确定宽度类型的整数。

# 2.2.4 有符号数和无符号数之间的转换

在有符号数与无符号数之间进行强制类型转换的结果是保持位值不变，只改变解释位的方式。

补码 x 转无符号数

$x \ge 0$，值不变

$x < 0$，转换后的值为 $2^w + x$

无符号数 x 转补码

$x < 2^{w-1}$，值不变

$x \ge 2^{w-1}$，转换后的值为 $x - 2^w$

# 2.2.5 C 语言中的有符号数和无符号数

C 语言中有符号数和无符号数相加减，有符号被转换成无符号。

# 2.2.6 扩展一个数字的位表示

扩展无符号数使用零扩展，即在最高位前加 0

扩展有符号数使用符号扩展，即在最高位前加最高有效位的值

# 2.2.7 截断数字

对一个 w 位的数字截断为一个 k 位数字，将丢弃高 w-k 位。

对于无符号数而言，截断后的数字实际上等于 w mod 2^k，即取余。

# 2.3 整数运算

# 2.3.1 无符号加法

考虑溢出，C 语言不会将溢出作为错误发出信号

当 $x+y \ge 2^w$ 时，实际结果为 $s = x+y-2^w$

对任意的 $x+y$，有 $s = (x+y) \bmod 2^w$

溢出的结果： 和小于两个加数

检验溢出的方式： 如果 $s<x$，说明溢出

无符号数的非： $x \mapsto 2^w - x \ (x>0)$

# 2.3.2 补码加法

当 $x+y \ge 2^{w-1}$ 时，$s = x+y-2^w$

当 $x+y < -2^{w-1}$ 时，$s = x+y+2^w$

正溢出的结果是负数，负溢出的结果是正数。

检验溢出的方式： 当 $x,y>0$ 而 $s\le 0$ 时是正溢出；当 $x,y<0$ 而 $s\ge 0$ 时是负溢出

# 2.3.3 补码的非

当 x = TMin，-x = TMin；当 x ≠ TMin，-x = -x

补码非的位级表示：对每一位求补，结果再加 1

计算补码非的第二种方法： 假设 k 是最右边的 1 的位置，对 k 左边的所有位取反

# 2.3.4 无符号乘法

无符号乘法的积 m = (x*y) % 2^w

# 2.3.5 补码乘法

可以认为补码乘法和无符号乘法的位级表示是一样的

C语言在运算时将 x,y 视为无符号数进行乘法运算，结果取余后将其按补码方式解释

补码乘法的积 m = (x*y) % 2^w

# 2.3.6 乘以常数

大多数机器上，整数乘法需要 10 个或更多的时钟周期，而加法、减法、位级运算和移位只需要 1 个时钟周期

编译器对整数乘法进行优化的方式：用移位和加法或减法运算的组合来代替常数因子的乘法。

左移 k 位等于乘以 2^k

如 x * 14 = (x<<3)+(x<<2)+(x<<1) = (x<<4)-(x<<2)

判断如何移动的方式很简单：14 的位级表示为 1110，所以分别左移 3，2，1

# 2.3.7 除以 2 的幂

大多数机器上，整数除法更慢，需要 30 个或更多的始终周期。

（只有）除以 2 的幂可以用移位运算来代替，无符号采用逻辑右移，补码采用算术右移

对于有符号数而言，算术右移的结果相当于进行除法运算后向下舍入

使用 (x+(1<<k)-1)>>k 的结果相当于进行除法运算然后向零舍入

代码实现

(x<0 ? x+(1<<k)-1 : x) >> k;

# 2.3.8 关于整数运算的最后思考

补码使用了与无符号算术运算相同的位级实现，包括加法、减法、乘法甚至除法。都有完全一样或非常类似的位级行为。

# 2.4 浮点数

浮点数对于非常大，非常接近零，近似值计算都很有用

# 2.4.1 二进制小数

小数的二进制表示法只能表示那些能够写为 $x \times 2^w$ 的数，其他的数都是近似表示。 $x$ 必须可以由形如 $2^i + 2^j + \dots + 2^n$ 的多项式表示。

浮点运算的不精确性可能产生严重后果

# 2.4.2 IEEE 浮点表示

IEEE 浮点标准的表示形式为：$V = (-1)^S \times M \times 2^E$，它分为三部分：

符号：S 决定是负数还是正数

阶码：E 的作用是对浮点数加权

尾数：M 是一个二进制小数。规格化值时范围是 $1 \le M < 2$，非规格化值时范围是 $0 \le M < 1$

在对浮点数的位编码时：

一个单独的符号位编码直接编码 S

k 位的阶码字段 e 编码 E；float 中 k=8，double 中** k=11**

n 位的小数字段 f 编码 M；float 中 n=23，double 中** n=52**

E 和 M 的编码方式分为三种情况：

规格化的值： 阶码字段即不全为 0 也不全为 1 时属于规格化值（0001~1110）

阶码字段解释方式：$E = e - (2^{k-1}-1)$；如 $k=4$ 时，$E$ 的范围是 $-6$ 到 $7$；单精度为 $-126$ 到 $127$

小数字段解释方式：M = 1 + f

非规格化的值：阶码字段全为 0 时属于非规格化形式

阶码字段解释方式：E = 1 - (2^(k-1)-1) ；与规格化值中 e = 1 时的 E 相同

小数字段解释方式：M = f

特殊值： 阶码字段全为 1 时，分两种情况：

小数字段全为 0：表示无穷

小数字段非零：表示 NaN。 比如 ∞-∞ 的结果就返回 NaN

# 2.4.3 数字示例

0 有 +0.0 和 -0.0 两种表示方式

最大非规格化数到最小规格化数的过渡是平滑的。

浮点数能够使用正数排序函数来排序，即浮点数的位级表示当用整数方式来解释时是顺序的（正数升序负数降序）。

# 问题 2.1

1. 十六进制中 A,C,F 分别是多少。
2. 如何定义有确定字长的整数，在哪个头文件中
3. 计算机的字长是什么？字长决定了什么？
4. short, int, long long 长度分别是多少，long 长度是多少
5. 一个 int 对象的地址是它所占哪个字节的地址
6. 多字节类型的小端法和大端法分别是什么，一般计算机是哪种方法
7. ASCII 和 Unicode 分别应用于哪些情况？两者的关系是什么
8. 掩码是什么？如何生成全 1 的数字
9. 什么是逻辑右移和算术右移，有符号数用哪个？无符号数用哪个
10. int, long long, char，short 可表示的范围分别是多少
11. float, double 的精度和可表示范围分别是多少
12. 补码如何解释位
13. 有符号数和无符号数的强制类型转换是如何转换的
14. 有符号转无符号数值如何变化？无符号转有符号数值如何变化？
15. 如何扩展有符号数？如何扩展无符号数？
16. 截断一个无符号数从数学运算上如何理解？

# 回答2.1

1. A 是 10，C 是 12，F 是 15
2. 使用 int32_t, int64_t, uint32_t, uint64_t。定义在头文件 <stdint.h> 中
3. 分别是 2，4，8 位，long 在 32 位程序中是 4 位，在 64 位机器中是 8位
4. 32 位计算机的字长是 32 位，64 位计算机的字长是 64 位，字长w决定了虚拟空间的大小：<= 2^w。
5. 最小字节的地址
6. 小端法将低位表示在低字节，大端法将高位表示在低字节。大部分是小端法。
7. ASCII 用于英文文档，UTF-8 用于多语言，所有的 ASCII 字符在 UTF-8 中是一样的
8. 掩码用来筛选一个数字的某几位，~0 的结果是全 1
9. 逻辑右移左边补 0，算术右移左端补符号位，有符号数用算术右移，无符号数用逻辑右移
10. int 大约是 10 位十进制精度（约 $-20$ 亿到 $20$ 亿）；long long 大约是 19 位；char 为 $-128$ 到 $127$；short 为 $-32768$ 到 $32767$
11. 6位，10 的 38 次方以内；15位，10 的 308 次方以内；
12. 最高位解释为负权
13. 位值不变，改变解释的方式
14. 若 $x<0$，则 $u_x = x + 2^w$；若无符号数 $u_x \ge 2^{w-1}$，则 $x = u_x - 2^w$
15. 左端填充为符号位；左端填充为 0
16. 对 2^k 取模

# 问题 2.2

1. 考虑溢出，无符号加法的计算公式，无符号乘法的计算公式？如何检验溢出？
2. 考虑溢出，补码加法的计算公式，补码加法溢出的特点是什么？如何检验溢出？
3. 考虑溢出，补码乘法的计算方法
4. 补码的非怎么求？
5. 整数乘法的计算速度？整数乘法的优化方式？如何判断移动的方式？
6. 整数除法的计算速度？除以 2 的幂的优化方式？
7. 整数补码运算与无符号运算的关系
8. 浮点数表示法的限制
9. 浮点数位级表示的三个部分？double 分别有多少位？
10. 阶码和尾数的三种编码方式分别是什么？
11. 最小的正非规格化值、最大的非规格化值、最小的正规格化值、最大的规格化值的位级表示分别是怎样的？
12. 什么是向偶数舍入？浮点数的近似匹配采用哪种舍入方式？有什么优点
13. 浮点运算满足什么运算性质？不满足什么性质？
14. 从 float 或 double 转换到 int 可能会发生什么情况？

# 回答2，2

1. s=(x+y)%2^w；m=(x*y)%2^w；检验加法溢出：s<x 或 s<y
2. 分三种情况，不溢出，正溢出，负溢出；特点：正溢出的结果是负数，负溢出的结果是正数；检验溢出：结果变号了就是溢出了
3. 将两个乘数当成无符号数进行乘法计算，截断溢出的部分后，将剩余部分用补码方式解释
4. 按位求反再加一
5. 大于等于 10 个时钟周期；用移位+加法/减法优化；根据移位程度 k 的位级表示来判断
6. 大于等于 30 个时钟周期；逻辑右移或算术右移；算术右移的结果是向下舍入，可以调整为向零舍入
7. 在位级表示上完全相同或非常相似
8. 只能表示 x * 2^y 类的数，其他数字只能近似表示
9. 符号、阶码、尾数；1，11位，52位
10. 规格化值：阶码非全 0 且非全 1，指数偏移量为 $2^{k-1}-1$，尾数为 $1+f$；非规格化值：阶码全 0，$E = 1-(2^{k-1}-1)$，尾数为 $f$；特殊值：阶码全 1，尾数全 0 表示无穷，尾数非全 0 表示 NaN
11. 末位为1，其他为0；尾数全1，其他全0；阶码末位为1，其他全0；阶码末位和符号位为0，其他全1；
12. 非中间值向近舍入，中间值向偶数舍入；采用向偶数舍入；优点是统计结果不偏差
13. 满足交换性和单调性，不满足结合性和分配性
14. 可能溢出和舍入；如果溢出，转换结果都是 100000，是一个负数。