01 Representing and Manipulating Information

信息的表示

电子计算机用高电平表示1，低电平表示0，由此实现对一个二进制位(bit)的存储和运算。

8个二进制位连续排列构成一个字节(byte)。

字长(word)取决于具体的计算机体系结构的设计，早些年常用的设计是“1 word = 32 bit = 4 byte”，这样的机器称为“32位计算机”。由于在设计体系结构时，所有地址都用一个字长表示与存储，每个地址存储一个字节，这就意味着32位机器最多只有表示$2^{32}$个不同的地址，因此内存空间最多只有$4\text{GB}$。因此，如今的大多数机器都是64位的（64位机器的内存空间最多能达到$16777216\text{TB}$）。

整数的表示

尽管C语言标准没有规定每种类型的变量所占的空间大小，但操作系统一般会为每种类型分配固定的空间大小。空间大小的单位是byte（不是word）。例如，char占1 byte，int占4 byte，double占8 byte等等。

整数的存储

让我们以int为例。一个int占4 byte，相当于32 bit。为了方便描述，我们常用16进制描述，这样描述一个int恰好需要8个16进制位，例如0x01234567。计算机的内存可以看作一个庞大的数组，数组的下标就是地址。以32位机器为例，我们用4个16进制位表示一个地址。我们通常会说“int 0x01234567被存储在地址0x0100处”，这句话的意思是这个4字节的整数被存储在0x0100，0x0101，0x0102，0x0103这四个连续的地址上（严格来说，这里的连续指的是虚拟内存意义下的连续，在物理内存意义上绝大多数情况也是连续的）。对于0x01234567，主流的计算机都会把67存储在0x0100，把45存储在0x0101，把23存储在0x0102，把01存储在0x0103，这称为小端法(little endian)。也有的计算机会反过来把01存储在0x0100，依此类推，这样的做法称为大端法(big endian)。（现在的很多系统兼容这两种表示方法，称为双端法(bi-endian)）。

补码

在计算机中表示整数时，需要区分有符号数(signed)与无符号数(unsigned)。在C语言中，int即代表signed int，unsigned int表示无符号的整数。一个unsigned int也占4 byte，此时从低到高第$i$位的进制权重就是$2^{i-1}$，最高位的权重就是$2^{31}$。而在有符号的int中，除了最高位以外从低到高第$i$位的进制权重依然是$2^{i-1}$，但最高位的权重为$-2^{31}$，是unsigned int中最高位权重的相反数。因此有符号int中最高位通常被称为“符号位”，因为只要最高位为1，就一定表示负数。

有符号整数最高位权重的设计非常精妙，这样的设计使得计算机只需要一个“加法器”就能统一地实现无符号整数的加法和有符号整数的加法。加法器的运算规则是：从低位到高位逐位相加，逢2进1，如果最高位产生了进位则直接丢弃这个进位。对于无符号的$n$位整数，当两数相加不溢出时结果显然正确，而当溢出时会模$2^n$（这事实上实现了一个$2^n$大小的循环群）。下面我们来讨论有符号数。为了方便讨论，让我们考虑8位有符号整数的例子。整数45表示为00101101，而通过计算可以得到其相反数-45表示为11010011（此时最高位权重为$-2^7$）。可以看到，按照加法器的规则，这二者相加恰好获得00000000，也就是整数0。我们可以从数学上证明，一个正数的相反数的有符号二进制表示恰好为“按位取反再加1（加法器意义下）”，这一转换称为求“补码(two's complement)”。

符号扩展

在补码表示法下，如果一个整数原本用$n_1$位二进制存储，现在要改为$n_2$位二进制存储，该如何处理？

当$n_1<n_2$时，做符号扩展(sign extension)：若原本补码表示时最高位为$0$，扩展后的高位都补$0$；若原本补码表示时最高位为$1$，扩展后的高位都补$1$。证明：只需证明权重变化后二进制串表示的数值不变。 补$0$显然成立。补$1$时，只需证明$-2^{n_1-1}=-2^{n_2-1}+\sum\limits_{i=n_1}^{n_2-1}2^{i-1}$，成立。

当$n_1>n_2$时，做截断(truncation)：直接丢弃最高的$n_1-n_2$位。可见，截断操作是有可能改变表示的数值的。

浮点数的表示

计算机基于二进制的科学计数法来表示浮点数。任何一个浮点数$x$都可以写作$x=(-1)^s\times M \times 2^E$。因此，我们只需表示$s,M,E$这三个信息：$s$是符号位，直接用1个二进制位表示，0代表正数，1代表负数；$M$是尾数(fraction)；$E$是阶码(exponent)。

C语言中的float占4 byte（32 bit），其中符号位占1位，阶码占8位，尾数占23位；double占8 byte（64 bit），符号位占1位，阶码占11位，尾数占52位。在具体表示中，有以下几点需要特殊对待：阶码可能为负数，但一般不用补码表示，而是用偏移量表示；尾数的小数点前的那一位总是1，因此省略不表示；浮点数分为规格化数(normalized)和非规格化数(denormalized)，规格化数的阶码为1~254，非规格化数的阶码为0或255。当阶码为0时，尾数小数点前隐含的是0而不是1，同时计算时使用的真实阶码为-126；当阶码为255时，如果尾数为0则表示无穷大$\infty$，否则不表示任何数(not a number, NaN)。

Reference

Randal E. Bryant, David R. O’Hallaron, Computer Systems: A Programmer's Perspective, CMU