CSAPP阅读笔记第二章

CSAPP阅读笔记第二章——信息的表示和处理

前述：

我们研究三种最重要的数字表示——无符号数编码基于传统的二进制表示法，表示大于或者等于0的数字。补码编码是表示有符号整数的最常见的方式，有符号整数就是可以为正或者为负的数字。浮点数编码是表示实数的科学计数法以2为基数的版本。

整数的表示虽然只能编码一个相对较小的数值范围，但是这种表示方式是精确的，而浮点数虽然可以编码一个较大的数值范围，但是这种表示只是近似的。

信息存储：

计算机程序将内存视为一个非常大的字节数组，称为虚拟内存。内存的每个字节都由一个唯一的数字来标识，称为它的地址。所有可能的地址的集合就称为虚拟地址空间。

进制之间的转换

二进制转十六进制（分组转换）

十进制转十六进制 （辗转相除法）

十六进制转十进制

字数据大小

字长：指明指针数据的标称大小

对于一个字长为w的位的机器来说，虚拟地址为 0~（2的w次方-1），程序最多访问2的w次方个字节。

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

98f038a8297af3d7840dbbb39f382a18

当程序prog.c使用如下伪指令编译

linux> gcc -m32 prog.c

该程序就可以在64或者32位机器上正确运行

而如果是使用linux> gcc -m64 prog.c

那就只能在64位机器上运行

因此，我们将程序称为32位程序或64位程序时，区别在于该程序是如何编译的，而不是其运行的机器类型

c语言标准对不同数据类型的数字范围设置了下界，但却没有上界。

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

寻址和字节顺序

两种字节存储法：

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

    小位置上的数字在小地址，我们看到的图就会倒过来

  • 大端法：数字的高位在前

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

例如：十六进制数字0x01234567

大端法

地址 0x100 0x101 0x102 0x103
数据 01 23 45 67

小端法

地址 0x100 0x101 0x102 0x103
数据 67 45 23 01

许多比较新的微处理器是双端法，就是说可以把他们配置成作为大端或者小端的机器运行，然而，实际情况是：一旦选择了操作系统，那么字节顺序也就固定下来。比如，用于许多移动电话的ARM微处理器，其硬件可以按小端或大端两种模式操作，但是这些芯片上最常见的两种操作系统——Android（来自Google）和IOS（来自Apple），却只能运行于小端模式。

布尔代数

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

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

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

C 语言中的位级运算

| 或 &与 ~非

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

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

C 语言中的逻辑运算

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

C 语言中的移位运算

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

右移分为逻辑右移和算术右移。

逻辑右移左端补 0，算术右移（有符号数）左端补最高有效位的值。

C++和C都支持有符号（默认）和无符号数

Java只支持有符号数。

整数数据类型

在 64 位系统上

  • int：4字节，可表示十进制数字位数：10位（-20~20亿以内）
  • long long：8字节，可表示十进制数字位数：19位（千亿亿级）
  • long：8字节
  • double：8字节，精度15位，可表示十进制数字位数308位
  • float：4字节，精度6位，可表示十进制数字38位
  • char：**-128~127**

java 只支持有符号数。

无符号数的编码

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

补码编码

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

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

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

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

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

补码 x 转无符号数

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

无符号数 x 转补码

  • x < 2^(w-1)，值不变
  • x >= 2^(w-1)，转换后的值为 x - 2^w

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

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

扩展一个数字的位表示

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

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

截断数字

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

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

整数运算

无符号加法

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

当 x+y >= 2^w，实际结果为 s = x+y-2^w

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

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

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

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

补码加法

当 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 是负溢出

补码的非

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

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

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

无符号乘法

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

补码乘法

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

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

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

乘以常数

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

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

左移 k 位等于乘以 2^k

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

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

除以 2 的幂

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

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

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

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

代码实现

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

​

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

浮点数

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

二进制小数

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

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

IEEE 浮点表示

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

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

在对浮点数的位编码时：

  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 的范围是 -67；单精度为 -126127
    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

  7. 数字示例

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

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

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

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

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

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

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

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

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

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

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

  20. 浮点运算

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

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

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

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

  25. C 语言中的浮点数

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

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

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

  29. 要小心地使用浮点运算。

#CSAPP笔记
CSAPP阅读笔记第二章
http://example.com/2024/07/13/CSAPP阅读笔记第二章/
作者
John Doe
发布于
2024年7月13日
许可协议