本文記錄《深入理解計算機系統》第3版中第2章信息的表示和處理的一些知識點。

第2章 信息的表示和處理

信息存儲

32 or 64位程序

大多數 64 位機器也可以運行為 32 位機器編譯的程序，這是一種向后兼容。因此，舉例來說，當程序用如下偽指令編譯后

gcc -m32 prog.c

該程序就可以在 32 位或 64 位機器上正確運行。另一方面，若程序用下述偽指令編譯

gcc -m64 prog.c

那就只能在 64 位機器上運行。

因此，將程序稱為“ 32 位程序”或“ 64 位程序”時，區別在于該程序是如何編譯的，而不是其運行的機器類型。

大端法和小端法

最低有效字節在最前面的方式，稱為小端法（little endian） 。最高有效字節在最前面的方式，稱為大端法（big endian）。假設變量 x 的類型為int，位于地址 0x100 處，它的十六進制值為 0x01234567 。地址范圍 0x100 ～ 0x103 的字節順序依賴于機器的類型：

邏輯右移與算術右移

一般而言，機器支持兩種形式的右移：邏輯右移和算術右移。邏輯右移在左端補個 0 。算術右移是在左端補個最高有效位的值。

C 語言標準并沒有明確定義對于有符號數應該使用哪種類型的右移一一算術右移或者邏輯右移都可以。不幸地，這就意味著任何假設一種或者另一種右移形式的代碼都可能會遇到可移植性問題。然而，實際上，幾乎所有的編譯器/機器組合都對有符號數使用算術右移，且許多程序員也都假設機器會使用這種右移。另一方面，對于無符號數，右移必須是邏輯的。

整數表示

64位整型取值范圍

編碼方式

不同數值類型編碼方式是不一樣的，尤其是無符號整數和有符號整數之間

無符號整數編碼

無符號整數用無符號整數編碼，無符號數編碼定義如下：

對向量\(\vec{x} = [x_{w-1}, x_{w-2}, \cdots, x_{0}]\):

\(B2U_{4}([1111]) = 1\cdot 2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = 8 + 4 + 2 + 1 = 15\)

\(w\)位的無符號整數最大值為\(U\max_w \doteq \sum_{i=0}^{w-1} 2^{i} = 2^w -1\)。

補碼編碼

最常見的有符號數的計算機表示方式就是補碼形式（Two's complement）。在這個定義中，將字的最高有效位解釋為負權。補碼編碼的定義如下：

對向量\(\vec{x} = [x_{w-1}, x_{w-2}, \cdots, x_{0}]\):

最高有效位\(x_{w-1}\)稱為符號位。

\(B2T_{4}([1111]) = -1\cdot 2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = -8 + 4 + 2 + 1 = -1\)

\(w\)位的有符號整數最小值為\(T\min_w \doteq -2^{w-1}\)，最大值為\(T\max_w \doteq \sum_{i=0}^{w-2} 2^{i} = 2^{w-1} -1\)。

反碼和原碼

有符號數還有另外兩種標準表示方法（現代機器基本不用這兩種）。

反碼（Ones' Complement）：除了最高有效位的權是\(-(2^{w-1} - 1)\)而不是\(-2^{w-1}\)，和補碼相同：

原碼（Sign-Magnitude）：最高有效位是符號位，用來確定剩下的位應該取負權還是正權：

這兩種表示方法都有一個奇怪的屬性，那就是對于數字 0 有兩種不同的編碼方式。這兩種表示方法，把[ 00...0 ]都解釋為+ 0 。而值-0 在原碼中表示為[10...0 ]，在反碼中表示為[ 11...1]。雖然過去生產過基于反碼表示的機器，但是幾乎所有的現代機器都使用補碼。

注意補碼（Two's Complement）和反碼（Ones' complement）的名稱中的撇號的位置是不同的（理解這個英文的區別能更好的理解補碼和反碼）。術語補碼來源于這樣一個情況，對于非負數\(x\)，用\(2^w - x\)來計算\(-x\)的表示。術語反碼來源于這樣一個屬性，用\([ 111\cdots1] - x\)來計算\(-x\)的反碼表示。

整數計算

無符號數的逆元

對滿足\(0 \leq x < 2^w\)的任意\(x\)，其\(w\)位的無符號逆元\(- _{w}^{u}x\) 由下式給出：

意思就是任何一個數，都能找到另外一個數讓他們兩加起來的位全為0。

補碼的非

對滿足 \(TMin_w \leq x \leq TMax_w\)的\(x\)，其補碼的非 \(- _{w}^{t}x\)由下式給出：

意思就是任何一個數，都能找到另外一個數讓他們兩加起來的位全為0。

對C來說，任何一個數都滿足 -x = ~x + 1。

浮點數

IEEE浮點表示

IEEE 浮點標準用\(V = (-1) ^{s} \times M \times 2^E\)的形式來表示一個數:

• 符號 (sign) \(s\)決定這數是負數。
• 尾數 (significand) \(M\) 是一個二進制小數，它的范圍是\(1 \sim 2-\epsilon\)，或者是 \(0 \sim 1 - \epsilon\) 。
• 階碼（exponent）\(E\) 的作用是對浮點數加權，這個權重是 2 的 \(E\) 次冪（可能是負數）。

將浮點數的位表示劃分為三個字段，分別對這些值進行編碼：

• 一個單獨的符號位\(s\)；
• \(k\)位的階碼字段\(exp = e_{k-1}\cdots e_{1}e_{0}\)編碼階碼\(E\)；
• \(n\)位小數字段\(frac = f_{n-1}\cdots f_{1} f_{0}\)編碼尾數\(M\)， 編碼出來的值也依賴于階碼字段的值是否等于0。

兩種最常見的格式如下圖。在單精度浮點格式（ float）中， \(s\)、 \(exp\) 和 \(frac\) 字段分別為 1 位、 8 位和 23 位，得到一個 32 位的表示。在雙精度浮點格式（ double) 中，\(s\)、 \(exp\) 和 \(frac\) 字段分別為 1 位、11 位和 52 位，得到一個 64 位的表示。

給定位表示，根據\(exp\)的值，被編碼的值可以分為三種不同的情況（最后一種情況有兩個變種）。下圖說明了對單精度格式的情況。

情況1：規格化的值

這是最普遍的情況。當 \(exp\) 的位模式既不全為 0 （數值 0 ），也不全為 1 （單精度數值為255 ，雙精度數值為 2047 ）時，都屬于這類情況。在這種情況中，階碼字段被解釋為以偏置（ biased ）形式表示的有符號整數。也就是說，階碼的值是 \(E=e—Bias\) ，其中 \(e\) 是無符號數，其位表示為\(e_{k-1}\cdots e_{1}e_{0}\) ，而\(Bias\)是一個等于\(2^{k-1} - 1\)（單精度是 127 ，雙精度是 1023 ）的偏置值。由此產生指數的取值范圍，對于單精度是\(-126 \sim +127\) ，而對于雙精度是\(-1022\sim+1023\) 。

小數字段\(frac\) 被解釋為描述小數值\(f\)，其中 \(0 \leq f < 1\) ，其二進制表示為\(0.f_{n-1}\cdots f_{1} f_{0}\)，也就是二進制小數點在最高有效位的左邊。尾數定義為 \(M = 1 + f\)。有時，這種方式也叫做隱含的以 1 開頭的 (implied leading 1) 表示，因為可以把 \(M\) 看成一個二進制表達式為 \(1.f_{n-1}f_{n-2}\cdots f_{0}\) 的數字。既然我們總是能夠調整階碼 \(E\) ，使得尾數 \(M\) 在范圍 \(1 \leq M < 2\) 之中（假設沒有溢出），那么這種表示方法是一種輕松獲得一個額外精度位的技巧。既然第一位總是等于 1 ，那么就不需要顯式地表示它。

情況2：非規格化的值

當階碼域為全 0 時，所表示的數是非規格化形式。這種情況下，階碼值是 \(E = 1 - Bias\) ，而尾數的值是\(M = f\)，也就是小數字段的值，不包含隱含的開頭的 1 。

非規格化數有兩個用途。首先，它們提供了一種表示數值 0 的方法，因為使用規格化數，我們必須總是使\(M \geq 1\)，因此就不能表示 0 。實際上，\(+0.0\)的浮點表示的位模式為全 0 ：符號位是 0 ，階碼字段全為 0 （表明是一個非規格化值），而小數域也全為 0 ，這就得到\(M = f = 0\)。令人奇怪的是，當符號位為 1 ，而其他域全為 0 時，得到值\(-0.0\) 。根據IEEE浮點格式，值\(+0.0\)和\(-0.0\)在某些方面被認為是不同的，而在其他方面是相同的。

非規格化數另外一個功能是表示那些非常接近于\(0.0\)的數。它們提供了一種屬性，稱為逐漸溢出 (gradual underflow) ，其中，可能的數值分布均勻地接近于\(0.0\)。

情況3：特殊值

最后一類數值是當指階碼全為 1 的時候出現的。當小數域全為 0 時，得到的值表示無窮。當\(s = 0\)時是\(+\infty\)，\(s = 1\)時是\(-\infty\)。當我們把兩個非常大的數相乘，或者除以零，無窮能夠表示溢出的結果。當小數域為非零時，結果值被稱為 "NaN ”，即“不是一個數 (Not a Number) ”的縮寫。一些運算的結果不能是實數或無窮，就會返回這樣的 NaN 值，比如當計算\(\sqrt{-1}\)或\(\infty - \infty\)時。在某些應用中，表示未初始化的數據時，它們也很有用處。