信息存储

十六进制与字节顺序

在计算机中，信息的存储均为二进制位(bit)的形式。每八个二进制位就形成一个字节(byte)。由于二进制位的表示将会把数字拉得很长，通常我们会用十六进制来表示。每个十六进制位都恰好表示四个二进制位，高位补0。

内存中的空间是以字节为单位的。而一个字节只有8位，可以存储的数据非常少。因此跨字节的存储就成为了必需。这也就意味着对于内存中的对象，我们需要两个规则：

这个对象的地址是什么？
内存中这些字节如何排列？

在所有的机器上，跨越多个字节的数据都是连续存储的，其地址为它所使用的字节中地址最小的一个。例如 int 型变量 x 需要用4个字节，分别为0x100 0x101 0x102 0x103，那么 &x 的值就是 0x100。但是 x 的四个字节在其中如何排列又成为了一个问题。设 x = 0x01234567，那么它的排列可能是 01 23 45 67 也有可能是 67 45 23 01。前者小端在前，称为小端法(little endian)；后者大端在前，称为大端法(big endian)。

字长

每台计算机都有一个字长(word size)，表明一个指针数据的标称大小。旧一些的机器通常是32位字长的，意味着它可以访问的字节数为 $2^{32}-1$。这样的空间总和大约为4GB，也就是说32位的机器最多只支持4GB的内存。而目前市面上的机器字长都是64位，其虚拟地址空间为16EB（$1.84\times 10^{19}$字节），远远超出我们现在所使用的空间了。一般地，字长为 $w$ 的机器，虚拟地址的范围为0到 $2^w-1$。同时需要强调，无论指针的类型如何，因为它表示的都是一个虚拟地址，所以其位数不变。在64位机器上，尽管 char 类型只有一个字节，但是 char *则会被分配8个字节。

字符与字符串

在C语言中，字符用 char 类型表达，占一个字节。这一个字节表示一个整数，它与不同的字符之间有一个映射规则，即 ASCII。因此字符型的变量存储和整数没有区别。字符串则是一个由字符组成的数组，并在其结尾有一个 \0，其 ASCII 码为0，标志着字符串的结尾。

布尔代数

布尔运算

布尔运算有& | ~ ^ 四种，分别为与、或、非和异或。它们的操作数只有0和1两种。其运算规则如下：

与：1 & 1 = 1，其余情况为0；
或：0 & 0 = 0，其余情况为1；
非：~1 = 0 ，~0 = 1；
异或：两数同为1或同为0得0，否则得1；

位级运算

在C语言中，同样的运算符将对操作数进行按位布尔运算。例如：

~0x41 = ~[01000001] = [10111110] = 0xBE；
0x69 & 0x55 = [01101001] & [01010101] = [01000001] = 0x41；
0x69 | 0x55 = [01101001] & [01010101] = [01111101] = 0x7D；

位级运算的重要作用之一是实现掩码运算。若要保留某个位，可用 &1或者|0；将某些位置为0，可用 &0；将某个位置为1，可用 |1。

逻辑运算

逻辑运算有三种：逻辑与&&，逻辑或||，逻辑非!。其运算规则是：

逻辑与：非零和非零得1，反之为0；
逻辑或：零和零得0，反之为1；
逻辑非：非零得0，零得1；

移位运算

C语言中有左移<<和右移>>两种移位运算。左移时低位补0，高位舍去；右移时则分为逻辑右移和算术右移两种。逻辑右移高位直接补0，而算术右移高位将补原来数的最高位。

对一个 $w$ 位存储的整数，向左移位时最多可以移动 $w - 1$ 位。考虑表达式 x << m ，若 $m >= w$ ，那么计算机会先进行 m %= w 的运算。也就是说，如果 $m=w$，那么 x << m 的值将与 x 完全相同。

整数的表达

整数的类型

在C语言中，一般有 char short int long long long 几种。它们占的内存（一般）为1、2、4、4、8字节。它们还有各自的无符号类型。无符号类型就只能表达非负数。

无符号数与有符号数

对有 $w$ 位来存储的整型变量，若为无符号类型，则其表达范围为0～$2^w-1$；若为有符号类型，则其表达范围为 $-2^w$ ～ $2^w - 1$。以下均认为我们所指的整型变量由 $w$ 位存储。

对无符号数而言，自右向左第 $k$ 位的权重为 $2^{k-1}$。所有位的加权和即为其表示的十进制值。对有符号数而言，最高位的权重为 $-2^w$，其余与无符号数相同。这样的表达也称为整数的补码表示。在这样的编码规则下，非负数的补码和原码相同，负数的补码是其相反数按位取反再加1。

这里需要注意，在32位 int 类型中，如果要表达 -2147483648 这个32位整数可以表达的最小值，一定要用 -2147483647-1 来表示。否则计算机将对 2147483648 这一个数取相反数。但是这个数已经超出了32位整型能表达的范围，就会出现问题。

另外，无符号类型的等级比有符号类型要高。因此如果无符号数和有符号数进行运算，结果将返回无符号数。如以下代码：

double sum_elements(double a[], unsigned length) {
    int i;
    double result = 0;
    for (i = 0; i <= length - 1; ++i) {
        result += a[i];
    }
    return result;
}

若 length == 0 ，那么在 for 循环中，length - 1 就会返回无符号数的最大值 $2^{32} - 1$，从而在访问 a[i] 时出现下标越界的状况。将 i <= length - 1 改为 i < length 即可解决这个问题。同样的道理，在无符号数的运算中，x - y > 0 和 x > y 可能会产生不同的结果。

溢出

由于存储的空间有限，一旦运算结果超出了可存储数的范围，就是出现溢出。这个时候，计算机会保留运算结果中较低的 $w$ 位。

加法

对无符号数而言，$0\leq x, y \leq 2^w - 1$ ，因此 $0\leq x + y\leq 2^{w+1}-2$ 。令 $z = x + y$，当 $0\leq z \leq 2^w - 1$ 时，不会发生溢出。但是当 $2^w\leq z\leq 2^{w+1} - 2$ 时，最高位超出了 $w$ 位的表示范围，于是得到的结果 $z’ = z\mod 2^w$。

对有符号数而言，$-2^{w-1}\leq x,y\leq 2^{w-1} - 1$，因此 $-2^w\leq x+y\leq 2^w - 2$。令 $z=x+y$，当 $-2^{w-1}\leq z\leq 2^{w-1} - 1$ 时不会发生溢出。当 $2^{w-1}\leq z\leq 2^w-2$，最高位出现一个权重为 $2^w$ 的进位会被舍去，于是 $z’=z-2^w<0$，称为正溢出（得到负数）。当 $-2^w\leq z\leq 2^{w-1}$，最高位出现退位，$z’=z+2^w>0$，称为负溢出（得到正数）。

乘法

类似的，乘法也会出现对应的溢出。

对两个无符号数 $x, y$，$0\leq x, y \leq 2^w - 1$。令 $z=x\cdot y$，则有 $0\leq z\leq 2^{2w} - 2^{w+1}+1$。然而一个无符号数 $z$ 若没有溢出，它应该满足 $0\leq z \leq 2^w-1$。在 $2^w\leq z\leq 2^{2w} - 2^{w+1}+1$ 的情况下都会出现溢出。此时将直接取低 $w$ 位。

有符号数的乘法在位级水平上与无符号数完全相同。因此只要将 $x\cdot y$ 的二进制表示取低 $w$ 位作为补码解读，即可得到计算的结果。考虑表达式 x * x，在不溢出的情况下它应该是一个大于等于0的数。设 $z=x^2$，那么不溢出的范围应该是 $z < 2^{31}$。因此只要 $x\geq 2^{15.5}\approx 46341$ 就会发生溢出。事实上，若 $x=2^{16}-1=65535$，则由以下代码可以得到一个小于0的值：

#include <stdio.h>
int main(void) {
    int x = 0xFFFF;
    printf("%d %X\n", x * x, x * x);
    return 0;
}

其输出为 -131071 FFFE0001，即我们算出了一个小于0的 x * x。这其实取决于 $x^2$ 二进制表示的第 $w-1$ 位，只要它是1就可以得到这样一个正溢出的效果。

乘法和除法的优化

从机器的水平上，乘法和除法是非常消耗时间的。乘法大约需要10个时钟周期，而除法则需要30多个。与此相比，加减和位运算则都只需要1个时钟周期。所以将乘法和除法优化为移位和加减将让程序执行的时间大大减少。

在十进制中，一次向左移位就意味着将原来的数乘以10。计算机中使用二进制，同理可得向左移一位就是将原来的数乘以2。假设现在我们有整数 $x$ 和常数 $y$ ，要计算 $x\cdot y$ 。若 $y=2^k$ ，那么 x * y 和 x << k 的值完全相等。我们知道，$y$ 可以被表示为一个二进制数 $(y_{w-1}\cdots y_1y_0)_2$ ，因此我们有：
$$
y=\sum_{i=0}^{w - 1}y_i2^i
$$
所以可以把其中为1的位都提出来，依次移位再相加。例如要计算 x * 14，而 $14=2^3+2^2+2^1$ 。所以这个运算可以被优化成 (x << 3) + (x << 2) + (x << 1)。又 $14=2^4-2^1$，它也可以被优化为 (x << 4) - (x << 1)。这一特性可以被用于解决 LeetCode 29: Divide two integers。

浮点数

浮点数是对形如 $V=x\times 2^y$ 的有理数进行编码的方案。这里说是有理数，是因为有限位的 $p$ 进制小数只能表示出有理数。这一种存储方案使我们可以对很小和很大的数进行方便的运算。

二进制小数的表示

一般地，对于一个 $p$ 进制的小数 $V$，我们可以将其表示为如下形式：
$$
V=\left(b_mb_{m-1}\cdots b_2b_1b_0.b_{-1}b_{-2}\cdots b_{-n+1}b_{-n}\right)_p
$$
其中，对 $-n\leq i\leq m$，均有 $0\leq b_i<p$，而 $b_i$ 的权重为 $p^{i}$。故有：
$$
V=\sum_{i=-n}^{m}b_ip^i
$$
特别地，当 $p=2$ 时，就可以得到一个二进制小数了。

IEEE浮点数

如何用一段二进制码来表示一个浮点数是一个非常重要的问题。为此 IEEE（电气和电子工程师协会）制订了浮点数的编码标准。显而易见地，用越多的字节来编码浮点数，我们就可以获得更广的表示范围和更高的精度。IEEE 定义了单精度浮点数（4字节）和双精度浮点数（8字节）。

IEEE 标准是这样的。对于一个浮点数 $V$，我们将它表示为 $V=(-1)^s\times M\times 2^E$ 的形式。其中 $s$ 称为符号 (sign)，用一位0或1来表示。$M$ 称为尾数 (significand)，它是一个二进制小数。$E$ 称为阶码 (exponent)，简单理解就是指数。将这三段拼在一起，就成为了一个 IEEE 浮点数的二进制表达。因此，假如用 $w$ 位来表达这个浮点数，就需要将这段空间划分为三段，方案如下：

最左边的1位为符号位 $s$。
阶码字段 $k$ 位，编码阶码 $E$。
$n$ 位小数字段，编码尾数 $M$。

在单精度浮点数中，$k=8,n=23$；双精度浮点数中，$k=11,n=52$。在了解这个编码方案后我们首先发现的问题就是如何处理0。由于有独立的符号位，可能出现 $+0$ 和 $-0$ 两种。这也是 IEEE 浮点数的一个特性。依据阶码的情况，IEEE 将浮点数分为以下三种：

规格化的值：$E\neq 0$ 且 $E\neq 2^k-1$。
非规格化的值：$E=0$。
特殊值：$E=2^k-1$。

规格化的值

在规格化的值中，阶码字段 $E$ 以无符号数的形式来表示一个有符号数（因为阶码确实需要负数，但补码用着不方便），因此会产生一个偏置 (bias)。我们用 $B$ 来表示这个偏置量，$B=2^{k-1}-1$。因此，若 $E$ 的无符号数对应值是 $e$，那么 $E=e-B$。

小数字段被解释为小数值 $f$，其中 $f\in [0,1)$。这里 $f=M-1$。$f$ 的二进制表示为 $0.f_{n-1}\cdots f_1f_0$。其实在这里 $V$ 就是被表示成了二进制下的科学记数法，前面被乘的部分 $M$ 应该满足 $1\leq M<2$，因此一定有一位1。由于是二进制，这里小数点前面一位只可能是1，为我们的编码省下了一位。

非规格化的值

当阶码字段为全0时，阶码值 $E=1-B$。这里多出来的1为非规格化的值与规格化的值无缝衔接提供了必要的保障。此时 $M=f$，没有开头隐含的1。这为我们表示数字 $0$ 提供了可能。它表示非常接近0的那些数。

特殊值

特殊值的阶码字段为全1。当小数域为全0时，它表示无穷。$s=0$ 时为 $+\infty$，$s=1$ 时为 $-\infty$。它可以表示溢出的结果。而当小数域不是全0，它表示 NaN (Not a Number)，比如 $\sqrt{-1}$ 。

这样的表示方法提供了极大的运算便利，即小数段的进位一旦溢出，恰好会落入阶码字段，这是一个非常神奇的巧合。

浮点数的舍入

由于二进制小数不能精确地表达十进制小数的值，它需要进行适当地舍入(rounding)。计算机中的舍入和我们日常所说的“四舍五入”是不太一样的。IEEE 定义了向偶数舍入、向零舍入、向下舍入和向上舍入四种舍入方式。首先我们解释后三种。向下舍入和向上舍入分别表示下取整和上取整。向零舍入则是对正数向下舍入，而对负数向上舍入。

向偶数舍入的基本原则是“四舍六入五取偶”。即1.5和2.5保留整数均为2，因为2是偶数。而2.51保留整数则应该为3，因为2.51并不会是2和3之间的正中间值。如果所有的5都要进一的话，最终的平均值计算下来很有可能会偏大。因此向偶数舍入可以在统计上保持平均值的稳定。

相似地，在二进制小数中，我们认为0是偶数，1是奇数，而如果需要保留的最低有效位后是 $1000\cdots$ 这样的串，那么在舍入时将在最低有效位取偶数。举例如下（保留小数点后2位）：

$10.00110 \approx 10.01$
$10.00011 \approx 10.00$
$10.11100 \approx 11.00$
$10.10100 \approx 10.10$

观察以上小数，从小数点后第3位起将被舍入。若小数点后第3–5位组成 100 串，则需要对小数点后第2位取偶，因为它们可能是上下两个可能值的正中间值。

小结

本章对于信息在计算机中的存储形式做了深度讲解。虽然知识点总结出来不多，但是还是需要大量的手算和练习去对布尔代数和位运算有基本的把握。由于存储空间的有限和运算精度的有限，计算机并不总能得到我们想要的答案。从这一章中可以找到以往编程中出现过的各种不能理解的错误，也可以学到一些位运算的奇技淫巧。大量的练习和实践仍然是掌握知识最重要的途径。