操作系统思考 中文版

 主页   资讯   文章   代码   电子书 

第五章 更多的位与字节

作者: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位数值上执行&运算的例子:

  1100
& 1010
  ----
  1000

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

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

  1100
| 1010
  ----
  1110

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

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

  1100
^ 1010
  ----
  0110

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

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

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

  xxxx
& 0011
  ----
  00xx

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

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

  xxxx
| 0011
  ----
  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) ** 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中对浮点数打包和解包,我们可以使用联合体和按位运算,下面是一个例子:

union {
    float f;
    unsigned int u;
} p;

p.f = -13.0;
unsigned int sign = (p.u >> 31) & 1;
unsigned int exp = (p.u >> 23) & 0xff;

unsigned int coef_mask = (1 << 23) - 1;
unsigned int coef = p.u & coef_mask;

printf("%d\n", sign);
printf("%d\n", exp);
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
130
0x500000

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

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

5.4 联合体和内存错误

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

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

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

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

void f1() {
    int i;
    int array[100];

    for (i=0; i<100; i++) {
        array[i] = i;
    }
}

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

void f2() {
    int x = 17;
    int array[10];
    int y = 123;

    printf("%d\n", array[-2]);
    printf("%d\n", array[-1]);
    printf("%d\n", array[10]);
    printf("%d\n", array[11]);
}

如果我一次调用f1f2,结果如下:

17
123
98
99

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

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

17
123
1120141312
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,下面是它们的二进制形式:

65 = b0100 0001
97 = b0110 0001

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

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

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

例如,如果你运行:

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

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