CSAPP Ch2. 信息的表示和处理

信息存储

任何信息在计算机中都是由 0 和 1 组成的比特串，但程序一般都是按字节进行寻址，而不会访问单独的比特位。对于程序来说，内存就是一个巨大的字节数组。字长是计算机地址（指针值）的占位大小，对于一台 w 位的机器，其虚拟地址空间的最大范围就是[0, 2^{w}-1]。

硬件和操作系统共同决定了信息在内存中存储的字节顺序，分大端法和小端法两种。“大端”就是数值高位在前，“小端”就是数值低位在前。比如，对于十六进制数 0x01234567（32位，4字节），大端法存储就01、23、45、67，小端法存储就是67、45、23、01。在 Linux 中执行 lscpu 命令可以看到系统的字节顺序，也可以通过下面的 C 程序进行判断。

#include <stdio.h>

void show_bytes(void *ptr, int len) {
    for (int i = 0; i < len; i++) {
        printf("%.2x ", ((unsigned char *)ptr)[i]);
    }
    printf("\n");
}

int main() {
    int num = 0x01234567;
    show_bytes(&num, sizeof(int)); // 小端存储输出结果为：67 45 23 01
}

整数

最早的时候，人们发明计算机仅仅是为了数学计算 [2]。因此，必然要了解数在计算机中的表示与运算。浮点数的表示机制比较复杂，我们着重了解整数部分。

整数表示

无符号整数容易理解，它基本就是原生的二进制表示。但无符号整数的使用场景很有限，事实上，除了 C 以外很少有语言支持无符号整数（语言的设计者认为其带来的弊大于利）。有符号数有三种标准的表示方法：原码、反码和补码，现在几乎所有的机器都以补码来表示有符号整数和实现运算。

补码表示

对于w位的比特串 x_{w-1}x_{w-2}...x_1x_0，它表示的数值为：

w位补码编码表示的范围是-2^{w-1}到2^{w-1}-1。

整数运算

补码加法

记+为一般的整数加法，定义+^t_w为补码加法，它使得x+^t_wy为整数和x+y的补码表示截断为w位的结果。关于补码加法有下面定理成立（证明略）：

这其中最关键的是中间未溢出的部分，它保证了补码加法的正确性。我们通过下面表格来理解上述定理。

关于补码表示有一条性质值得注意：对于任意的w位补码数a，其关于补码加法+_w^t的逆元（记为-a）都可以通过\sim a+1快速得到，即对a的每一位求补，然后对结果加 1。特殊地，-2^{w-1}的逆元是它自己。

乘法与除法

在大多数机器上，整数的乘法指令相当慢，需要 10 个或者更多的时钟周期。整数除法则要更慢，需要 30 个或者更多的时钟周期，因此，编译器对于一些特殊的整数乘法和除法，会尝试使用诸如移位、加法等更初级的运算来进行代替，从而加快运算速度。

浮点数

浮点数的机器表示要复杂得多，因为原生的二进制小数表示体系无法基于少量的位来表示大规模的实数集合。这里只记录 IEEE 浮点标准中浮点数及其运算的一些重要特征，目前的计算机实际上都支持 IEEE 浮点标准。

• 浮点数天然无法精确表示所有实数，对于绝大部分实数只能进行近似表示；

• 可表示的实数并不是均匀分布的，越靠近原点处越稠密；

• 浮点运算会取近似，同样也可能溢出，且浮点运算并不满足结合律和分配率，这些对于科学计算程序和编译器（以及任何对计算精度要求高的场景）的编写者来说很重要。

References

1. 《深入理解计算机系统》

2. 《穿越计算机的迷雾》