上一章我們簡(jiǎn)單的介紹了布爾代數(shù)以及C語(yǔ)言的位運(yùn)算，本次我們主要來(lái)看,，二進(jìn)制如何表示整數(shù),，這是很重要的一章，希望各位猿友莫要錯(cuò)過(guò)。

C語(yǔ)言中的整數(shù)類型及范圍

我們依然以C語(yǔ)言為例，C語(yǔ)言當(dāng)中提供了多種整數(shù)類型，一共十種,，位數(shù)為1、2,、4,、8，其中32位機(jī)器上,，4位的有兩種,，在64位機(jī)器上，8位的有兩種,。不過(guò)C語(yǔ)言有它的最小數(shù)值范圍,，也就是說(shuō)C語(yǔ)言要求這些數(shù)據(jù)類型至少要滿足一個(gè)標(biāo)準(zhǔn)的范圍。下圖是C語(yǔ)言對(duì)整數(shù)類型要求的最小表示范圍,。

仔細(xì)看的話,，可以發(fā)現(xiàn)，C語(yǔ)言只要求有符號(hào)數(shù)的范圍是對(duì)稱的,，另外就是int和long類型的位數(shù)要求都比較低,，分別是2位和4位。

可以看到以上的表中,，每一種整數(shù)類型都可以加unsigned關(guān)鍵字,，來(lái)表示一個(gè)無(wú)符號(hào)數(shù)，即沒(méi)有正負(fù)之分,。在書中,，給出了無(wú)符號(hào)數(shù)的定義，LZ將它簡(jiǎn)化一下，對(duì)于一個(gè)w位的二進(jìn)制來(lái)說(shuō),，它的無(wú)符號(hào)表示為以下形式。

對(duì)于一個(gè)無(wú)符號(hào)編碼來(lái)說(shuō),，它的最大值和最小值很好確定,，對(duì)于一個(gè)w位的二進(jìn)制序列來(lái)說(shuō)，當(dāng)所有位都為0時(shí),，則為最小值,，即

                               UMinw = 0

而當(dāng)所有位都為1時(shí)，則為最大值,，根據(jù)等比數(shù)列的求和公式,，即

                               UMaxw = 1 * (1-2w) / 1 - 2 = 2w - 1

如果把上述的定義看成是一個(gè)函數(shù)的話，那么這個(gè)函數(shù)就是一個(gè)雙射,。也就是說(shuō),，對(duì)于任意整數(shù)x，當(dāng)0 =< x < 2w的時(shí)候,，存在唯一的二進(jìn)制序列與其對(duì)應(yīng),。反過(guò)來(lái)也是一樣的，對(duì)于任意一個(gè)w位的二進(jìn)制序列,，都存在唯一一個(gè)整數(shù)x滿足0 =< x < 2w,，與這個(gè)二進(jìn)制序列對(duì)應(yīng)。

無(wú)符號(hào)編碼屬于相對(duì)較簡(jiǎn)單的格式,，因?yàn)樗衔覀兊膽T性思維,，上述定義其實(shí)就是對(duì)二進(jìn)制轉(zhuǎn)化為十進(jìn)制的公式而已，只不過(guò)在一向嚴(yán)格的數(shù)學(xué)領(lǐng)域來(lái)說(shuō),，是要給予明確的含義的,。

補(bǔ)碼編碼

無(wú)符號(hào)編碼符合人的慣性思維是沒(méi)錯(cuò)，但是可惜的是,，它無(wú)法表示負(fù)整數(shù),。因此我們需要一種能夠表示負(fù)數(shù)的整數(shù)表示方式，這就是補(bǔ)碼編碼,。與無(wú)符號(hào)編碼一樣,，書中依然給出了補(bǔ)碼編碼的定義，即對(duì)于任意一個(gè)w位的二進(jìn)制來(lái)說(shuō),，它的補(bǔ)碼表示為以下形式,。

這里最高位xw-1為符號(hào)位，當(dāng)它為1時(shí),，該公式得到的值為負(fù)數(shù),，當(dāng)為0時(shí)，得到的則為正數(shù),。

我們觀察這個(gè)公式,，不難看出,，補(bǔ)碼格式下，對(duì)于一個(gè)w位的二進(jìn)制序列來(lái)說(shuō),，當(dāng)最高位為1,，其余位全為0時(shí)，得到的就是補(bǔ)碼格式的最小值,，即

                            TMinw = -2w-1

而當(dāng)最高位為0,，其余位全為1時(shí)，得到的就是補(bǔ)碼格式的最大值,，根據(jù)等比數(shù)列的求和公式,，即

                            TMaxw = 1 * (1 - 2w-1) / 1 - 2 = 2w-1-1

與無(wú)符號(hào)編碼一樣，如果把上述的定義看成是一個(gè)函數(shù)的話,，那么這個(gè)函數(shù)同樣是一個(gè)雙射,。也就是說(shuō)，對(duì)于任意整數(shù)x,，當(dāng)-2w-1 =< x < 2w-1的時(shí)候,，存在唯一的二進(jìn)制序列與其對(duì)應(yīng)。反過(guò)來(lái),，對(duì)于任意一個(gè)w位的二進(jìn)制序列,，都存在唯一一個(gè)整數(shù)x滿足-2w-1 =< x < 2w-1，與這個(gè)二進(jìn)制序列對(duì)應(yīng),。

相對(duì)于無(wú)符號(hào)編碼來(lái)說(shuō),，補(bǔ)碼編碼與我們的慣性思維有些不同，因此直觀的理解起來(lái)會(huì)有些別扭,，不過(guò)作為一個(gè)程序猿,，我們應(yīng)該有一顆半機(jī)器的腦子，盡量去適應(yīng)機(jī)器的習(xí)慣,。

兩種編碼的轉(zhuǎn)換

在C語(yǔ)言當(dāng)中,，我們經(jīng)常會(huì)使用強(qiáng)制類型轉(zhuǎn)換，而在之前的章節(jié)中,，LZ也提到過(guò)強(qiáng)制類型轉(zhuǎn)換,。強(qiáng)制類型轉(zhuǎn)換不會(huì)改變二進(jìn)制序列，但是會(huì)改變數(shù)據(jù)類型的大小以及解釋方式,，那么考慮相同整數(shù)類型的無(wú)符號(hào)編碼和補(bǔ)碼編碼,，數(shù)據(jù)類型的大小是沒(méi)有任何變化的，變化的就是它們的解釋方式,。比如1000這個(gè)二進(jìn)制序列,，如果用無(wú)符號(hào)編碼解釋的話就是表示8，而若采用補(bǔ)碼編碼解釋的話，則是表示-8,。

考慮到上面我們已經(jīng)說(shuō)過(guò),，無(wú)論是無(wú)符號(hào)編碼還是補(bǔ)碼編碼，其映射方式都是雙射,，因此它們都一定存在逆映射,。如果我們定義U2Bw(x)為B2Uw(x)的逆映射，則對(duì)于任意一個(gè)整數(shù)x,，如果0 =< x < 2w，經(jīng)過(guò)U2Bw(x)的計(jì)算之后,，將得到唯一一個(gè)二進(jìn)制序列,。同樣的，如果我們定義T2Bw(x)為B2Tw(x)的逆映射,，則對(duì)于任意一個(gè)整數(shù)x,，如果-2w-1 =< x < 2w-1，經(jīng)過(guò)T2Bw(x)的計(jì)算之后,，也將得到唯一一個(gè)二進(jìn)制序列,。

可以很明顯的看出，對(duì)于0到2w-1-1這個(gè)區(qū)間內(nèi)的整數(shù)來(lái)說(shuō),，兩種編碼得到的二進(jìn)制序列是一樣的,。為了得到其它區(qū)間里的整數(shù)的映射關(guān)系，我們定義

                     T2Uw(x) = B2Uw(T2Bw(x))

這個(gè)函數(shù)代表的含義是補(bǔ)碼編碼轉(zhuǎn)換為無(wú)符號(hào)編碼的時(shí)候,，先將補(bǔ)碼編碼轉(zhuǎn)換為二進(jìn)制序列,，再將二進(jìn)制序列轉(zhuǎn)換為無(wú)符號(hào)編碼，最終也就是補(bǔ)碼編碼轉(zhuǎn)為無(wú)符號(hào)編碼的計(jì)算,。

下面我們簡(jiǎn)單的推算一下上面的定義,，究竟是如何轉(zhuǎn)換的，也就是無(wú)符號(hào)編碼與補(bǔ)碼編碼的關(guān)系,。我們將上面無(wú)符號(hào)編碼和補(bǔ)碼編碼的公式相減,，

即                              B2Uw(x) - B2Tw(x) = xw-12w-1 - (-xw-12w-1) = xw-12w

即                                           B2Uw(x) = xw-12w + B2Tw(x)

此處我們令x為T2Bw(x)，則          B2Uw(T2Bw(x)) = xw-12w + B2Tw(T2Bw(x)) = xw-12w + x

即                                            T2Uw(x) = xw-12w + x

此時(shí)考慮xw-1的情況,，當(dāng)xw-1為1時(shí),，也就是補(bǔ)碼編碼表示負(fù)數(shù)的時(shí)候，T2Uw(x)則為2w + x ,。（LZ小提示：此時(shí)x為負(fù)數(shù),，也就是說(shuō)2w + x < 2w）

若xw-1為0時(shí)，則補(bǔ)碼編碼為正數(shù),，此時(shí)T2Uw(x) = x ,。

綜上可知，有下列式子成立

從這個(gè)式子中可以很明顯的看出，最終得到的無(wú)符號(hào)數(shù)范圍為0 =< x < 2w,。

相反,，我們用同樣的方式也可以證明從無(wú)符號(hào)編碼到補(bǔ)碼編碼的公式，這一部分書中省略了,，LZ這里還是寫上來(lái),，以免有的猿友不知所云。我們依然將無(wú)符號(hào)編碼和補(bǔ)碼編碼的公式相減

即                              B2Uw(u) - B2Tw(u) = uw-12w-1 - (-uw-12w-1) = uw-12w

即                                           B2Tw(u) = B2Uw(u) - uw-12w

此時(shí)我們令u為U2Bw(u),，則    B2Tw(U2Bw(u)) = B2Uw(U2Bw(u)) - uw-12w = u - uw-12w

即                                           U2Tw(u) = u - uw-12w

此時(shí)考慮uw-1的情況,，當(dāng)uw-1為0時(shí)，也就是無(wú)符號(hào)編碼數(shù)值小于2w-1的時(shí)候,，U2Tw(u)則為u ,。

若uw-1為1時(shí)，也就是無(wú)符號(hào)編碼數(shù)值大于或等于2w-1的時(shí)候,，此時(shí)U2Tw(u)= u - 2w,。（LZ小提示：此時(shí)U2Tw(u)為負(fù)數(shù)，因?yàn)?u < 2w）

綜上,，我們可以得到無(wú)符號(hào)編碼轉(zhuǎn)換為補(bǔ)碼編碼的公式

同樣的,，在0至2w-1-1之間，兩者依然是相等的,，而其余區(qū)間則不同,。