上下文約束

默認(rèn)圍繞8位計(jì)算機(jī)展開討論。

問題

在進(jìn)入正文之前月而，先提三個(gè)問題：

1. 計(jì)算機(jī)中的數(shù)為什么用補(bǔ)碼（2's complement）來表示和存儲(chǔ)碌嘀？
2. 補(bǔ)碼的計(jì)算規(guī)則是怎么來的晤柄？
3. 計(jì)算機(jī)是如何區(qū)分unsigned int和int？

眾所周知蜡坊，二進(jìn)制是一種記數(shù)系統(tǒng)（類比十進(jìn)制），而補(bǔ)碼就是該系統(tǒng)之上的編碼協(xié)議赎败。協(xié)議是為了無序信息流變得規(guī)整秕衙，讓人能夠控制它。從這方面猜測僵刮，補(bǔ)碼產(chǎn)生的原因是為了最小化硬件設(shè)計(jì)的成本灾梦，這大概也是最初的軟件定義硬件（SDH）。

當(dāng)我們想象比特流的存儲(chǔ)過程時(shí)妓笙，不免好奇自己頭腦中的數(shù)值概念（尤其是負(fù)數(shù)和小數(shù)）怎么被計(jì)算機(jī)編碼成有意義的比特流若河？這些比特流如何被正確地計(jì)算成另一種比特流？在更高層次上寞宫，編程語言中的short, int, unsigned int, long, long long等數(shù)值類型是怎樣被計(jì)算機(jī)正確地識(shí)別的萧福？

通常，協(xié)議是處理復(fù)雜度的好方法辈赋，但隱藏在協(xié)議背后的原因比它本身更有探索的價(jià)值鲫忍。如果你也感同身受，那么閱讀下文就是合適的钥屈。

為什么用補(bǔ)碼悟民？

概念解釋

1. 原碼^[1](True form)
   原碼是指一個(gè)二進(jìn)制數(shù)左邊加上符號(hào)位后所得到的碼，且當(dāng)二進(jìn)制數(shù)大于0時(shí)篷就，符號(hào)位為0射亏；二進(jìn)制數(shù)小于0時(shí)，符號(hào)位為1；二進(jìn)制數(shù)等于0時(shí)智润，符號(hào)位可以為0(+0)或1(-0)及舍。

2. 反碼^[2](One's complement)
   反碼是帶有符號(hào)位的二進(jìn)制數(shù)表示；負(fù)數(shù)的反碼是將其對(duì)應(yīng)正數(shù)按位取反窟绷，正數(shù)和0的反碼就是該數(shù)字本身锯玛。

3. 補(bǔ)碼^[3](Two's complement)
   補(bǔ)碼也是帶有符號(hào)位的二進(jìn)制表示；負(fù)數(shù)的補(bǔ)碼是將其對(duì)應(yīng)正數(shù)按位取反再加1兼蜈，正數(shù)和0的補(bǔ)碼就是該數(shù)字本身攘残。

三者的關(guān)系很密切，是1對(duì)1的單射關(guān)系为狸。準(zhǔn)確地說肯腕，補(bǔ)碼下可表示的最大負(fù)數(shù)沒有對(duì)應(yīng)的原碼和反碼。具體原因钥平，待會(huì)兒做詳細(xì)討論实撒。

從實(shí)際應(yīng)用的角度提問，現(xiàn)代計(jì)算機(jī)中數(shù)據(jù)的存儲(chǔ)形式是原碼涉瘾、反碼還是補(bǔ)碼知态？這個(gè)問題其實(shí)可以規(guī)約到另一個(gè)問題上：哪種存儲(chǔ)形式最有利于計(jì)算機(jī)進(jìn)行運(yùn)算？從這個(gè)角度思考就不難得出答案立叛，當(dāng)然是補(bǔ)碼负敏，不然，要是原碼和反碼都?jí)蛴妹厣撸瑸樯对O(shè)計(jì)出補(bǔ)碼其做？

那么，為什么原碼和反碼不夠用赁还？單獨(dú)從數(shù)據(jù)表示來看是無法得出結(jié)論的妖泄，需要從計(jì)算的角度思考。我們都知道艘策，二進(jìn)制是以2為基數(shù)的記數(shù)系統(tǒng)蹈胡，和十進(jìn)制、六十進(jìn)制的記數(shù)本質(zhì)相同朋蔫。在最開始罚渐，記數(shù)系統(tǒng)中是沒有負(fù)數(shù)的，引入負(fù)數(shù)是為了統(tǒng)一概念相反的事物驯妄。比如：收入和支出荷并，支出就可以視為負(fù)的收入。如果用恒等式表達(dá)收支平衡收入 = 支出青扔，將支出移項(xiàng)到左邊就得變號(hào)收入-支出 = 0源织，換句話說翩伪，收入+(-支出) = 0，此時(shí)表達(dá)了總收入為0這個(gè)事實(shí)雀鹃。相同的概念對(duì)于運(yùn)算的意義重大，以前需要設(shè)計(jì)減法的運(yùn)算規(guī)則励两，現(xiàn)在用加法規(guī)則就可以替代黎茎。在人類看來，這意味著概念的統(tǒng)一当悔，而對(duì)于計(jì)算機(jī)而言傅瞻，這簡化了ALU（算術(shù)邏輯單元）中集成電路的設(shè)計(jì)。

既然如此盲憎，負(fù)數(shù)在二進(jìn)制中的表示就尤為重要嗅骄。按照原碼的定義，-1的二進(jìn)制表示是1000 0001饼疙，那么計(jì)算1-1溺森，也就是計(jì)算0000 0001 + 1000 0001 = 1000 0010，這個(gè)數(shù)表示的是十進(jìn)制中的-2窑眯。1-1=-2當(dāng)然是錯(cuò)的屏积，它為什么是錯(cuò)的呢？因?yàn)榉?hào)位也參與運(yùn)算了磅甩，上面的算式其實(shí)表達(dá)的是1+129=130這個(gè)算式炊林。

看到這里，或許需要思考的是數(shù)的表示和它們之間的運(yùn)算是不對(duì)稱的疑問卷要？究其緣由是渣聚，數(shù)在計(jì)算機(jī)中表示是人為定義的，我們規(guī)定了左邊的1是符號(hào)位僧叉，但是ALU不知道奕枝，而且也不應(yīng)該知道。為什么呢瓶堕？因?yàn)槿耸巧谱兊谋度ǎ竺孢€會(huì)出現(xiàn)無符號(hào)數(shù)，那時(shí)候左邊的1可就不能視作符號(hào)位捞烟。

在繼續(xù)探索之前薄声，我們先補(bǔ)充點(diǎn)數(shù)學(xué)知識(shí)。

同余

當(dāng)兩個(gè)整數(shù)除以同一個(gè)正整數(shù)题画，若得相同余數(shù)默辨，則這兩個(gè)整數(shù)同余^[4]。記為：

讀作a與b關(guān)于模m同余苍息。同余的數(shù)具備很多性質(zhì)缩幸，其中有一條保持基本運(yùn)算：

我們用這個(gè)性質(zhì)來反觀一下日常生活中的12小時(shí)制計(jì)時(shí)法壹置。

0點(diǎn)和12點(diǎn)關(guān)于12點(diǎn)同余，5和5當(dāng)然關(guān)于12點(diǎn)同余表谊，那么有：

所以5和17關(guān)于12同余钞护。當(dāng)我們說下午5點(diǎn)時(shí)，其實(shí)也就是在說17點(diǎn)爆办。負(fù)數(shù)也滿足這樣的關(guān)系难咕，即-5和7關(guān)于12同余。

負(fù)數(shù)的反碼

按照定義我們求得-1的反碼距辆，1000 0001的反碼為1111 1110即254余佃，-1和254相對(duì)于255(1111 1111)同余。依據(jù)同余的基本性質(zhì)跨算，

取c為1爆土，那么

即0和255相對(duì)于255同余。當(dāng)然诸蚕，正確性顯而易見步势。但是，這里面也出現(xiàn)了一個(gè)問題背犯，0和255(-0)都是0這個(gè)數(shù)在反碼中的正確表達(dá)立润，這也是負(fù)數(shù)的反碼表示數(shù)的范圍是[-127, 127]，總數(shù)是255個(gè)的由來媳板，就像12小時(shí)制計(jì)時(shí)0和12都是零點(diǎn)的表達(dá)桑腮，那么對(duì)于判0運(yùn)算而言，就得有兩手準(zhǔn)備蛉幸。簡單起見破讨，有沒有其他方式去掉這種特殊情況呢？于是奕纫，補(bǔ)碼順勢上位提陶。

負(fù)數(shù)的補(bǔ)碼

由于0和255都是8位計(jì)算機(jī)中0的合法表達(dá)，容易想到的一種方法就是去掉一個(gè)匹层，而且還得保留同余的性質(zhì)隙笆。

假如把相對(duì)于255的同余變成256的同余是否有幫助呢？此時(shí)升筏，0和256就相對(duì)于256同余了撑柔，但是因?yàn)?位二進(jìn)制只能表示[0, 255]范圍的數(shù)，再多就溢出了您访，256是沒法表示的铅忿。我們還是以-1舉例子：

取c為1，那么

0和256同余灵汪，即0000 0000和1 0000 0000同余檀训，溢出位1被舍去柑潦，就變成了0000 0000。

負(fù)數(shù)的補(bǔ)碼數(shù)的表示范圍為[-128, 127]峻凫，這個(gè)-128是怎么來的呢渗鬼？它的補(bǔ)碼表示是1000 0000。要解答這個(gè)問題荧琼，得看看原碼和反碼中的0的表示譬胎。

先看看原碼，左邊第一位是符號(hào)位铭腕，說明它把0~255個(gè)數(shù)分成了兩半银择，分別是0~127, 128~255多糠。其中累舷，0000 0000和1000 0000都表示0，所以它只能表示255個(gè)數(shù)夹孔。即被盈，-127~127.

類似地，反碼中的0000 0000和1111 1111也都表示0搭伤，其中1000 0000表示-127只怎，所以它也只能表示255個(gè)數(shù)。即怜俐，-127~127.

但是補(bǔ)碼就不同身堡，它里面的0就只有一個(gè)0000 0000，而-128和128相對(duì)于256同余拍鲤，但是128(1 0000 0000)在8位機(jī)器上沒法表示贴谎，所以干脆把1000 0000直接拿來當(dāng)-128，可想而知季稳，這個(gè)數(shù)是沒法通過原碼取反加1計(jì)算出來的擅这，因?yàn)樗鼘?duì)應(yīng)的原碼并不存在（整數(shù)128是不存在的）。

補(bǔ)碼的計(jì)算規(guī)則是怎么來的景鼠？

正數(shù)的補(bǔ)碼就是其本身仲翎；
負(fù)數(shù)的補(bǔ)碼是在其原碼的基礎(chǔ)上, 符號(hào)位不變, 其余各位取反, 最后+1

先說說反碼計(jì)算方式的由來。以-1為例铛漓，其原碼表示如下：

1000 0001

那么為何對(duì)它符號(hào)位之外進(jìn)行取反溯香，就得到了它相對(duì)于255(1111 1111)的反碼呢？

我們用255減去-1的絕對(duì)值浓恶，試試看

  1111 1111
- 0000 0001
-----------
  1111 1110

1111 1110就是254逐哈，它和1000 0001保留符號(hào)位后各位取反的結(jié)果一致。這是巧合嗎问顷？顯然不是昂秃，因?yàn)?code>1111 1111是8位中最大的數(shù)禀梳，所以就不存在借位操作，那么各位減下來肠骆，位是0的自然得到1算途，位是1的自然得到0.

-1和254相對(duì)于255同余，所以-1是254的補(bǔ)（One's complement）蚀腿。不信的話嘴瓤，可以去clojure repl中運(yùn)行下面的表達(dá)式。

(mod -1 255) #=> 254

知道到了反碼的求值方法的由來莉钙，我們不難推斷出補(bǔ)碼的計(jì)算方法廓脆。因?yàn)?56是255+1，取反就是用255減去該數(shù)磁玉，那么用256減去該數(shù)停忿，也就等價(jià)于255減去該數(shù)再加一。

計(jì)算機(jī)是如何區(qū)分unsigned int和int的蚊伞？

我們已經(jīng)知道了計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)全部用的補(bǔ)碼的形式席赂，所以從內(nèi)存中拿出來的數(shù)就是補(bǔ)碼，那么-1的補(bǔ)碼是1111 1111时迫，也就是數(shù)2^8-1=255.

如果說unsigned int的存儲(chǔ)形式和int的一致颅停，那意味著int負(fù)數(shù)轉(zhuǎn)換成unsigned int的值就是它補(bǔ)碼的字面值。我們使用Solidity語言程序驗(yàn)證掠拳，在驗(yàn)證之前癞揉，先要安裝ganache-cli和solidity-repl.

$ ganache-cli
...
$ solr
Welcome to the Solidity REPL!
> int8 c = -1
> uint8 d = uint8(c)
> d
255

-1的補(bǔ)碼是1111 1111，也就是十進(jìn)制的255溺欧，所以從結(jié)果中不難得出如下結(jié)論：在計(jì)算機(jī)中喊熟，數(shù)的存儲(chǔ)和表示是分開的，存儲(chǔ)的是補(bǔ)碼胧奔，計(jì)算過程也使用補(bǔ)碼逊移，但是最后的表示由程序員來決定。所以毫不夸張地說龙填，程序員是規(guī)則的締造者胳泉，也是規(guī)則的解讀者。

順帶一提
solidity中的int和uint是成對(duì)的岩遗，而且從8, 16, 24, ..., 256扇商，一共有32個(gè)。正確性可以通過它的詞法分析程序得出來宿礁。

//solidity/liblangutil/Token.cpp

if (0 < m && m <= 256 && m % 8 == 0 && positionX == _literal.end())
{
    if (keyword == Token::UInt)
        return make_tuple(Token::UIntM, m, 0);
    else
        return make_tuple(Token::IntM, m, 0);
}

1. https://zh.wikipedia.org/wiki/原碼 ?

2. https://zh.wikipedia.org/wiki/反碼 ?

3. https://zh.wikipedia.org/wiki/二補(bǔ)數(shù) ?

4. https://zh.wikipedia.org/wiki/同餘 ?