CSAPP-2-信息的表示和處理

如果能完全理解計(jì)算機(jī)系統(tǒng)以及它對(duì)應(yīng)用程序的影響，那么恭喜你，你走上了一條為數(shù)不多的大牛道路。

本文是深入理解計(jì)算機(jī)系統(tǒng)的第二篇文章，接著上一篇我們講解的計(jì)算機(jī)系統(tǒng)開篇-《計(jì)算機(jī)系統(tǒng)漫游》，本篇文章繼續(xù)深入，一起來(lái)學(xué)習(xí) 信息的表示和處理。

本篇文章一共分為四部分，信息存儲(chǔ)、整數(shù)的表示，整數(shù)的運(yùn)算 和 浮點(diǎn)數(shù)。

1. 信息存儲(chǔ)

程序?qū)?nèi)存視為一個(gè)非常大的字節(jié)數(shù)組，稱為虛擬內(nèi)存。內(nèi)存中的每一個(gè)字節(jié)都由一個(gè)唯一的數(shù)字來(lái)標(biāo)識(shí)，稱為它的地址，地址的集合就稱為虛擬地址空間。

每臺(tái)計(jì)算都有一個(gè)字長(zhǎng)，虛擬地址空間是以字來(lái)編碼的，所以字長(zhǎng)決定了虛擬地址空間的大小。對(duì)于一個(gè)字長(zhǎng)為 w 位的機(jī)器而言，虛擬地址的范圍為 0~2^w? -1 ,程序最多訪問?2^w? 個(gè)字節(jié)。

1.1 尋址和字節(jié)順序

對(duì)于我們?nèi)粘３绦蛑械膶?duì)象，它們?cè)趦?nèi)存中往往是多字節(jié)的，那么我們必須知道兩個(gè)規(guī)則：這個(gè)對(duì)象的地址是什么？以及內(nèi)存中如何排列這些字節(jié)？

在幾乎所有的機(jī)器上，字節(jié)都是被連續(xù)存儲(chǔ)的，對(duì)象的地址為所使用字節(jié)中最小的地址。例如，一個(gè)int類型的變量x的地址為0x100，也就是地址表達(dá)式&x 的值為0x100，x的四個(gè)字節(jié)存儲(chǔ)在內(nèi)存0x100、0x101、0x102、0x103位置。

排列表示一個(gè)對(duì)象的字節(jié)，有兩個(gè)通用的規(guī)則：

  • 大端法：最高有效字節(jié)在最前面
  • 小端法：最低有效字節(jié)在最前面
1.png

對(duì)于我們程序員來(lái)說(shuō)，機(jī)器使用的字節(jié)順序?qū)ξ覀兪遣豢梢姷模瑹o(wú)論哪種字節(jié)順序的機(jī)器，我們的程序編譯后得到的結(jié)果都是一樣的，不過(guò)有時(shí)候字節(jié)順序也會(huì)成為問題，這里不再詳述什么情況下會(huì)產(chǎn)生問題，只作學(xué)習(xí)驗(yàn)證機(jī)器的字節(jié)順序不同產(chǎn)生的不同結(jié)果。

# include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len)
{
    size_t i;
    for(i =0; i < len;i++)
        printf("%.2x",start[i]);
    printf("\n");
}

void show_int(int x) {
    show_bytes((byte_pointer) &x,sizeof(int));
}

void show_float(float x) {
    show_bytes((byte_pointer) &x,sizeof(float));
}

void show_pointer(void *x) {
    show_bytes((byte_pointer) &x,sizeof(void *));
}

void test_show_bytes(int val) {
    int ival = val;
    float fval = (float) ival;
    int *pval = &ival;
    show_int(ival);
    show_float(fval);
    show_pointer(pval);
}

int main() {
    test_show_bytes(12345);
    return 1;
}

運(yùn)行上面的c語(yǔ)言程序，得到的結(jié)果如下：

39300000
00e44046
a8e7a4c2ff7f0000

參數(shù)12345的十六進(jìn)制表示為0x00000393,結(jié)合上面的結(jié)果 39300000 說(shuō)明我的linux64是一個(gè)小端法機(jī)器。下面在放一張?jiān)诟鱾€(gè)機(jī)器測(cè)試的不同結(jié)果，更加全面的對(duì)比圖：

2.png

上圖指針 值完全不相同的原因是不同的操作系統(tǒng)使用不同的存儲(chǔ)分配規(guī)則，不過(guò)需要注意的是Linux64使用的是8字節(jié)地址。

1.2 表示字符串

C語(yǔ)言的字符串：一個(gè)以null(值為0)字符結(jié)尾的字符數(shù)組 如字符串"12345"編碼為 61 62 63 64 65 使用ASCII編碼。 linux系統(tǒng)可以使用 man ascii 命令查看ASCII編碼表。

1.3 布爾代數(shù)簡(jiǎn)介

二進(jìn)制是計(jì)算機(jī)編碼、存儲(chǔ)和操作信息的核心。 將邏輯值 TRUE 和 FALSE 編碼為1和0，能夠設(shè)計(jì)一種代數(shù)，用來(lái)研究邏輯推理的基本原則。

布爾運(yùn)算：

3.png

1.4 C語(yǔ)言中的位級(jí)運(yùn)算

事實(shí)上，我們平時(shí)代碼中寫的 | 就是OR(或)，& 就是AND(與)，~ 就是NOT（取反），^就是異或，本質(zhì)上都是按位進(jìn)行運(yùn)算的。

以下是一些對(duì)char數(shù)據(jù)類型表達(dá)式求值的例子：

4.png

正如示例說(shuō)明的那樣，確定一個(gè)位級(jí)表達(dá)式的結(jié)果最好的方法，就是將十六進(jìn)制的參數(shù)擴(kuò)展成二進(jìn)制表示并執(zhí)行二進(jìn)制運(yùn)算，然后再轉(zhuǎn)換回十六進(jìn)制。

1.5 C語(yǔ)言中的移位運(yùn)算

5.png

移位運(yùn)算右移分為：邏輯右移和算術(shù)右移。

  • 邏輯右移：在左端補(bǔ)0；
  • 算術(shù)右移：如果操作數(shù)的最高位是1則左端補(bǔ)1，如果為0則補(bǔ)0；

C語(yǔ)言中，幾乎所有的編譯器都對(duì)有符號(hào)數(shù)使用算術(shù)右移，無(wú)符號(hào)數(shù)使用邏輯右移。

Java中有明確定義，x>>k 表示算術(shù)右移k個(gè)位置，而x>>>k 會(huì)對(duì)x做邏輯右移。

這里說(shuō)明一個(gè)移位運(yùn)算有關(guān)的操作符優(yōu)先級(jí)問題：

表達(dá)式 1<<2+3<<4 ，本意是（1<<2）+(3<<4),你可能也會(huì)犯這樣的錯(cuò)誤，其實(shí)前面的表達(dá)式等價(jià)于：1<<(2+3)<<4,因?yàn)?strong>加法（減法）的優(yōu)先級(jí)比移位運(yùn)算要高。

2. 整數(shù)表示

下面的數(shù)據(jù)術(shù)語(yǔ)用來(lái)精確定義和描述計(jì)算機(jī)如何編碼和操作整數(shù)。

6.png

2.1 無(wú)符號(hào)數(shù)的編碼

假設(shè)一個(gè)整數(shù)有w位，每個(gè)位的取值即0非1。

原理：無(wú)符號(hào)數(shù)編碼的定義

對(duì)向量
\vec{x}=\left[\begin{array}{cccc}{x_{w-1},} & {x_{w-2}} & {,} & {\cdots, \quad x_{0}}\end{array}\right]
用一個(gè)函數(shù)來(lái)表示：
B 2 U_{w}(\vec{x}) \doteq \sum_{i=0}^{w-1} x_{i} 2^{i}
計(jì)算規(guī)則：
\begin{array}{l}{B 2 U_{4}([0001])=0 \cdot 2^{3}+0 \cdot 2^{2}+0 \cdot 2^{1}+1 \cdot 2^{0}=0+0+0+1=1} \\ {B 2 U_{4}([0101])=0 \cdot 2^{3}+1 \cdot 2^{2}+0 \cdot 2^{1}+1 \cdot 2^{0}=0+4+0+1=5} \\ {B 2 U_{4}([1011])=1 \cdot 2^{3}+0 \cdot 2^{2}+1 \cdot 2^{1}+1 \cdot 2^{0}=8+0+2+1=11} \\ {B 2 U_{4}([1111])=1 \cdot 2^{3}+1 \cdot 2^{2}+1 \cdot 2^{1}+1 \cdot 2^{0}=8+4+2+1=15}\end{array}

2.2 補(bǔ)碼編碼

上面介紹的是無(wú)符號(hào)編碼的表示形式，但是我們應(yīng)用中，還是希望表示負(fù)數(shù)值。最常見的有符號(hào)數(shù)計(jì)算機(jī)表示方式就是補(bǔ)碼。

原理：補(bǔ)碼編碼的定義

對(duì)向量：
\begin{aligned} \vec{x}=\left[x_{w-1}, x_{w-2},\right.&\left.\cdots, x_{0}\right] \\ & B 2 T_{w}(\vec{x}) \doteq-x_{u-1} 2^{w-1}+\sum_{i=0}^{w-2} x_{i} 2^{i} \end{aligned}

最高有效位即 x_{w-1} 也稱為符號(hào)位。符號(hào)位等于1時(shí)，表示值為負(fù)，等于0時(shí)，值為非負(fù)，下面來(lái)看實(shí)際的計(jì)算示例：

\begin{array}{l}{B 2 T_{4}([0001])=-0 \cdot 2^{3}+0 \cdot 2^{2}+0 \cdot 2^{1}+1 \cdot 2^{0}=0+0+0+1=1} \\ {B 2 T_{4}([0101])=-0 \cdot 2^{3}+1 \cdot 2^{2}+0 \cdot 2^{1}+1 \cdot 2^{0}=0+4+0+1=5} \\ {B 2 T_{4}([1011])=-1 \cdot 2^{3}+0 \cdot 2^{2}+1 \cdot 2^{1}+1 \cdot 2^{0}=-8+0+2+1=-5} \\ {B 2 T_{4}([1111])=-1 \cdot 2^{3}+1 \cdot 2^{2}+1 \cdot 2^{1}+1 \cdot 2^{0}=-8+4+2+1=-1}\end{array}?

這里讓我們一起來(lái)考慮下補(bǔ)碼所能表示的值的范圍，最小值為：T M i n_{w} \doteq-2^{w-1}?.

最大值為：T M a x_{w} \doteq \sum_{i=0}^{w-2} 2^{i}=2^{w-1}-1?

例如以長(zhǎng)度為4為例，T M i n_{4}=B 2 T_{4}([1000])=-2^{3}=-8?, 而 T M a x_{4}=B 2 T_{4}([0111])=2^{2}+2^{1}+2^{0}=4+2+1=7?

補(bǔ)碼編碼也是取值范圍內(nèi)每個(gè)數(shù)字都有唯一的w位補(bǔ)碼編碼。

2.3 有符號(hào)數(shù)和無(wú)符號(hào)數(shù)之間的轉(zhuǎn)換

原理：補(bǔ)碼轉(zhuǎn)換為無(wú)符號(hào)數(shù)

對(duì)滿足T M i n_{w} \leqslant x \leqslant T M a x_{w}? 的 x 有：
T 2 U_{w}(x)=\left\{\begin{array}{ll}{x+2^{w},} & {x<0} \\ {x,} & {x \geqslant 0}\end{array}\right.

比如，T 2 U_{16}(-12345)=-12345+2^{16}=53191? ,同時(shí) ?T 2 U_{w}(-1)=-1+2^{w}=U M a x_{w}?。

原理：無(wú)符號(hào)數(shù)轉(zhuǎn)換為補(bǔ)碼

對(duì)滿足 0 \leqslant u \leqslant U M a x_{w} 的 u 有：
U 2 T_{w}(u)=\left\{\begin{array}{ll}{u,} & {u \leqslant T \operatorname{Max}_{w}} \\ {u-2^{w},} & {u>\operatorname{TMax}_{w}}\end{array}\right.

3. 整數(shù)運(yùn)算

在我們剛剛學(xué)習(xí)計(jì)算機(jī)時(shí)，大家有沒有經(jīng)歷過(guò)，兩個(gè)正數(shù)相加會(huì)得出一個(gè)負(fù)數(shù)，而比較表達(dá)式 x<y 和 x-y<0 會(huì)產(chǎn)生不同的結(jié)果呢？帶著這些問題一起往下看吧。

3.1 無(wú)符號(hào)加法

原理：無(wú)符號(hào)加法，對(duì)滿足 0 \leqslant x, \quad y<2^{w}? 的 x 和 y有：
x+_{w}^{u} y=\left\{\begin{array}{ll}{x+y,} & {x+y<2^{w}} \\ {x+y-2^{w},} & {2^{w} \leqslant x+y<2^{w+1}}\end{array}\right.

比如：x=9，y=12 的位表示分別為[1001] 和 [1100]。它們的和是21，表示為5位的[10101]，產(chǎn)生溢出，丟棄最高位。

原理： 檢測(cè)無(wú)符號(hào)數(shù)加法中的溢出

對(duì)在范圍 0 \leqslant x, \quad y \leqslant U M a x_{w}?,s=x+y，若s < x 或者等價(jià)的 s < y時(shí)，發(fā)生了溢出。

原理： 無(wú)符號(hào)數(shù)求反

對(duì)滿足 0 \leqslant x<2^{w}? ,的任意x，其w位的無(wú)符號(hào)逆元 -_{w}^{u} x? 表達(dá)式如下：

-_{w}^{u} x=\left\{\begin{array}{ll}{x,} & {x=0} \\ {2^{w}-x,} & {x>0}\end{array}\right.

3.2 補(bǔ)碼加法

原理： 補(bǔ)碼加法

對(duì)滿足0 \leqslant x, \quad y \leqslant U M a x_{w} 的整數(shù)x，y，有：

x+_{w}^{t} y=\left\{\begin{array}{ll}{x+y-2^{w},} & {2^{w-1} \leqslant x+y} \\ {x+y,} & {-2^{w-1} \leqslant x+y<2^{w-1} \quad \begin{array}{l}\\ \end{array}} \\ {x+y+2^{w},} & {x+y<-2^{w-1}} \end{array}\right.

原理： 檢測(cè)補(bǔ)碼加法中的溢出

對(duì)滿足 T M i n_{w} \leqslant x, \quad y \leqslant T M a x_{w}? 的x 和 y，令 s = x + y。當(dāng)且僅當(dāng)x>0,y>0，但s<=0時(shí)，計(jì)算s發(fā)生了正溢出。當(dāng)且僅當(dāng) x<0,y<0，但s>=0時(shí)，計(jì)算發(fā)生了負(fù)溢出。

3.3 乘法和除法

在大多數(shù)機(jī)器上，整數(shù)乘法指令相當(dāng)慢，需要10個(gè)或者更多的時(shí)鐘周期，然而加法、減法、位運(yùn)算、移位操作只需要一個(gè)時(shí)鐘周期。

因此，編譯器使用了移位和加法運(yùn)算的組合代替乘以常數(shù)因子的乘法。

原理： 乘以2的冪

例如：x*14，利用14 = 14=2^{3}+2^{2}+2^{1} ,編譯器會(huì)將乘法重寫為 (x<<3)+(x<2)+(x<<1) ,將乘法替換為三個(gè)移位和一個(gè)加法。

在大多數(shù)機(jī)器上，整數(shù)除法比乘法更慢，需要30個(gè)左右的時(shí)鐘周期。

所以除法，也可以采用移位運(yùn)算，相對(duì)于乘法這里采用的是右移，而不是左移。

4. 浮點(diǎn)數(shù)

固定范圍的數(shù)字，小數(shù)點(diǎn)前代表大小范圍，小數(shù)點(diǎn)后代表精度，浮動(dòng)小數(shù)點(diǎn)即平衡范圍和精度，所以叫浮點(diǎn)數(shù)

4.1 二進(jìn)制小數(shù)

十進(jìn)制數(shù)轉(zhuǎn)換描述定義：
d=\sum_{i=-n}^{m} 10^{i} \times d_{i}

例如：12.34 = 1 \times 10^{1}+2 \times 10^{0}+3 \times 10^{-1}+4 \times 10^{-2}=12 \frac{34}{100}?

二進(jìn)制數(shù)轉(zhuǎn)換描述定義：
b=\sum_{i=-n}^{m} 2^{i} \times b_{i}

例如，101.11_{2}= 1 \times 2^{2}+0 \times 2^{1}+1 \times 2^{0}+1 \times 2^{-1}+1 \times 2^{-2}=4+0+1+\frac{1}{2}+\frac{1}{4}=5 \frac{3}{4} ?

增加二進(jìn)制表示的長(zhǎng)度可以提高表示的精度：

8.png

4.2 IEEE浮點(diǎn)表示

IEEE浮點(diǎn)標(biāo)準(zhǔn)用 V=(-1)^{s} \times M \times 2^{E}? 的形式來(lái)表示一個(gè)數(shù)：

  • 符號(hào)（sign）s決定這數(shù)是負(fù)數(shù)（s=1）還是正數(shù)（s=0）。
  • 尾數(shù)（signnificand） M是一個(gè)二進(jìn)制小數(shù)，它的范圍是 1 \sim 2-\varepsilon。
  • 階碼（exponent） E的作用是對(duì)浮點(diǎn)數(shù)加權(quán)，權(quán)重是2的E次冪。
  • 一個(gè)單獨(dú)的符號(hào)位s
  • k位的階碼字段 編碼階碼E
  • n位小數(shù)字段 編碼尾數(shù)M

如下圖：

在單精度格式（float），s，exp 和 frac 字段分別為 s=1，k=8, n = 23,得到一個(gè)32位的表示。

在雙精度浮點(diǎn)格式（double）中，s=1、k=11、n=52位，得到一個(gè)64位的表示。

9.png

4.3 C語(yǔ)言中的浮點(diǎn)數(shù)

  • 從int轉(zhuǎn)換成float，數(shù)字不會(huì)溢出，但可能會(huì)被舍入；
  • 從int或float轉(zhuǎn)成double，因?yàn)閐ouble范圍更大，精度更高，所以能夠精確的保留數(shù)值；
  • 從double轉(zhuǎn)成float，因?yàn)榉秶?，所以值可能溢出成正無(wú)窮或者負(fù)無(wú)窮，另外由于精度較小，可能舍入。
  • 從float或者double轉(zhuǎn)成int，值將會(huì)向零舍入，例如1.999轉(zhuǎn)換成1，-1.999轉(zhuǎn)成-1。進(jìn)一步來(lái)說(shuō)，值可能會(huì)溢出。

5. 總結(jié)

  • 計(jì)算機(jī)將信息編碼為位（比特），通常組成成字節(jié)序列。
  • 大多數(shù)機(jī)器對(duì)整數(shù)使用補(bǔ)碼編碼，而對(duì)浮點(diǎn)數(shù)使用IEEE標(biāo)準(zhǔn)754編碼。在位級(jí)上理解這些編碼有助于寫出全部數(shù)值范圍上正確運(yùn)算的程序。
  • 由于編碼長(zhǎng)度有限，計(jì)算機(jī)運(yùn)算會(huì)產(chǎn)生溢出。
  • 使用浮點(diǎn)運(yùn)算要小心，因?yàn)橹挥杏邢薜姆秶途取?/li>

本文涉及的數(shù)學(xué)知識(shí)較多，看著比較枯燥。如果是計(jì)算機(jī)專業(yè)的同學(xué)，應(yīng)該會(huì)有些熟悉。 不過(guò)我們?nèi)绻鲆幻呒?jí)程序員，計(jì)算機(jī)底層是繞不過(guò)去的，所以還是擼起袖子，加油干吧！

推薦閱讀

?

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容