CSAPP 信息的表示和处理

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_t 和 int64_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 语言创建一个无符号常量，必须加上后缀字符 U 或 u，例如 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 语言实现：

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 语言实现：

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’)$$

判断补码乘法是否会溢出

• 方法一：

  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$。

  2. 根据整数除法，设 $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$。

• 方法二：

  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 变量 x 和 y，且 $0 \le k < w$，C 表达式 x << k 产生数值 $x *_w^u 2^k$。

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

对于补码数值 $x$、无符号数值 $k$ 的 C 变量 x 和 k，且 $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 变量 x 和 k，且 $0 \le k < w$，C 表达式 x >> k 产生数值 $\lfloor x/2^k \rfloor$。

原理：除以 2 的幂的补码除法，向下舍入

对于补码数值 $x$、无符号数值 $k$ 的 C 变量 x 和 k，且 $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 变量 x 和 k，且 $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 数字示例

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 向偶数舍入（向最接近的值舍入）

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

2. Round-toward-zero 向零舍入

3. Round-down 向下舍入

4. 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 结果为 inf，1e20 * (1e20 * 1e-20) 结果为 1e20。浮点乘法在加法上不具备分配性，例如 1e20 * (1e20 - 1e20) 的结果为 0.0，1e20 * 1e20 - 1e20 * 1e20 结果为 nan。

家庭作业

2.58

判断是否为小端机器：

int is_little_endian() {
    int i = 1;
    return *(char *) &i;
}

2.62

判断是否为算数右移：

const size_t W = sizeof(int) << 3;

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

2.63

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

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：

/* 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：

/*
 * 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 位及以上的机器上运行：

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 的掩码：

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

实现循环左移：

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 位补码表示：

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

补码加法，溢出时返回最值：

/* 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

判断补码减法是否溢出：

/* 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$ 位。

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 函数：

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$ 时需要加一个偏移量：

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$ 可能溢出：

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$ 位两部分计算，其中高位无需考虑舍入，只有低位需要加入偏移量：

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

比较浮点数大小：

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$：

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

求浮点数相反数：

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

求浮点数绝对值：

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$：

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$：

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：

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：

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 复杂一些，因为要考虑舍入的问题。