2.1 信息存储

2.1.1 十六进制表示法

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

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

2.1.2 字数据大小

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

1	$ gcc -m32 prog.c

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

1	$ 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，即，按照 C 标准实际上位移量是，但这种行为对于 C 程序来说是没有保证的。而 Java 则保证这一点。

2.2 整数表示

2.2.3 补码编码

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

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

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

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

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

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

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

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

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

1 2	#define INT_MAX 2147483647 #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。

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

推导：要证明

只需证明

将左边展开：

归纳即可证明。

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

2.3 整数运算

2.3.2 补码加法

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

原理：对的整数和，有：

推导：

设，，，分 4 种情况讨论：

。，，。此时必定有，，，两个负数相加，结果为非负，发生负溢出
。，，
。，
。，，。此时必定有，，，两个正数相加，结果为负，发生正溢出

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

对满足的和，令。当且仅当但 $注$ 时，发生了正溢出。当且仅当但时，发生了负溢出。

注：中英原文均为，但此时的情况不可能发生。

推导：

如果而，那么显然发生了正溢出
如果发生了正溢出，必有（否则，就不可能发生正溢出了），且

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

C 语言实现：

int tadd_ok(int x, int y)
{
    int sum = x + y;
    int pos_of = x >= 0 && y >= 0 && sum < 0,
        neg_of = x < 0 && y < 0 && sum >= 0;
    return !pos_of && !neg_of;
}

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

2.3.3 补码的非

原理：补码的非：

对满足的，其补码的非

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

对每一位取反，再对结果加 1。在 C 语言中，对于任意整数值 x，-x 和 ~x + 1 的结果完全一样
找到最右边的 1，将其左边所有位取反

2.3.5 补码乘法

将乘积截断为位。

原理：补码乘法

对满足的和，有：

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

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

给定长度为的位向量，则

推导：

，则

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

再对等式两边同时应用得

判断补码乘法是否会溢出

C 语言实现

方法一：
1
2
3
4

int tmult_ok(int x, int y)
{
return !x || x * y / x == y;
}
证明：

当时，显然乘法不会溢出。

当时，
1. 可以用位的补码数表示，设其高位的补码数为，低位的无符号数为，则
  
  设补码乘法的结果为，则，得
  
  其中。
  - 当时，，乘法不会溢出
  - 当时，，乘法溢出
  故乘法不会溢出的充要条件为。
2. 根据整数除法，设除以的商为，余数为，则，且，则
  - 若，则，由于，此时必有且
  - 若，则，由于，此时必有
  故的充要条件为。
综合 1、2 得，乘法不会溢出的充要条件为。

方法二：

int tmult_ok1(int x, int y)
{
    int64_t pll = (int64_t) x * y;
    return pll == (int) pll;
}

2.3.6 乘以常数

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

对于无符号数值、的 C 变量 x 和 y，且，C 表达式 x << k 产生数值。

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

对于补码数值、无符号数值的 C 变量 x 和 k，且，C 表达式 x << k 产生数值。

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

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

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

形式 A：(x << n) + (x << (n - 1)) + ... + (x << m)
形式 B：(x << (n + 1)) - (x << m)

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

2.3.7 除以 2 的幂

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

对于无符号数值、的 C 变量 x 和 k，且，C 表达式 x >> k 产生数值。

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

对于补码数值、无符号数值的 C 变量 x 和 k，且，当执行算数右移时 C 表达式 x >> k 产生数值。

推导：

设为位模式表示的补码整数，，为高位表示的补码数，为低位表示的无符号数，显然，而，则。而算数右移后位向量为

刚好是从位符号扩展到位，因此位移后的位向量即为的补码表示。

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

对于补码数值、无符号数值的 C 变量 x 和 k，且，当执行算数右移时 C 表达式 (x + (1 << k) - 1) >> k 产生数值。

推导：

设，其中，则。当能被整除时，，后面一项为，结果为，当不能整除时，，后面一项为，结果为。综上得。

C 表达式 x + (1 << k) - 1 得到数值，再右移位，即除以，得。

2.4 浮点数

2.4.2 IEEE 浮点表示

IEEE 浮点标准用的形式来表示一个数。

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

一个单独的符号位 s 直接编码符号
位阶码字段 exp = 编码阶码
位小数字段 frac = 编码尾数

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

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

情况 1:规格化的值

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

阶码的值为，其中为无符号数，位表示为，偏置值（单精度是 127，双精度为 1023）。由此产生的指数取值范围，对于单精度为 -126 ~ +127，双精度为 -1022 ~ +1023。

小数字段 frac 描述小数值，其二进制表示为，尾数值为。可以看作二进制表示为的数字，其开头的 1 是隐含的，这样可以获得额外的一位精度。

情况 2:非规格化的值

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

此时阶码的值为，单精度即为 -126，双精度即为 -1022，与规格化值的最小阶码相同。尾数的值为，即不包含隐含位。这种设置可以让规格化值与规格化数值之间平滑过渡。

功能 1：表示 0。规格化数中尾数总是，无法表示 0，但是非规格化可以表示 0：

+0.0：所有位都为 0
-0.0：符号位为 1，其它位全为 0

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

情况 3:特殊值

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

当小数字段全为 0 时，值为无穷，且时为，时为，可以表示溢出的结果。

当小数字段不为 0 时，值为 NaN（Not a Number），例如或的结果。也可用来表示未初始化的数据。

2.4.3 数字示例

描述	位表示	值
0	0 00000000 00000000000000000000000
最小非规格化数	0 00000000 00000000000000000000001
…	…	…
最大非规格化数	0 00000000 11111111111111111111111
最小规格化数	0 00000001 00000000000000000000000
…	…	…
最大规格化数	0 11111110 11111111111111111111111
无穷大	0 11111111 00000000000000000000000

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，就是降序排列的。之所以不直接用补码整数来解释，是因为 -0.0 的位表示用补码解释的话就是最小值，显然不合理。

2.4.4 舍入

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

Round-to-even 向偶数舍入（向最接近的值舍入）

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

2.4.5 浮点运算

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

浮点加法具有单调性：如果，那么对于任何、和的值，除外，都有。而无符号或补码加法则不具有。

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

csapp 信息的表示和处理 2.1 信息存储 2.2 整数表示 2.3 整数运算 2.3.3 补码的非 2.4 浮点数