第五章 更多的位与字节

作者：Allen B. Downey

原文：Chapter 5 More bits and bytes

译者：飞龙

协议：CC BY-NC-SA 4.0

5.1 整数的表示

你可能知道计算机以二进制表示整数。对于正数，二进制的表示法非常直接。例如，十进制的5表示成二进制是0b101。

对于负数，最清晰的表示法使用符号位来表明一个数是正数还是负数。但是还有另一种表示法，叫做“补码”（two’s complement），它更加普遍，因为它和硬件配合得更好。

为了寻找一个负数-x的补码，需要找到x的二进制表示，将所有位反转，之后加上1。例如，要表示-5（十进制），要先从5（十进制）开始，如果将其写成8位的形式它是0b0000 0101。将所有位反转并加1会得到0b1111 1011。

在补码中，最左边的位相当于符号位。正数中它是0，负数中它是1。

为了将8位的数值转换为16位，我们需要对正数添加更多的0，对负数添加更多的1。实际上，我们需要将符号位复制到新的位上，这个过程叫做“符号扩展”。

在C语言中，除非你用unsigned声明它们，所有整数类型都是有符号的（能够表示正数和负数）。它们之间的差异，以及这个声明如此重要的原因，是无符号整数上的操作不使用符号扩展。

5.2 按位运算

学习C语言的人有时会对按位运算&和|感到困惑。这些运算符将整数看做位的向量，并且在相应的位上执行逻辑运算。

例如，&执行“且”运算。如果两个操作数都为1结果为1，否则为0。下面是一个在两个4位数值上执行&运算的例子：

  1.   1100
  2. & 1010
  3.   ----
  4.   1000

C语言中，这意味着表达式12 & 10值为8。

与之相似，|执行“或”运算，如果两个操作数至少一个为1结果为1，否则为0。

  1.   1100
  2. | 1010
  3.   ----
  4.   1110

所以表达式12 | 10值为14。

最后，^运算符执行“异或”运算，如果两个操作数有且仅有一个为1，结果为1。

  1.   1100
  2. ^ 1010
  3.   ----
  4.   0110

所以表达式12 ^ 10值为6。

通常，&用于清除位向量中的一些位，|用于设置位，^用于反转位。下面是一些细节：

清除位：对于任何x，x & 0值为0，x & 1值为x。所以如果你将一个向量和3做且运算，它只会保留最右边的两位，其余位都置为0。

  1.   xxxx
  2. & 0011
  3.   ----
  4.   00xx

在这个语境中，3叫做“掩码”，因为它选择了一些位，并屏蔽了其余的位。

设置位：与之相似，对于任何x，x | 0值为x，x | 1值为1。所以如果你将一个向量与3做或运算，它会设置右边两位，其余位不变。

  1.   xxxx
  2. | 0011
  3.   ----
  4.   xx11

反转位：最后，如果你将一个向量与3做异或运算，它会反转右边两位，其余位不变。作为一个练习，看看你能否使用^计算出12的补码。提示：-1的补码表示是什么？

C语言同时提供了移位运算符，<<和>>，它可以将位向左或向右移。向左每移动一位会使数值加倍，所以5 << 1为10，5 << 2为20。向右每移动一位会使数值减半（向下取整），所以5 >> 1为2，2 >> 1为1。

5.3 浮点数的表示

浮点数使用科学计数法的二进制形式来表示。在十进制的形式中，较大的数字写成系数与十的指数相乘的形式。例如，光速大约是2.998 * 10 ** 8米每秒。

大多数计算机使用IEEE标准来执行浮点数运算。C语言的float类型通常对应32位的IEEE标准，而double通常对应64位的标准。

在32位的标准中，最左边那位是符号位，s。接下来的8位是指数q，最后的23位是系数c。浮点数的值为：

  1. (-1) ** s * c * 2 ** q

这几乎是正确的，但是有一点例外。浮点数通常为规格化的，所以小数点前方有一个数字。例如在10进制中，我们通常使用2.998 * 10 ** 8而不是2998 * 10 ** 5，或者任何其它等价的表示。在二进制中，规格化的浮点数总是在二进制小数点前有一个数字1。由于这个位置上的数字永远是1，我们可以将其从表示中去掉以节省空间。

例如，十进制的13表示为0b1101，在浮点数中，它就是1.101 * 2 ** 3。所以指数为3，系数储存为101（加上20个零）。

这几乎是正确的，但是指数以“偏移”储存。在32位的标准中，偏移是127，所以指数3应该储存为130。

为了在C中对浮点数打包和解包，我们可以使用联合体和按位运算，下面是一个例子：

  1. union {
  2.     float f;
  3.     unsigned int u;
  4. } p;
  6. p.f = -13.0;
  7. unsigned int sign = (p.u >> 31) & 1;
  8. unsigned int exp = (p.u >> 23) & 0xff;
  10. unsigned int coef_mask = (1 << 23) - 1;
  11. unsigned int coef = p.u & coef_mask;
  13. printf("%d\n", sign);
  14. printf("%d\n", exp);
  15. printf("0x%x\n", coef);

这段代码位于这本书的仓库的float.c中。

联合体可以让我们使用p.f储存浮点数，之后将使用p.u当做无符号整数来读取。

为了获取符号位，我们需要将其右移31位，之后使用1位的掩码选择最右边的位。

为了获取指数，我们需要将其右移23位，之后选择最右边的8位（十六进制值0xff含有8个1）。

为了获取系数，我们需要解压最右边的23位，并且忽略掉其余位，通过构造右边23位是1并且其余位是0的掩码。最简单的方式是将1左移23位之后减1。

程序的输出如下：

  1. 1
  2. 130
  3. 0x500000

就像预期的那样，负数的符号位为1。指数是130，包含了偏移。而且系数是101带有20个零，我用十六进制将其打印了出来。

作为一个练习，尝试组装或分解double，它使用了64位的标准。请见IEEE浮点数的维基百科。

5.4 联合体和内存错误

C的联合体有两个常见的用处。一个是就是在上一节看到的那样，用于访问数据的二进制表示。另一个是储存不同形式的数据。例如，你可以使用联合体来表示一个可能为整数、浮点、复数或有理数的数值。

然而，联合体是易于出错的，这完全取决于你，作为一个程序员，需要跟踪联合体中的数据类型。如果你写入了浮点数然后将其读取为整数，结果通常是无意义的。

实际上，如果你错误地读取内存的某个位置，也会发生相同的事情。其中一种可能的方式是越过数组的尾部来读取。

我会以这个函数作为开始来观察所发生的事情。这个函数在栈上分配了一个数组，并且以0到99填充它。

  1. void f1() {
  2.     int i;
  3.     int array[100];
  5.     for (i=0; i<100; i++) {
  6.         array[i] = i;
  7.     }
  8. }

接下来我会定义一个创建小型数组的函数，并且故意访问在开头之前和末尾之后的元素：

  1. void f2() {
  2.     int x = 17;
  3.     int array[10];
  4.     int y = 123;
  6.     printf("%d\n", array[-2]);
  7.     printf("%d\n", array[-1]);
  8.     printf("%d\n", array[10]);
  9.     printf("%d\n", array[11]);
  10. }

如果我一次调用f1和f2，结果如下：

  1. 17
  2. 123
  3. 98
  4. 99

这里的细节取决于编译器，它会在栈上排列变量。从这些结果中我们可以推断，编译器将x和y放置到一起，并位于数组“下方”（低地址处）。当我们越过数组的边界读取时，似乎我们获得了上一个函数调用遗留在栈上的数据。

这个例子中，所有变量都是整数，所以比较容易弄清楚其原理。但是通常当你对数组越界读取时，你可能会读到任何类型的值。例如，如果我修改f1来创建浮点数组，结果就是：

  1. 17
  2. 123
  3. 1120141312
  4. 1120272384

最后两个数值就是你将浮点数解释为整数的结果。如果你在调试时遇到这种输出，你就很难弄清楚发生了什么。

5.5 字符串的表示

字符串有时也会有相关的问题。首先，要记住C的字符串是以空字符结尾的。当你为字符串分配空间时，不要忘了末尾额外的字节。

同样，要记住C字符串中的字母和数字都编码为ASCII码。数字0~9的ASCII码是48~57，而不是0~9。ASCII码的0是NUL字符，用于标记字符串的末尾。ASCII码的1~9是用于一些通信协议的特殊字符。ASCII码的7是响铃，在一些终端中，打印它们会发出声音。

'A'的ASCII码是65，'a'是97，下面是它们的二进制形式：

  1. 65 = b0100 0001
  2. 97 = b0110 0001

细心的读者会发现，它们只有一位的不同。这个规律对于其余所有字符都适用。从右数第六位起到“大小写”位的作用，0表示大写字母，1表示小写字母。

作为一个练习，编写一个函数，接收字符串并通过反转第六位将小写字符转换成大写字母。作为一个挑战，你可以通过一次读取字符串的32位或64位而不是一个字符使它更快。如果字符串的长度是4或8字节的倍数，这个优化会容易实现一些。

如果你越过字符串的末尾来读取，你可能会看到奇怪的字符。反之，如果你创建了一个字符串，之后无意中将其作为整数或浮点读取，结果也难以解释。

例如，如果你运行：

  1. char array[] = "allen";
  2. float *p = array;
  3. printf("%f\n", *p);

你会发现我的名字的前8个字符的ASCII表示，可以解释为一个双精度的浮点，它是69779713878800585457664。