第五章 更多的位與字節(jié)

作者：Allen B. Downey

原文：Chapter 5 More bits and bytes

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

5.1 整數(shù)的表示

你可能知道計算機(jī)以二進(jìn)制表示整數(shù)。對于正數(shù)，二進(jìn)制的表示法非常直接。例如，十進(jìn)制的5表示成二進(jìn)制是0b101。

對于負(fù)數(shù)，最清晰的表示法使用符號位來表明一個數(shù)是正數(shù)還是負(fù)數(shù)。但是還有另一種表示法，叫做“補(bǔ)碼”（two's complement），它更加普遍，因?yàn)樗陀布浜系酶谩?/p>

為了尋找一個正數(shù)的補(bǔ)碼，-x，需要找到x的二進(jìn)制表示，將所有位反轉(zhuǎn)，之后加上1。例如，要表示十進(jìn)制的-5，要先從十進(jìn)制的5開始，如果將其寫成8位的形式它是0b0000 0101。將所有位反轉(zhuǎn)并加以會得到0b1111 1011。

在補(bǔ)碼中，最左邊的位相當(dāng)于符號位。正數(shù)中它是0，負(fù)數(shù)中它是1。

為了將8位的數(shù)值轉(zhuǎn)換為16位，我們需要對正數(shù)添加更多的0，對負(fù)數(shù)添加更多的1。實(shí)際上，我們需要將符號位復(fù)制到新的位上，這個過程叫做“符號擴(kuò)展”。

在C語言中，除非你用unsigned聲明它們，所有整數(shù)類型都是有符號的（能夠表示正數(shù)和負(fù)數(shù)）。它們之間的差異，以及這個聲明如此重要的原因，是無符號整數(shù)上的操作不使用符號擴(kuò)展。

5.2 按位運(yùn)算

學(xué)習(xí)C語言的人有時會對按位運(yùn)算&和|感到困惑。這些運(yùn)算符將整數(shù)看做位的向量，并且在相應(yīng)的位上執(zhí)行邏輯運(yùn)算。

例如，&執(zhí)行“且”運(yùn)算。如果兩個操作數(shù)都為1結(jié)果為1，否則為0。下面是一個在兩個4位數(shù)值上執(zhí)行&運(yùn)算的例子：

  1100
& 1010
  ----
  1000

C語言中，這意味著表達(dá)式12 & 10值為8。

與之相似，|執(zhí)行“或”運(yùn)算，如果兩個操作數(shù)至少一個為1結(jié)果為1，否則為0。

  1100
| 1010
  ----
  1110

所以表達(dá)式12 | 10值為14。

最后，^運(yùn)算符執(zhí)行“異或”運(yùn)算，如果兩個操作數(shù)其中有一個為1，而不是全部為1，結(jié)果為1。

  1100
^ 1010
  ----
  0110

所以表達(dá)式12 ^ 10值為6。

通常，&用于清除位向量中的一些位，|用于設(shè)置位，^用于反轉(zhuǎn)位。下面是一些細(xì)節(jié)：

清除位：對于任何x，x & 0值為0，x & 1值為x。所以如果你將一個向量和3做且運(yùn)算，它只會保留最右邊的兩位，其余位都置為0。

  xxxx
& 0011
  ----
  00xx

在這個語境中，3叫做“掩碼”，因?yàn)樗x擇了一些位，并屏蔽了其余的位。

設(shè)置位：與之相似，對于任何x，x | 0值為x，x | 1值為1。所以如果你將一個向量與3做或運(yùn)算，它會設(shè)置右邊兩位，其余位不變。

  xxxx
| 0011
  ----
  xx11

反轉(zhuǎn)位：最后，如果你將一個向量與3做異或運(yùn)算，它會反轉(zhuǎn)右邊兩位，其余位不變。作為一個練習(xí)，看看你能否使用^計算出12的補(bǔ)碼。提示：-1的補(bǔ)碼表示是什么？

C語言同時提供了移位運(yùn)算符，<<和>>，它可以將位向左或向右移。向左每移動一位會使數(shù)值加倍，所以5 << 1為10，5 << 2為20。向右每移動一位會使數(shù)值減半（向下取整），所以5 >> 1為2，2 >> 1為1。

5.3 浮點(diǎn)數(shù)的表示

浮點(diǎn)數(shù)使用科學(xué)計數(shù)法的二進(jìn)制形式來表示。在十進(jìn)制的形式中，較大的數(shù)字寫成系數(shù)與十的指數(shù)相乘的形式。例如，光速大約是2.998 * 10 ** 8米每秒。

大多數(shù)計算機(jī)使用IEEE標(biāo)準(zhǔn)來執(zhí)行浮點(diǎn)數(shù)運(yùn)算。C語言的float類型通常對應(yīng)32位的IEEE標(biāo)準(zhǔn)，而double通常對應(yīng)64位的標(biāo)準(zhǔn)。

在32位的標(biāo)準(zhǔn)中，最左邊那位是符號位，s。接下來的8位是指數(shù)q，最后的23位是系數(shù)c。浮點(diǎn)數(shù)的值為：

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

這幾乎是正確的，但是有一點(diǎn)例外。浮點(diǎn)數(shù)通常為規(guī)格化的，所以小數(shù)點(diǎn)前方有一個數(shù)字。例如在10進(jìn)制中，我們通常使用2.998 * 10 ** 8而不是2998 * 10 ** 5，或者任何其它等價的表示。在二進(jìn)制中，規(guī)格化的浮點(diǎn)數(shù)通常在二進(jìn)制小數(shù)點(diǎn)前有一個數(shù)字1。由于這個位置上的數(shù)字永遠(yuǎn)是1，我們可以將其從表示中去掉以節(jié)省空間。

例如，十進(jìn)制的13表示為0b1101，在浮點(diǎn)數(shù)中，它就是1.011 * 2 ** 3。所以指數(shù)為3，系數(shù)儲存為101（加上20個零）。

這幾乎是正確的，但是指數(shù)以“偏移”儲存。在32位的標(biāo)準(zhǔn)中，偏移是127，所以指數(shù)3應(yīng)該儲存為130。

為了在C中對浮點(diǎn)數(shù)打包和解包，我們可以使用聯(lián)合體和按位運(yùn)算，下面是一個例子：

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中。

聯(lián)合體可以讓我們使用p.f儲存浮點(diǎn)數(shù)，之后將使用p.u當(dāng)做無符號整數(shù)來讀取。

為了獲取符號位，我們需要將其右移31位，之后使用1位的掩碼選擇最右邊的位。

為了獲取指數(shù)，我們需要將其右移23位，之后選擇最右邊的8位（十六進(jìn)制值0xff含有8個1）。

為了獲取系數(shù)，我們需要解壓最右邊的23位，并且忽略掉其余位，通過構(gòu)造右邊23位是1并且其余位是0的掩碼。最簡單的方式是將1左移23位之后減1。

程序的輸出如下：

1
130
0x500000

就像預(yù)期的那樣，負(fù)數(shù)的符號位為1。指數(shù)是130，包含了偏移。而且系數(shù)是101帶有20個零，我用十六進(jìn)制將其打印了出來。

作為一個練習(xí)，嘗試組裝或分解double，它使用了64位的標(biāo)準(zhǔn)。請見IEEE浮點(diǎn)數(shù)的維基百科。

5.4 聯(lián)合體和內(nèi)存錯誤

C的聯(lián)合體有兩個常見的用處。一個是就是在上一節(jié)看到的那樣，用于訪問數(shù)據(jù)的二進(jìn)制表示。另一個是儲存不同形式的數(shù)據(jù)。例如，你可以使用聯(lián)合體來表示一個可能為整數(shù)、浮點(diǎn)、復(fù)數(shù)或有理數(shù)的數(shù)值。

然而，聯(lián)合體是易于出錯的，這完全取決于你，作為一個程序員，需要跟蹤聯(lián)合體中的數(shù)據(jù)類型。如果你寫入了浮點(diǎn)數(shù)然后將其讀取為整數(shù)，結(jié)果通常是無意義的。

實(shí)際上，如果你錯誤地讀取內(nèi)存的某個位置，也會發(fā)生相同的事情。其中一種可能的方式是越過數(shù)組的尾部來讀取。

我會以這個函數(shù)作為開始來觀察所發(fā)生的事情。這個函數(shù)在棧上分配了一個數(shù)組，并且以0到99填充它。

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

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

接下來我會定義一個創(chuàng)建小型數(shù)組的函數(shù)，并且故意訪問在開頭之前和末尾之后的元素：

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]);
}

如果我一次調(diào)用f1和f2，結(jié)果如下：

17
123
98
99

這里的細(xì)節(jié)取決于編譯器，它會在棧上排列變量。從這些結(jié)果中我們可以推斷，編譯器將x和y放置到一起，并位于數(shù)組“下方”（低地址處）。當(dāng)我們越過數(shù)組的邊界讀取時，似乎我們獲得了上一個函數(shù)調(diào)用遺留在棧上的數(shù)據(jù)。

這個例子中，所有變量都是整數(shù)，所以比較容易弄清楚其原理。但是通常當(dāng)你對數(shù)組越界讀取時，你可能會讀到任何類型的值。例如，如果我修改f1來創(chuàng)建浮點(diǎn)數(shù)組，結(jié)果就是：

17
123
1120141312
1120272384

最后兩個數(shù)值就是你將浮點(diǎn)數(shù)解釋為整數(shù)的結(jié)果。如果你在調(diào)試時遇到這種輸出，你就很難弄清楚發(fā)生了什么。

5.5 字符串的表示

字符串有時也會有相關(guān)的問題。首先，要記住C的字符串是以空字符結(jié)尾的。當(dāng)你為字符串分配空間時，不要忘了末尾額外的字節(jié)。

同樣，要記住C字符串中的字母和數(shù)字都編碼為ASCII碼。數(shù)字0_{9的ASCII碼是48}57，而不是0_{9。ASCII碼的0是`NUL`字符，用于標(biāo)記字符串的末尾。ASCII碼的1}9是用于一些通信協(xié)議的特殊字符。ASCII碼的7是響鈴，在一些終端中，打印它們會發(fā)出聲音。

'A'的ASCII碼是65，'a'是97，下面是它們的二進(jìn)制形式：

65 = b0100 0001
97 = b0110 0001

細(xì)心的讀者會發(fā)現(xiàn)，它們只有一位的不同。這個規(guī)律對于其余所有字符都適用。從右數(shù)第六位起到“大小寫”位的作用，0表示大寫字母，1表示小寫字母。

作為一個練習(xí)，編寫一個函數(shù)，接收字符串并通過反轉(zhuǎn)第六位將小寫字符轉(zhuǎn)換成大寫字母。作為一個挑戰(zhàn)，你可以通過一次讀取字符串的32位或64位而不是一個字符使它更快。如果字符串的長度是4或8字節(jié)的倍數(shù)，這個優(yōu)化會容易實(shí)現(xiàn)一些。

如果你越過字符串的末尾來讀取，你可能會看到奇怪的字符。反之，如果你創(chuàng)建了一個字符串，之后無意中將其作為整數(shù)或浮點(diǎn)讀取，結(jié)果也難以解釋。

例如，如果你運(yùn)行：

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

你會發(fā)現(xiàn)我的名字的前8個字符的ASCII表示，可以解釋為一個雙精度的浮點(diǎn)，它是69779713878800585457664。