首页 CSAPP

# CSAPP: 第二章

# 2、信息的表示和处理

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

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

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

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

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

# 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 库头文件 定义了一组常量来限定不同整数数据类型的取值范围。INT_MAX、INT_MIN、UINT_MAX

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

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

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

补码 x 转无符号数

  • x >= 0，值不变
  • x < 0，转换后的值为 2^w + x

无符号数 x 转补码

  • x <2^(w-1)，值不变
  • x >= 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 >= 2^w，实际结果为 s = x+y-2^w

对任意的 x+y，s = (x+y) % 2^w

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

** 检验溢出的方式：** 如果 s，说明溢出

无符号数的非：~x = 2^w - x (x>0)

# 2.3.2 补码加法

当 x+y >= 2^(w-1)， s = x+y-2^w

当 x+y <-2^(w-1)，s = x+y+2^w

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

** 检验溢出的方式：** 当 x,y>0 而 s<=0 是正溢出；当 x,y<0 而 s>=0 是负溢出

# 2.3.3 补码的非

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

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

计算补码非的第二种方法：假设 k 是最右边的位置，对 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 的结果相当于进行除法运算然后向零舍入

代码实现

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

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

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

# 2.4 浮点数

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

# 2.4.1 二进制小数

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

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

# 2.4.2 IEEE 浮点表示

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

  1. 符号：S 决定是负数还是正数
  2. 阶码：E 的作用是对浮点数加权
  3. 尾数：M 是一个二进制小数，范围是 1~2-ε 或 0~1-ε

在对浮点数的位编码时：

  1. 一个单独的符号位编码直接编码 S
  2. k 位的阶码字段 e 编码 E；float 中 k=8，double 中 k=11
  3. n 位的小数字段 f 编码 M；float 中 n=23，double 中 n=52

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

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

    1. 阶码字段解释方式：E = e - (2^(k-1)-1)；如 k=4 时，E 的范围是 -6~7；单精度为 -126~127
    2. 小数字段解释方式：M = 1 + f

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

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

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

    1. 小数字段全为 0：表示无穷
    2. 小数字段非零：表示 NaN。比如 ∞-∞ 的结果就返回 NaN

# 2.4.3 数字示例

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

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

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

浮点数可表示的数的分布是不均匀的，越接近零时越稠密

几个特殊的值的位级表示：

  1. +0.0 全为 0
  2. 最小的正非规格化值：最低有效位为 1，其他为 0
  3. 最大的非规格化值：小数字段全为 1，其他为 0
  4. 最小的正规格化值：阶码字段最低位为 1，其他为 0
  5. 最大的规格化值：阶码字段最低位为 0，符号位为 0，其他为 1

# 2.4.4 舍入

因为范围和精度有限，浮点运算只能近似表示实数运算。

在浮点数的近似匹配上，IEEE 浮点格式定义了四种舍入方式（默认第一种）：

  1. 向偶数舍入（向最接近的值舍入）：非中间值 (0.5) 四舍五入，中间值向偶数舍入。
  2. 向零舍入
  3. 向下舍入
  4. 向上舍入

向偶数舍入可以计算一组数的平均数时避免统计偏差。

实际上这种舍入是发生在二进制小数上的。

# 2.4.5 浮点运算

IEEE 标准定义 1/-0 = -∞，1/+0 = +∞

浮点运算是可交换不可结合也不可分配的。

浮点加法满足加法和乘法上的单调性。如果 a>=b，则 x+a >= x+b

缺乏结合性和分配性会使一些简单问题变得很复杂

# 2.4.6 C 语言中的浮点数

在 int、float、double 间进行强制类型转换时的几种情况：

  1. int 到 float：不会溢出，可能舍入
  2. int 或 float 到 double：不会溢出也不会舍入
  3. double 到 float：可能溢出和舍入
  4. float 或 double 到 int：向零舍入，很大时可能溢出，很接近零时也可能溢出。当从浮点转换到整数时如果溢出，转变结果都为 [1000]，因此一个正浮点可能得到一个负整数

把大的浮点数转换为整数是一种常见的错误。

要小心地使用浮点运算。