同樣的位元,不一樣的讀法
在上一篇裡,你學會了把一串位元讀成一個單純的計數:每個位置是二的某次方,把所有的 1 加起來就是了。一個 8 位元的位元組這樣讀,範圍是 0 到 255,而這正是無號的解讀方式。但這裡有個初學者很少察覺的陷阱:位元本身並不包含「這到底是不是有號數?」的答案。位元組 0xFF 不過就是八個 1。那八個 1 究竟代表 255 還是代表 -1,完全由你宣告的型別決定,記憶體裡存的任何東西都不參與這個決定。
這正是位元樣式與解讀的核心,值得慢慢說,因為日後許多混淆都源自漏掉這一點。記憶體裡的一個格子裝著一個位元樣式——一組由 0 和 1 排成的原始排列。而解讀——無號整數、有號整數、一個字元、或一個浮點數的某一部分——則是你的程式選來觀看它的一副鏡片。中央處理器存的是樣式;你的型別決定它說了什麼。所以當你在 C 裡寫 `unsigned char` 而非 `signed char` 時,你並沒有改動任何一個位元;你改的是那副鏡片。
於是我們真正的問題就尖銳起來了:我們手上有一個個固定寬度的位元盒子——8、16、32 或 64 個位元——而我們希望其中一種解讀能夠表達「負的」。我們沒辦法像在紙上那樣另外抓一個負號來用;根本沒有多出來的格子。我們只能拿我們本來就有的那些位元樣式中的一部分,撥去代表負值。每一套這麼做的方案都是一筆交易,而訣竅就在於找出那筆讓硬體做起來最輕鬆的交易。
兩個差一點就成功的錯誤起步
最直觀的想法是符號數值法:偷走最左邊那個位元當作符號旗標——0 代表正、1 代表負——剩下的位元拿來裝大小。在一個位元組裡,0000 0101 是 +5,而 1000 0101 是 -5。整齊又貼近人腦!可是它有兩個難看的毛病。第一,有兩個零:0000 0000 是 +0,1000 0000 是 -0,這既浪費一個樣式,也讓相等判斷變得棘手。第二,也更糟,加法不再簡單:要算 5 + (-3),硬體得先比大小、判斷哪個比較大、做減法、再挑出符號。為了一個小小的和,這要動用好多電路。
一個更聰明、但仍差一點的方案是一的補數:要把一個數變負,就把每個位元翻轉。於是 +5 是 0000 0101,-5 是它的翻轉 1111 1010。如今加法已經非常接近普通的二進位加法了,這很有希望。但兩個零的問題頑固地還在(0000 0000 是 +0,1111 1111 是 -0),而且加法仍需要一道彆扭的補正:從最高位溢出的進位,得繞回去加到最低位,也就是所謂的循環進位。這兩套方案都是真實的歷史,合稱符號數值法與一的補數,也都真的在早期機器上用過。它們被棄用只有一個原因:有個更好的點子出現了。
二的補數:勝出的把戲
每一顆現代中央處理器採用的方案是二的補數,它的核心點子妙得有點狡猾:把普通的二進位加法原封不動地保留下來、不做任何補正,再把那些負數的樣式選得讓加法剛好自己對上。把一個數變負的招牌做法是:每個位元翻轉,然後加 1。所以要在位元組裡得到 -5,從 +5 = 0000 0101 出發,翻轉成 1111 1010,加 1 得到 1111 1011。這個樣式現在就是我們約定稱作 -5 的東西。注意 -0 消失了:把 0000 0000 翻成 1111 1111、加 1,進位從最高位掉出去,你又落回 0000 0000。只有一個零。問題解決。
現在來看回報。用普通的二進位加法器算 5 + (-3),不分任何特例。也就是 0000 0101 + 1111 1101。一欄一欄加起來,結果是 1 0000 0010;最前面那個 1 是溢出 8 位元邊界的進位,被丟棄,剩下 0000 0010,正是 +2。正確,而且用的是你算無號數時用的同一個加法器。這就是二的補數勝出的全部理由:一個電路、一套演算法、兩種號通吃。中央處理器的算術單元是真的不知道、也不在乎你把運算元當成有號還是無號——它只是把位元樣式相加。
negate(x) = (~x) + 1 # flip all bits, then add one
+5 : 0000 0101
~5 : 1111 1010 # flip
-5 : 1111 1011 # + 1
5 + (-3) in one plain adder:
0000 0101 (+5)
+ 1111 1101 (-3)
-----------
1 0000 0010 -> drop the carry off the 8-bit edge
0000 0010 = +2 correct對同樣這些位元組,還有一個更乾淨的思考方式,值得隨身帶著:在一個 n 位元的二的補數數裡,最高位不是單純的符號旗標——它帶著一個負的位值。對一個位元組來說,位元的權重精確地是:最左邊那個權重是 -128,其餘則是平常的 +64、+32、……、+1。於是 1111 1011 直接讀成 -128 + 64 + 32 + 16 + 8 + 0 + 2 + 1 = -5,不用翻轉任何東西。這個「最高位帶負權重」的觀點是最乾淨的心智模型,也讓接下來的點子——符號位元——變得理所當然。
符號位元、不對稱的範圍,以及為何 -1 全是 1
從負權重的觀點看,最左邊那個位元當之無愧地擔起符號位元之名:它是 0,數就是零或正;它是 1,數就是負——因為只有這個位元貢獻負量。這同一個最高位也就是最高有效位元(位值最大者,MSB);最右邊那個則是最低有效位元(值為 1,LSB)。所以要快速讀懂任何一個二的補數位元組,就是:瞄一眼最高有效位元判斷符號,再去秤其餘的位元。1111 1111 的符號位元被設起,所以它是負的——算下來是 -128 + 127 = -1。這正是為什麼任何寬度下的 -1 都是「全部是 1」:位元組裡是 0xFF,32 位元 int 裡是 0xFFFFFFFF。
有一個你必須尊重、不能含糊帶過的真正不對稱。一個 8 位元有號值的範圍是 -128 到 +127,而不是 -127 到 +127。負的那一側比正的那一側多伸出一格,因為零站在正數這一隊,用掉了一個「非負」的樣式。誠實的後果是:最小的那個負數沒有對應的正數夥伴。在一個位元組裡你寫得出 +127,卻寫不出 +128,而關鍵在於 `-(-128)` 會溢位、又繞回 -128,因為對 1000 0000 做翻轉再加 1,得到的還是 1000 0000。在任何會做取負或取絕對值的程式碼裡,都要把這單一個值當成永遠存在的邊界情況來對待。
二的補數也讓加寬變得乾淨。把一個小小的負值存進一個更寬的盒子——比方把 `signed char` 存進 `int`——必須保住它的意義,於是新增的高位會填上符號位元的複本,這個動作叫做符號擴展。位元組 -5 = 1111 1011 變成 32 位元的 0xFFFFFFFB,仍然是 -5。(無號數加寬則改填 0,叫做零擴展。)這些固定寬度本身——8、16、32、64——由 int8_t、uint32_t 這類固定寬度型別精確命名,把大小與符號都寫得清清楚楚,讓你永遠不必用猜的。
這在真實的 C 裡會在哪咬你一口
這一切在你於 C 裡混用號別的那一刻,就不再只是冷知識。在有號與無號型別之間的選擇,會改變同樣的位元被怎麼讀,而這個語言又有個悄悄做轉換的習慣。拿一個裝著 -1 的 `signed int` 去和一個裝著 1 的 `unsigned int` 比較,C 會先把 -1 轉成無號:它的位元樣式 0xFFFFFFFF 被重新讀成巨大的無號值 4294967295,於是 `-1 > 1u` 竟然算出真。位元一個都沒動;變的只有那副鏡片,正如第二節所警告的。
這些轉換遵循整數提升與轉換底下真實而固定的規則——並非隨機——但趕工時很容易忘掉。一個經典臭蟲:`for (size_t i = n - 1; i >= 0; i--)` 永遠停不下來,因為 `size_t` 是無號的,所以 `i >= 0` 永遠為真,而 `i--` 從 0 出發會繞回一個巨大的數,而不是變成負的。修法是把會降到零以下的迴圈計數器放進有號型別,或者重組迴圈。這一課不是「別用無號」,而是「弄清楚每個值戴的是哪副鏡片,並盯緊它們相遇的那道邊界」。
用一個誠實的但書收尾。二的補數如今已是天下共主——自 C23 標準起,它是 C 唯一允許的有號表示法,而且每一顆主流中央處理器數十年來都用它——所以上面那些位元層級的事實,你在做無號算術、或在讀位元樣式時都可以放心倚靠。但別就此推斷有號算術可以放心溢位。有號溢位在 C 裡仍然是未定義行為,是另一個獨立的陷阱,我們會在緊接著的下一篇講溢位與環繞時專門對付它。知道一種表示法,跟被允許走出它的邊界,是兩回事。