CSAPP 信息的表示和处理

2018-12-25

2.1 信息存储

2.1.1 十六进制表示法

十六进制转换窍门:记住 A、C 和 F 对应的值,B、D 和 E 可通过计算它们与前三个值的相对关系来完成。

对于 2 的非负整数 n 次幂 x,即 $x = 2^n$,一个转换为十六进制的技巧:x 的二进制形式就是 1 后面跟 n 个 0,把 n 表示成 $i + 4j$,其中 $0 \le i \le 3$,当 i 为 0、1、2、3 时,x 的十六进制开头数字分别为 1、2、4、8,后面跟着 j 个十六进制的 0。如 $2048 = 2 ^ {11}$,有 $n = 11 = 3 + 4 \cdot 2$,从而得到十六进制 0x800。

2.1.2 字数据大小

大多数 64 位机器也可以运行 32 位机器编译的程序,这是一种向后兼容。例如 prog.c 用如下伪指令编译后

$ gcc -m32 prog.c

该程序就可以在 32 位或 64 位机器上正确运行。若用如下伪指令编译

$ gcc -m64 prog.c

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

C 语言的数据类型中,int 即使是为 64 位系统编译,通常也只有 4 个字节,long 一般在 32 位程序中为 4 字节,64 位程序中则为 8 字节。

ISO C99 引入了一类数据类型,其数据长度是固定的,不随编译器和机器设置变化,例如 int32_tint64_t 分别为 4 个字节和 8 个字节。

大多数编译器将 char 类型视为有符号数,但 C 标准不保证这一点,程序员应该用 signed char 来保证它为有符号数值。不过在很多情况下,char 是否有符号并不敏感。

2.1.3 寻址和字节顺序

在几乎所有机器上,多字节对象被存储为连续的字节序列,对象的地址是所使用字节中最小的地址。

  • 小端法:按照从最低有效字节到最高有效字节的顺序存储对象
  • 大端法:按照从最高有效字节到最低有效字节的顺序存储对象

man ascii 可查询 ASCII 字符码表。

2.1.7 C 语言中的位级运算

~0可以生成一个全 1 的掩码,不管机器的字长是多少。

x ^ ~0xff 可以把除最低字节以外的位取反(取补)。

x ^ y 等价于 (x & ~y) | (~x & y)

2.1.9 C 语言中的移位运算

C 语言左移 << 都是逻辑左移,没有算数左移。

逻辑右移是在左端补 0,算数右移是在左端补最高有效位的值。

C 语言标准并没有明确规定对于有符号数应该使用哪种类型的右移,但几乎所有的编译器/机器组合都对有符号数使用算数右移,对于无符号数必定是逻辑右移。

Java 对如何右移有明确定义,>> 是算数右移,>>> 是逻辑右移。

如果移位量 k 大于数据类型的位数 w,即 $k \ge w$,按照 C 标准实际上位移量是 $k\ mod\ w$,但这种行为对于 C 程序来说是没有保证的。而 Java 则保证这一点。

2.2 整数表示

2.2.2 无符号数的编码

$$B2U_w(x) = \sum_{i=0}^{w-1} x_i2^i$$

2.2.3 补码编码

$$B2T_w(x) = -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2} x_i2^i$$

C 语言标准并没有要求使用补码形式来表示有符号整数,但几乎所有机器都是这么做的。

limits.h 定义了不同整型数据类型的取值范围,stdint.h 中定义了不同长度的有符号和无符号整数及其取值范围,inttypes.h 中定义了打印确定宽度类型的所需的宏。

Java 对整数类型的取值范围和表示是非常明确的,它要求采用补码表示。其单字节数据类型为 byte 而不是 char

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

补码转无符号数:

$$T2U_w(x) = \begin{cases} x + 2^w, & x < 0 \\ x, & {x \ge 0} \end{cases} \\ = x + x_{w-1}2^w$$

无符号数转补码:

$$U2T_w(u) = \begin{cases} u, & u \le TMax_w \\ u - 2^w, & u > TMax_w \end{cases} \\ = -u_{w-1}2^w + u$$

2.2.5 C 语言中的有符号数与无符号数

C 语言创建一个无符号常量,必须加上后缀字符 Uu,例如 12345U 或者 0x1A2Bu

C 语言允许无符号数和有符号数之间的转换,C 标准没有精确规定应如何进行这种转换,但大多数系统遵循的原则是底层的位表示保持不变,即应用 $U2T_w$ 和 $T2U_w$。

当用 printf 输出数值时,分别用指示符 %d%u%x 以有符号十进制、无符号十进制和十六进制格式输出一个数字,printf 没有使用任何类型信息。

当执行一个运算时,如果它的一个运算数是有符号的,另一个是无符号的,C 语言会隐式地将有符号数强制转换为无符号数,并假设这两个数都是非负的,来执行这个运算。例如假设 int 表示为 32 位补码,-1 < 0U 等价于 429467295U < 0U,结果为非。

32 位补码表示的 int 最小值 $TMin_{32}$ 通常写成 -2147483647 - 1,而不是 -2147383648 或 0x80000000。limits.h 中是这样定义的:

#define	INT_MAX		2147483647	/* max value for an int */
#define	INT_MIN		(-2147483647-1)	/* min value for an int */

解释可参考 c - Why do we define INT_MIN as -INT_MAX - 1? - Stack Overflow ,简而言之,-2148473648 不是一个 int 常量,而是由一元操作符 - 和常量 2147483648 组合而成,而后者超过了 int 范围,在 32 位系统中是 long long,在 64 位系统中是 long

2.2.6 扩展一个数字的位表示

无符号数的零扩展:将一个无符号数转换为一个较长的数据类型,只要在开头添加 0。

补码数的符号扩展:将一个补码数转换为一个较长的数据类型,在开头添加最高有效位的值。

推导:要证明

$$B2T_{w+k}([x_{w-1}, …, x_{w-1}, x_{w-1}, x_{w-2}, …, x_0]) = B2T_w([x_{w-1}, x_{w-2}, …, x_0])$$

只需证明

$$B2T_{w+1}([x_{w-1}, x_{w-1}, x_{w-2}, …, x_0]) = B2T_w([x_{w-1}, x_{w-2}, …, x_0])$$

将左边展开:

$$ B2T_{w+1}([x_{w-1}, x_{w-1}, x_{w-2}, …, x_0]) \\ = -x_{w-1}2^w + \sum_{i=0}^{w-1}x_i2^i \\ = -x_{w-1}2^w + x_{w-1}2^{w-1} + \sum_{i=0}^{w-2}x_i2^i \\ = -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2}x_i2^i \\ = B2T_w([x_{w-1}, x_{w-2}, …, x_0]) $$

归纳即可证明。

C 语言标准规定,先作位扩展,再作有符号和无符号数之间的转换。例如,把 short 类型的变量 sx 转换为 unsigned 类型,(unsigned) sx 等价于 (unsigned) (int) sx,而不是 (unsigned) (unsigned short) sx

2.2.7 截断数字

将较长类型转换为较短类型,直接去掉高位。

2.3 整数运算

2.3.1 无符号加法

无符号整数 $x$ 和 $y$ 相加,把和 $x + y$ 截断为 $w$ 位得到无符号数结果。

$$x +_w^u y = \begin{cases} x + y, & x + y < 2^w \\ x + y - 2^w, & 2^w \le x + y < 2^{w+1} \end{cases}$$

原理:检测无符号数加法中的溢出:

对在范围 $0 \le x, y \le UMax_w$ 中的 $x$ 和 $y$,令 $s = x +_w^u y$,则当且仅当 $s < x$(或者等价地 $s < y$)时发生了溢出。

推导

  1. $s < x$ 和 $s < y$ 必定同时成立或同时不成立。

  2. 如果 $s < x$(或者等价地 $s < y$),那么显然发生溢出。

  3. 如果发生了溢出,$s = x + y - 2^w$,由于 $y < 2^w$,则 $s < x$。

C 语言实现:

csapp-representing-and-manipulating-information/uadd_check.c
int uadd_ok(unsigned x, unsigned y) {
    return x + y >= x;
}

原理:无符号数的非

对满足 $0 \le x < 2^w$ 的任意 $x$,其 $w$ 位无符号数的非

$$-_w^ux = \begin{cases} x, & x = 0 \\ 2^w - x, & x > 0 \end{cases}$$

2.3.2 补码加法

两个 $w$ 位补码之和与无符号之和有完全相同的位级表示,大多数计算机使用同样的机器指令来执行无符号和有符号加法。把 $x + y$ 截断为 $w$ 位得到补码结果。

原理:对 $-2^{w-1} \le x,y \le 2^{w-1} - 1$ 的整数 $x$ 和 $y$,有:

$$x +_w^t y = \begin{cases} x + y - 2^w, & 2^{w-1} \le x + y \\ x + y, & -2^{w-1} \le x + y < 2^{w-1} \\ x + y + 2^w, & x + y < -2^{w-1} \end{cases}$$

推导

$$x +_w^t y \\ = U2T_w(T2U_w(x) +_w^u T2U_w(y)) \\ = U2T_w[(x_{w-1}2^w + x + y_{w-1}2^w + y)\ mod\ 2^w] \\ = U2T_w[(x + y)\ mod\ 2^w] (x' \cdot y')\ mod\ 2^w \\ = ((x + x_{w-1}2^w)(y + y_{w-1}2^w)\ mod\ 2^w \\ = (x \cdot y + (xy_{w-1} + yx_{w-1})2^w + 2^{2w})\ mod\ 2^w \\ = (x \cdot y)\ mod\ 2^w$$

设 $z = x + y$,$z' = z \ mod\ 2^w$,$z'' = U2T_w(z') = x +_w^t y$,分 4 种情况讨论:

  1. $-2^w \le z < -2^{w-1}$。$z' = z + 2^w$,$0 \le z' < 2^{w-1}$,$z'' = z' = x + y + 2^w$。此时必定有 $x < 0$,$y < 0$,$0 \le z'' < 2^{w-1}$,两个负数相加,结果为非负,发生负溢出。

  2. $-2^{w-1} \le z < 0$。$z' = z + 2^w$,$2^{w-1} \le z' < 2^w$,$z'' = z' - 2^w = x + y$。

  3. $0 \le z < 2^{w-1}$。$z' = z$,$z'' = z' = x + y$。

  4. $2^{w-1} \le z < 2^w$。$z' = z$,$2^{w-1} \le z' < 2^w$,$z'' = z' - 2^w = x + y - 2^w$。此时必定有 $x > 0$,$y > 0$,$-2^{w-1} \le z'' < 0$,两个正数相加,结果为负,发生正溢出。

原理:检测补码加法中的溢出:

对满足 $TMin_w \le x, y \le TMax_w$ 的 $x$ 和 $y$,令 $s = x +_w^t y$。当且仅当 $x > 0, y > 0$ 但 $s < 0^{[注]}$ 时,发生了正溢出。当且仅当 $x < 0, y < 0$ 但 $s \ge 0$ 时,发生了负溢出。

注:中英原文均为 $s \le 0$,但此时 $s = 0$ 的情况不可能发生。

推导

  1. 如果 $x > 0, y > 0$ 而 $s < 0$,那么显然发生了正溢出。

  2. 如果发生了正溢出,必有 $x > 0, y > 0$(否则 $x + y < TMax_w$,就不可能发生正溢出了),且 $s = x + y - 2^w < 0$。

同样的讨论也适用于负溢出的情况。

C 语言实现:

csapp-representing-and-manipulating-information/tadd_check.c
int tadd_ok(int x, int y) {
    int sum = x + y;
    return !(x >= 0 && y >= 0 && sum < 0) &&
        !(x < 0 && y < 0 && sum >= 0);
}

这里只用 >= 0< 0,只需取 int 符号位即可判断,不需要其他位。

2.3.3 补码的非

原理:补码的非:

对满足 $TMin_w \le x \le TMax_w$ 的 $x$,其补码的非

$$-_w^tx = \begin{cases} TMin_w, & x = TMin_w \\ -x, & x > TMin_w \end{cases}$$

计算补码位级表示的非的几种方法:

  • 对每一位取反,再对结果加 1。在 C 语言中,对于任意整数值 x-x~x + 1 的结果完全一样

  • 找到最右边的 1,将其左边所有位取反

2.3.4 无符号乘法

把乘积 $x \cdot y$ 截断为 $w$ 位。

原理

对满足 $0 \le x, y \le UMax_w$ 的 $x$ 和 $y$ 有

$$x *_w^u y = (x \cdot y)\ mod \ 2^w$$

2.3.5 补码乘法

将乘积截断为 $w$ 位。

原理:补码乘法

对满足 $TMin_w \le x, y < TMax_w$ 的 $x$ 和 $y$,有:

$$x *_w^t y = U2T_w((x \cdot y)\ mod \ 2^w)$$

对于无符号和补码乘法来说,乘法运算的位级表示都是一样的。

原理:无符号和补码乘法的位级等价性

给定长度为 $w$ 的位向量 $\vec{x}, \vec{y}, x = B2T_w(\vec{x}), y = B2T_w(\vec{y}), x' = B2U_w(\vec{x}), y' = B2U_w(\vec{y})$,则

$$T2B_w(x *_w^t y) = U2B_w(x' *_w^u y')$$

推导

$x' = x + x_{w-1}2^w, y' = y + x_{w-1}2^w$,则

$$(x' \cdot y')\ mod\ 2^w = ((x + x_{w-1}2^w)(y + y_{w-1}2^w)\ mod\ 2^w \\ = (x \cdot y + (xy_{w-1} + yx_{w-1})2^w + 2^{2w})\ mod\ 2^w \\ = (x \cdot y)\ mod\ 2^w$$

对补码乘法公式两边应用 $T2U_w$ 得

$$T2U_w(x *_w^t y) = (x \cdot y)\ mod \ 2^w = (x' \cdot y') \ mod \ 2^w = x' *_w^u y'$$

再对等式两边同时应用 $U2B_w$ 得

$$T2B_w(x *_w^t y) = U2B_w(x' *_w^u y')$$

判断补码乘法是否会溢出

  • 方法一:

    csapp-representing-and-manipulating-information/tmult_check.c
    int tmult_ok(int x, int y) {
        return !x || x * y / x == y;
    }

    证明:

    当 $x = 0$ 时,显然乘法不会溢出。

    当 $x \ne 0$ 时,

    1. $x \cdot y$ 可以用 $2w$ 位的补码数表示,设其高 $w$ 位的补码数为 $v$,低 $w$ 位的无符号数为 $u$,则

    $$x \cdot y = v2^w + u$$

    设补码乘法的结果为 $p$,则 $u = p + p_{w-1}2^w$,得

    $$x \cdot y = v2^w + p + p_{w-1}2^w = p + t2^w$$

    其中 $t = v + p_{w-1}$。

    • 当 $t = 0$ 时,$x \cdot y = p$,乘法不会溢出
    • 当 $t \ne 0$ 时,$x \cdot y \ne p$,乘法溢出

    故乘法不会溢出的充要条件为 $t = 0$。

    1. 根据整数除法,设 $p$ 除以 $x$ 的商为 $q$,余数为 $r$,则 $p = x \cdot q + r$,且 $\mid r \mid < \mid x \mid$,则

    $$x \cdot y = p + t2^w = x \cdot q + r + t2^w$$

    • 若 $q = y$,则 $r + t2^w = 0$,由于 $\mid r \mid < \mid x \mid \le 2^{w-1}$,此时必有 $t = 0$ 且 $r = 0$
    • 若 $t = 0$,则 $y - q = r / x$,由于 $\mid r \mid < \mid x \mid$,此时必有 $y = q$

    故 $t = 0$ 的充要条件为 $q = y$。

    综合 1、2 得,乘法不会溢出的充要条件为 $q = y$。

  • 方法二:

    csapp-representing-and-manipulating-information/tmult_check.c
    int tmult_ok1(int x, int y) {
        int64_t pll = (int64_t) x * y;
        return pll == (int) pll;
    }

2.3.6 乘以常数

原理:与 2 的幂相乘的无符号乘法

对于无符号数值 $x$、$k$ 的 C 变量 xy,且 $0 \le k < w$,C 表达式 x << k 产生数值 $x *_w^u 2^k$。

原理:与 2 的幂相乘的补码乘法

对于补码数值 $x$、无符号数值 $k$ 的 C 变量 xk,且 $0 \le k < w$,C 表达式 x << k 产生数值 $x *_w^t 2^k$。

无论是无符号还是补码运算,乘以 2 的幂都可能会溢出,即使溢出时其结果也与移位效果相同。

整数乘法的开销比移位和加法大得多,许多 C 编译器试图以移位和加减法的组合,来消除许多整数乘以常数的情况。例如 x * 14,$14 = 2^3 + 2^2 + 2^1$,编译器可以将乘法重写为 (x << 3) + (x << 2) + (x << 1),这样将乘法替换为三个移位和两个加法。无论 x 是无符号还是补码,甚至乘法会导致溢出时,两个计算都会得到一样的结果。还可以利用 $14 = 2^4 - 2^1$,乘法重写为 (x << 4) - (x << 1),这时只需要两个移位和一个减法。

对于某个常数 $K$ 的表达式 x * K,编译器会将 $K$ 的二进制表示表达为一组 0 和 1 交替的序列。考虑一组从 $n$ 位到 $m$ 位的连续的 1($n \ge m$),可以用两种不同的形式来计算这些位对乘积的作用:

  • 形式 A:(x << n) + (x << (n - 1)) + ... + (x << m)

  • 形式 B:(x << (n + 1)) - (x << m)

选择用移位和加减法组合,还是乘法指令,取决于这些指令的相对速度。大多数编译器只在需要少量移位和加减法就足够时才使用这种优化。

2.3.7 除以 2 的幂

整数除法总是舍入到零。

原理:除以 2 的幂的无符号除法

对于无符号数值 $x$、$k$ 的 C 变量 xk,且 $0 \le k < w$,C 表达式 x >> k 产生数值 $\lfloor x/2^k \rfloor$。

原理:除以 2 的幂的补码除法,向下舍入

对于补码数值 $x$、无符号数值 $k$ 的 C 变量 xk,且 $0 \le k < w$,当执行算数右移时 C 表达式 x >> k 产生数值 $\lfloor x/2^k \rfloor$。

推导

设 $x$ 为位模式 $[x_{w-1}, x_{w-2}, …, x_0]$ 表示的补码整数,$0 \le k < w$,$x'$ 为高 $w - k$ 位 $[x_{w-1}, x_{w-2}, …, x_k]$ 表示的补码数,$x''$ 为低 $k$ 位表示的无符号数,显然 $x = 2^k x' + x''$,而 $0 \le x'' < 2^k$,则 $x' = \lfloor x / 2^k \rfloor$。而算数右移后位向量为

$$[x_{w-1}, …, x_{w-1}, x_{w-1}, x_{w-2}, …, x_k]$$

刚好是 $[x_{w-1}, x_{w-2}, …, x_k]$ 从 $w-k$ 位符号扩展到 $w$ 位,因此位移后的位向量即为 $\lfloor x / 2^k \rfloor$ 的补码表示。

原理:除以 2 的幂的补码除法,向上舍入

对于补码数值 $x$、无符号数值 $k$ 的 C 变量 xk,且 $0 \le k < w$,当执行算数右移时 C 表达式 (x + (1 << k) - 1) >> k 产生数值 $\lceil x/2^k \rceil$。

推导

设 $x = qy + r$,其中 $0 \le r < y$,则 $\lfloor (x + y - 1) / y \rfloor = \lfloor (qy + r + y - 1) / y \rfloor = q + \lfloor (r + y - 1) / y \rfloor$。当 $x$ 能被 $y$ 整除时,$r = 0$,后面一项为 $0$,结果为 $q$,当不能整除时,$0 < r < y$,后面一项为 $1$,结果为 $q + 1$。综上得 $\lfloor (x + y - 1) / y \rfloor = \lceil y / x \rceil$。

C 表达式 x + (1 << k) - 1 得到数值 $x + 2^k - 1$,再右移 $k$ 位,即除以 $2^k$,得 $\lceil x / 2^k \rceil$。

以上分析表明,对于使用算数右移的补码机器,C 表达式

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

将会计算数值 $x/2^k$。

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

补码使用了与无符号运算相同的位级实现,包括加法、减法、乘法甚至除法。

2.4 浮点数

2.4.2 IEEE 浮点表示

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

浮点数位表示划分为三个字段:

  • 一个单独的符号位 s 直接编码符号 $s$

  • $k$ 位阶码字段 exp = $e_{k - 1}… e_1 e_0$ 编码阶码 $E$

  • $n$ 位小数字段 frac = $f_{n - 1}… f_1 f_0$ 编码尾数 $M$

单精度浮点格式中,s、exp、frac 字段分别为 1 位、k = 8 位和 n = 23 位,双精度浮点格式中分别为 1 位、k = 11 位 和 n = 52 位。

根据 exp 的值,被编码的值可以分为三种情况。

情况 1:规格化的值

当 exp 的位模式既不全为 0 也不全为 1 时,浮点数为规格化的值。

阶码的值为 $E = e - Bias$,其中 $e$ 为无符号数,位表示为 $e_{k - 1}… e_1 e_0$,偏置值 $Bias = 2^{k - 1} - 1$(单精度是 127,双精度为 1023)。由此产生的指数取值范围,对于单精度为 -126 ~ +127,双精度为 -1022 ~ +1023。

小数字段 frac 描述小数值 $f$,其二进制表示为 $0.f_{n - 1}… f_1 f_0$,尾数值为 $M = 1 + f$。$M$ 可以看作二进制表示为 $1.f_{n - 1}… f_1 f_0$ 的数字,其开头的 1 是隐含的,这样可以获得额外的一位精度。

情况 2:非规格化的值

当阶码全为 0 时,浮点数表示非规格化的值。

此时阶码的值为 $E = 1 - Bias = 2 - 2^{k - 1}$,单精度即为 -126,双精度即为 -1022,与规格化值的最小阶码相同。尾数的值为 $M = f$,即不包含隐含位。这种设置可以让规格化值与规格化数值之间平滑过渡。

功能 1:表示 0。规格化数中尾数总是 $M \ge 1$,无法表示 0,但是非规格化可以表示 0:

  • +0.0:所有位都为 0

  • -0.0:符号位为 1,其它位全为 0

功能 2:表示非常接近 0 的数。非规格化数是均匀接近于 0 的(渐进式下溢,gradual underflow),而规格化数绝对值越小分布越稠密。

情况 3:特殊值

当阶码全为 1 时,浮点数为特殊值。

当小数字段全为 0 时,值为无穷,且 $s = 0$ 时为 $+\infty$,$s = 1$ 时为 $-\infty$,可以表示溢出的结果。

当小数字段不为 0 时,值为 NaN(Not a Number),例如 $\sqrt{-1}$ 或 $\infty - \infty$ 的结果。也可用来表示未初始化的数据。

2.4.3 数字示例

描述位表示
00 00000000 00000000000000000000000$0$
最小非规格化数0 00000000 00000000000000000000001$2^{-23} \cdot 2^{-126}$
最大非规格化数0 00000000 11111111111111111111111$(1 - 2^{-23}) \cdot 2^{-126}$
最小规格化数0 00000001 00000000000000000000000$2^{-126}$
最大规格化数0 11111110 11111111111111111111111$(2 - 2^{-23}) \cdot 2^{127}$
无穷大0 11111111 00000000000000000000000$\infty$

C 语言中 float.h 中定义了一些浮点数的值。

Java 中 Float 类定义了一些单精度浮点数的值:

public final class Float extends Number implements Comparable<Float> {
    /**
     * A constant holding the positive infinity of type
     * {@code float}. It is equal to the value returned by
     * {@code Float.intBitsToFloat(0x7f800000)}.
     */
    public static final float POSITIVE_INFINITY = 1.0f / 0.0f;

    /**
     * A constant holding the negative infinity of type
     * {@code float}. It is equal to the value returned by
     * {@code Float.intBitsToFloat(0xff800000)}.
     */
    public static final float NEGATIVE_INFINITY = -1.0f / 0.0f;

    /**
     * A constant holding a Not-a-Number (NaN) value of type
     * {@code float}.  It is equivalent to the value returned by
     * {@code Float.intBitsToFloat(0x7fc00000)}.
     */
    public static final float NaN = 0.0f / 0.0f;

    /**
     * A constant holding the largest positive finite value of type
     * {@code float}, (2-2<sup>-23</sup>)&middot;2<sup>127</sup>.
     * It is equal to the hexadecimal floating-point literal
     * {@code 0x1.fffffeP+127f} and also equal to
     * {@code Float.intBitsToFloat(0x7f7fffff)}.
     */
    public static final float MAX_VALUE = 0x1.fffffeP+127f; // 3.4028235e+38f

    /**
     * A constant holding the smallest positive normal value of type
     * {@code float}, 2<sup>-126</sup>.  It is equal to the
     * hexadecimal floating-point literal {@code 0x1.0p-126f} and also
     * equal to {@code Float.intBitsToFloat(0x00800000)}.
     *
     * @since 1.6
     */
    public static final float MIN_NORMAL = 0x1.0p-126f; // 1.17549435E-38f

    /**
     * A constant holding the smallest positive nonzero value of type
     * {@code float}, 2<sup>-149</sup>. It is equal to the
     * hexadecimal floating-point literal {@code 0x0.000002P-126f}
     * and also equal to {@code Float.intBitsToFloat(0x1)}.
     */
    public static final float MIN_VALUE = 0x0.000002P-126f; // 1.4e-45f

    // ...
}

上面表格中的值,如果把浮点数的位表示解释为无符号整数,它们就是按升序排列的,就像它们表示的浮点数一样,以便使用整数排序函数进行排序。如果符号位为 1,就是降序排列的。

2.4.4 舍入

IEEE 浮点数规定了四种舍入方式:

  1. Round-to-even 向偶数舍入(向最接近的值舍入)

是默认方式,将结果舍入为最接近的值,如果两个数一样接近时,则取最低有效数字为偶数的值。这样的好处是避免统计偏差。例如如果总是向上舍入,则平均值总是比实际高一些。

  1. Round-toward-zero 向零舍入

  2. Round-down 向下舍入

  3. Round-up 向上舍入

2.4.5 浮点运算

浮点加法是可交换的,但不可结合,例如 (3.14 + 1e10) - 1e10 的结果为 0.0,但 3.14 + (1e10 - 1e10) 的结果为 3.14,由于舍入而丢失了精度。编译器就无法利用结合性进行优化。

浮点加法具有单调性:如果 $a \ge b$,那么对于任何 $a$、$b$ 和 $x$ 的值,除 $NaN$ 外,都有 $x + a \ge x + b$。而无符号或补码加法则不具有。

浮点乘法也是可交换但不可结合的,例如 (1e20 * 1e20) * 1e-20 结果为 inf1e20 * (1e20 * 1e-20) 结果为 1e20。浮点乘法在加法上不具备分配性,例如 1e20 * (1e20 - 1e20) 的结果为 0.01e20 * 1e20 - 1e20 * 1e20 结果为 nan

家庭作业

2.58

判断是否为小端机器:

csapp-representing-and-manipulating-information/is_little_endian.c
int is_little_endian() {
    int i = 1;
    return *(char *) &i;
}

2.62

判断是否为算数右移:

csapp-representing-and-manipulating-information/is_shifts_are_arithmetic.c
const size_t W = sizeof(int) << 3;

int is_shifts_are_arithmetic() {
    return (-1 >> (W - 1) >> 1) & 1;
}

2.63

用算数右移模拟逻辑右移、用逻辑右移模拟算数右移:

csapp-representing-and-manipulating-information/right_shifts.c
const size_t W = sizeof(int) << 3;

unsigned srl(unsigned x, int k) {
    assert(0 <= k && k < W);
    /* Perform shift arithmetically */
    unsigned xsra = (int) x >> k;
    unsigned mask = (1 << (W - k)) - 1;
    return xsra & mask;
}

int sra(int x, int k) {
    assert(0 <= k && k < W);
    /* Perform shift logically */
    int xsrl = (unsigned) x >> k;
    unsigned sign = ((unsigned) x & INT_MIN) >> (W - 1);
    unsigned mask = ~((sign << (W - k)) - 1);
    return xsrl | mask;
}

2.65

判断无符号整数二进制形式中是否有奇数个 1:

csapp-representing-and-manipulating-information/odd_ones.c
/* Return 1 when x contains an odd number of 1s; 0 otherwise.
 * Assume w=32 */
int odd_ones(unsigned x) {
    assert(sizeof(unsigned) == 4);
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 1;
}

让所有二进制位做异或操作,即得到结果。

2.66

找到无符号整数二进制形式中最高位的 1:

csapp-representing-and-manipulating-information/leftmost_one.c
/*
 * Generate mask indicating leftmost 1 in x.  Assume w=32.
 * For example, 0xFF00 -> 0x8000, and 0x6600 --> 0x4000.
 * If x = 0, then return 0.
 */
int leftmost_one(unsigned x) {
    assert(sizeof(unsigned) == 4);
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x ^ (x >> 1);
}

2.67

判断 int 类型是否为 32 位,可以在 16 位及以上的机器上运行:

csapp-representing-and-manipulating-information/int_size_is_32.c
int int_size_is_32() {
    int set_msb = 1 << 15 << 15 << 1;
    int beyond_msb = set_msb << 1;
    return set_msb && !beyond_msb;
}

2.68

生成低 n 位为 1 的掩码:

csapp-representing-and-manipulating-information/lower_one_mask.c
const size_t W = sizeof(int) << 3;

/*
 * Mask with least signficant n bits set to 1
 * Examples: n = 6 --> 0x3F, n = 17 --> 0x1FFFF
 * Assume 1 <= n <= w
 */
int lower_one_mask(int n) {
    assert(1 <= n && n <= W);
    return (1 << (n - 1) << 1) - 1;
}

2.69

实现循环左移:

csapp-representing-and-manipulating-information/rotate_left.c
const size_t W = sizeof(unsigned) << 3;

/*
 * Do rotating left shift.  Assume 0 <= n < w
 * Examples when x = 0x12345678 and w = 32:
 *    n=4 -> 0x23456781, n=20 -> 0x67812345
 */
unsigned rotate_left(unsigned x, int n) {
    assert(0 <= n && n < W);
    return (x << n) | (x >> (W - n));
}

2.70

判断 x 能否用 n 位补码表示:

csapp-representing-and-manipulating-information/fits_bits.c
const size_t W = sizeof(int) << 3;

/*
 * Return 1 when x can be represented as an n-bit, 2's-complement
 * number; 0 otherwise
 * Assume 1 <= n <= w
 */
int fits_bits(int x, int n) {
    assert(1 <= n && n <= W);
    unsigned mask = (unsigned) -1 >> (W - n);
    return x == (x & mask);
}

2.73

补码加法,溢出时返回最值:

csapp-representing-and-manipulating-information/saturating_add.c
/* Addition that saturates to TMin or TMax */
int saturating_add(int x, int y) {
    int s = x + y;
    int of = !(x & INT_MIN) && !(y & INT_MIN) && (s & INT_MIN);
    of && (s = INT_MAX);
    int uf = (x & INT_MIN) && (y & INT_MIN) && !(s & INT_MIN);
    uf && (s = INT_MIN);
    return s;
}

2.74

判断补码减法是否溢出:

csapp-representing-and-manipulating-information/tsub_ok.c
/* Determine whether arguments can be subtracted without overflow */
int tsub_ok(int x, int y) {
    int s = x - y;
    int of = !(x & INT_MIN) && (y & INT_MIN) && (s & INT_MIN);
    int uf = (x & INT_MIN) && !(y & INT_MIN) && !(s & INT_MIN);
    return !of && !uf;
}

2.75

已知补码乘法高 $w$ 位,求无符号整数乘法高 $w$ 位。

在补码乘法与无符号乘法的位级等价性推导中,

$$x' \cdot y' = (x + x_{w-1}2^w)(y + y_{w-1}2^w) = x \cdot y + (xy_{w-1} + yx_{w-1})2^w + 2^{2w}$$

两边同时除以 $2^w$ 即可得到乘积的高 $w$ 位。

csapp-representing-and-manipulating-information/unsigned_high_prod.c
const size_t W = sizeof(int) << 3;

int signed_high_prod(int x, int y) {
    return (int64_t) x * y >> W;
}

unsigned unsigned_high_prod(unsigned x, unsigned y) {
    int shp = signed_high_prod(x, y);
    return shp + x * (y >> (W - 1)) + y * (x >> (W - 1));
}

unsigned uhp(unsigned x, unsigned y) {
    return (uint64_t) x * y >> W;
}

2.76

实现 calloc 函数:

csapp-representing-and-manipulating-information/calloc.c
void *calloc(size_t nmemb, size_t size) {
    if (nmemb == 0 || size == 0)
        return NULL;
    size_t n = nmemb * size;
    if (n / nmemb != size)
        return NULL;
    void *p = malloc(n);
    if (p)
        memset(p, 0, n);
    return p;
}

2.78

用移位实现除以 2 的幂算法,由于除法是向零取整的,当 $x < 0$ 时需要加一个偏移量:

csapp-representing-and-manipulating-information/divide_power2.c
const size_t W = sizeof(int) << 3;

/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k) {
    assert(0 <= k && k < W - 1);
    int bias = 0;
    (x & INT_MIN) && (bias = (1 << k) - 1);
    return (x + bias) >> k;
}

2.79

计算 $3x/4$,其中 $3x$ 可能溢出:

csapp-representing-and-manipulating-information/mul3div4.c
int mul3div4(int x) {
    x += (x << 1);
    int bias = 0;
    (x & INT_MIN) && (bias = 3);
    return (x + bias) >> 2;
}

2.80

计算 $3x/4$,其中 $3x$ 不允许溢出,此时可把 $x$ 分为高 $w-2$ 位和低 $2$ 位两部分计算,其中高位无需考虑舍入,只有低位需要加入偏移量:

csapp-representing-and-manipulating-information/threefourths.c
int threefourths(int x) {
    int high = x & ~3, low = x & 3;
    high = (high >> 1) + (high >> 2);
    low += low << 1;
    int bias = 0;
    (x & INT_MIN) && (bias = 3);
    return high + ((low + bias) >> 2);
}

2.83

A. 设 $x$ 的二进制表示为 $0.yyyy…$,其中 $y$ 是一个 $k$ 位序列,两边同时左移 $k$ 位得

$$x « k = y.yyy…$$

$$x \cdot 2^k = y + x$$

$$x = \frac{y}{2^k-1}$$

2.84

比较浮点数大小:

csapp-representing-and-manipulating-information/float_le.c
unsigned f2u(float f) {
    return *(unsigned *) &f;
}

int float_le(float x, float y) {
    assert(sizeof(unsigned) == 4);
    unsigned ux = f2u(x);
    unsigned uy = f2u(y);

    /* Get the sign bits */
    unsigned sx = ux >> 31;
    unsigned sy = uy >> 31;

    /* Give an expression using only ux, uy, sx, and sy */
    return (ux << 1 == 0 && uy << 1 == 0) ? 1
        : (sx ^ sy ? sx : (sx ? ux >= uy : ux <= uy));
}

2.90

求浮点数 $2^x$:

csapp-representing-and-manipulating-information/fpwr2.c
unsigned f2u(float f) {
    return *(unsigned *) &f;
}

float u2f(unsigned u) {
    return *(float *) &u;
}

float fpwr2(int x) {
    /* Result exponent and fraction */
    unsigned exp, frac;
    unsigned u;

    if (x < -149) {
        /* Too small.  Return 0.0 */
        exp = 0;
        frac = 0;
    } else if (x < -126) {
        /* Denormalized result */
        exp = 0;
        frac = 1 << (149 + x);
    } else if (x < 128) {
        /* Normalized result. */
        exp = x + 127;
        frac = 0;
    } else {
        /* Too big.  Return +oo */
        exp = 255;
        frac = 0;
    }

    /* Pack exp and frac into 32 bits */
    u = exp << 23 | frac;
    /* Return as float */
    return u2f(u);
}

2.92

求浮点数相反数:

csapp-representing-and-manipulating-information/float_negate.c
typedef unsigned float_bits;

/* Compute -f.  If f is NaN, then return f. */
float_bits float_negate(float_bits f) {
    unsigned sign = f & 0x80000000, exp = f & 0x7f800000, frac = f & 0x007fffff;
    if (!(exp == 0x7f800000 && frac != 0))
        sign ^= 0x80000000;
    return sign | exp | frac;
}

2.93

求浮点数绝对值:

csapp-representing-and-manipulating-information/float_absval.c
typedef unsigned float_bits;

/* Compute |f|.  If f is NaN, then return f. */
float_bits float_absval(float_bits f) {
    unsigned sign = f & 0x80000000, exp = f & 0x7f800000, frac = f & 0x007fffff;
    if (sign && !(exp == 0x7f800000 && frac != 0))
        sign = 0;
    return sign | exp | frac;
}

2.94

求浮点数 $2x$:

csapp-representing-and-manipulating-information/float_twice.c
typedef unsigned float_bits;

/* Compute 2*f.  If f is NaN, then return f. */
float_bits float_twice(float_bits f) {
    if (f << 1 == 0 || (f & 0x7f800000) == 0x7f800000)
        return f;
    unsigned sign = f & 0x80000000, exp = f & 0x7f800000, frac = f & 0x007fffff;
    if (exp == 0)
        return sign | f << 1;
    exp += 0x00800000;
    if (exp == 0x7f800000)
        frac = 0;
    return sign | exp | frac;
}

IEEE 浮点数的设计很精妙,当浮点数为非规格化时,直接将除符号位外整体左移一位即可。

2.95

求浮点数 $0.5x$:

csapp-representing-and-manipulating-information/float_half.c
typedef unsigned float_bits;

/* Compute 0.5*f.  If f is NaN, then return f. */
float_bits float_half(float_bits f) {
    if (f << 1 == 0 || (f & 0x7f800000) == 0x7f800000)
        return f;
    unsigned sign = f & 0x80000000, exp = f & 0x7f800000, frac = f & 0x007fffff;
    if ((exp & 0x7f000000) == 0) {
        f &= 0x7fffffff;
        if ((f & 3) == 3)
            ++f;
        return sign | f >> 1;
    }
    exp -= 0x00800000;
    return sign | exp | frac;
}

比求 $2x$ 要复杂一些,因为当尾数右移时要考虑舍入的问题,如果最后两位为 11,则需要添加一个偏移量以向偶数舍入。

2.96

float 转换为 int

csapp-representing-and-manipulating-information/float_f2i.c
typedef unsigned float_bits;

/*
 * Compute (int) f.
 * If convertion causes overflow or f is NaN, return 0x80000000
 */
int float_f2i(float_bits f) {
    int exp = ((f >> 23) & 0xff) - 127;
    if (exp < 0)
        return 0;
    if (exp > 30)
        return 0x80000000;
    int sign = f >> 31, frac = (f & 0x007fffff) | 0x00800000, value;
    if (exp < 23)
        value = frac >> (23 - exp);
    else if (exp > 23)
        value = frac << (exp - 23);
    return sign ? -value : value;
}

2.97

int 转换为 float

csapp-representing-and-manipulating-information/float_i2f.c
typedef unsigned float_bits;

/* Compute (float) i */
float_bits float_i2f(int i) {
    unsigned sign = i & 0x80000000, frac = sign ? -i : i, exp = -1;
    for (unsigned u = frac; u; ++exp) u >>= 1;
    if (exp < 23) {
        frac <<= 23 - exp;
    } else if (exp > 23) {
        unsigned w = exp - 23, mask = (unsigned) -1 >> (32 - w);
        unsigned shifts = frac & mask, mid = 1 << (w - 1);
        unsigned bias = 0;
        if (shifts > mid)
            bias = 1 << (w - 1);
        else if (shifts == mid && (frac & (1 << w)))
            bias = 1 << (w - 1);
        frac = (frac + bias) >> (exp - 23);
    }
    exp = (exp + 127) << 23;
    frac &= 0x007fffff;
    return sign | exp | frac;
}

float 转换为 int 复杂一些,因为要考虑舍入的问题。

CSAPP读书笔记
本站的全部文字在署名-非商业性使用-相同方式共享 4.0 国际协议之条款下提供。

素数筛法和哥德巴赫猜想

CSAPP 计算机系统漫游