關於補碼的由來和作用

• 2019 年 11 月 5 日
• 筆記

最近在讀《深入理解電腦系統》(CSAPP)，第二章中關於補碼的描述很有意思，在書中並沒有詳細敘述補碼的由來和為什麼要使用補碼來表示有符號數，而不是用原碼和反碼。相反這本書詳細的敘述了補碼的數學表示，以及公式的推導！對補碼的由來卻一筆帶過，甚至原碼和反碼只是簡單的在後面的籃框提示中提了一下，根本沒有出現在正文。

這在一定程度上造成了我的閱讀困難，於是在搜索引擎的幫助下，我查了很多資料，了解到補碼的更多細節，以及這個神奇的編碼方式如何幫助人們設計CPU時節省大量的精力和金錢。這裡我把他記錄下來。

電腦中的資訊都是用二進位表示的，在表示無符號數時並沒有什麼問題，但是在表示有符號整數時就出現了問題，如何在二進位中區分正數與負數呢？
區分正數和負數的另一個意義在於如果能夠準確的表示出、負數，我們就可以化減法為加法，如5-4就可以表示為5+(-4)，至於為什麼那麼多先輩要執著於把減法化為加法，原因很簡單，對電腦的電路而言，計算加法要比計算減法方便的多。
很多人提出了有符號整數的編碼方式，其中有：原碼(Sign-Magnitude)、反碼(ones’ Complement)、補碼(two’s Complement)。

原碼

原碼的英文為sign-magnitude，第一個單詞為符號的意思，第二個單詞經過查詢有「大小」的意思，大意應該為符號-數值的組合，在原碼中，第一個數字代表符號位，1代表負數，0代表正數，餘下的為數值位，用來表示具體的數值。這種編碼方式最簡潔易懂，也最符合人的思維。比如：-5用4位二進位原碼來表示就是1101。
CSAPP中給出的原碼數學公式為：

由此我們能推斷出SMAX_w=2^w-1-1,SMIN_w=-(2^w-1-1)。如八位二進位原碼的範圍應該為[-127,127]。
使用原碼來讓機器做運算似乎是可行的，但是實際上，這種方法對機器來說卻是十分困難的，機器無法像人一樣判斷出0是+，1是-，設計出一個能讓機器判斷正負的電路也是十分複雜和困難的。
實際上目前我們很少用原碼來做運算，原碼目前常常用來作為我們求補碼的一個過渡。

反碼

反碼的英文為ones’complement，乍看之下有些迷惑，翻譯過來是「很多個1的補」，似乎更迷惑了。。。
其實反碼確實可以用「很多1的補」來理解，我們都知道w位二進位數表示的最大範圍是2^w-1，用位向量來表示就是[111111….11111]，就是很多個1。假設x是正數，求-x的補碼的含義實際上就是求[11111…111]-x，也就是(2^w-1-x)(其中w為位數)，這是反碼的一種計算方式，另一種計算方式就是用原碼計算，原碼的符號位不變，剩下的數值位全部取反，比如1011的反碼就位1100。這和上面的計算方法得到的結果是一致的。
當然要注意的是上面所說的計算方法只對負整數有作用，正整數的反碼實際上和正常的無符號數編碼沒有區別。
反碼的另一種具體數學解釋是在CSAPP中看到的：

由此我們能推斷出OMAX_w=2^w-1-1,OMIN_w=-(2^w-1-1)。如八位二進位原碼的範圍應該為[-127,127]。
這個公式應該可以通過上面的提到的計算方法嚴格證明出來。
使用此公式可以快速的算出反碼錶示的值。
反碼的優點是計算快捷，不僅僅是對人而言，計算一個負數的補碼，只需要將其的正數表示按位取反即可，對於機器來說，取反可比做加減法快多了。
反碼實際上可以用來做二進位運算，它的規則是從低位到高位逐列進行計算。1和1相加是0但要產生一個進位1，0和1相加是1，0和0相加是0。若最高位相加後產生進位，則最後得到的結果要加1。(反碼運算的原理將在下面的補碼運算中解釋)。
需要注意的是與原碼不同的是，反碼的運算符號位與數值一起參加運算。
用反碼運算，其運算結果亦為反碼。在轉換為真值時，若符號位為0，數位不變；若符號位為1，應將結果求反才是其真值。

原碼和反碼的缺陷

原碼和反碼在不考慮性能的情況下確實能夠用來做二進位有符號整數的計算，歷史上也確有基於這兩種編碼方式的機器。但是這兩種編碼卻存在很多難以解決的缺陷。
考慮四位二進位數[0000]，在原碼中表示0，在反碼中也表示0，而對於原碼來說[1000]也表示0，對於反碼來說[1111]也表示0。一般我們把[0000]稱為+0，而另一種表示方法稱為-0。
一個數字有兩種編碼方式，這顯然是不合理的！為了解決這種不合理我們引入了補碼的概念，它既能完美的解決補碼和原碼的缺點！

介紹完了原碼反碼，在介紹補碼之前，為了便於理解，我們首先要介紹一下模的概念：

模

「模」是指一個計量系統的計數範圍。如時鐘等。電腦也可以看成一個計量機器，它也有一個計量範圍，即都存在一個「模」。
例如：
時鐘的計量範圍是1～12，模=12。表示n位的電腦計量範圍是0～2^(n) -1，模=2^(n)。
「模」實質上是計量器產生「溢出」的量，它的值在計量器上表示不出來，計量器上只能表示出模的餘數。任何有模的計量器，均可化減法為加法運算。
在電腦中，計算加法要比計算減法要容易和便宜，那麼到底如何在計量裝置中用加法代替減法呢？
這裡我們可以用時鐘舉一個例子:

這是一個只有時針的時鐘，目前它指向9。如果我們想讓他回退到4。我們有什麼辦法呢？
最簡單的方法是，倒退五個單位，9-5=4。但是這裡我們不想讓指針回退，是否有另外的方法能夠讓指針指向4呢？
答案是把指針向前撥7個單位。

為什麼能夠這麼做呢，這就是前面我們提到的「模」的作用。
9+7=16=12+4，在時鐘這個計量機器上進位並不能顯示出來，所以最後時鐘上顯示的是4。
在以12模的系統中，加7和減5效果是一樣的，因此凡是減5運算，都可以用加7來代替。對「模」而言，8和4互為補數。實際上以12模的系統中，11和1，10和2，9和3，8和4，6和6都有這個特性。共同的特點是兩者相加等於模。
同樣的概念在電腦中也完全成立，考慮一個四位的二進位數，它的範圍為[0,255]，模為256，把這個概念擴展一下。w位的二進位數的模就為2^w。
模就是補碼之所以能夠進行二進位計算的基本原理。

補碼

現在我們來談談本文的主角補碼(Two’s complement)，它的英文名依舊很迷惑，不過沒關係，下面我會用引入模的概念來幫助我們理解補碼的具體含義。
我們知道一個模為10的計算系統中，-4與+6的結果是相同的(9+6=10+5=15，捨去進位最後的結果為5與9-4相同)，我們把這個概念擴展：
在一個模為M的系統中，我們需要計算m-n，而-n在模為M的系統中可以轉化為+(M-n),所以只需要計算m+(M-n)，這樣就成功的把減法轉換成了加法。
把其擴展到二進位中：
在一個位數為w的計算系統中，我們需要計算m-n(n為正整數)，而-n在系統中可以轉化為(2^w-n),所以只需要計算m+(2^w-n)並把溢出的位捨去，而-n的補碼計算方法就是為2^w-n。這也是英文名為Two’s complement的原因，意為2的補，這裡只有一個2，所以用Two’s complement。
補碼似乎已經十分完美了，它不僅解決了0的編碼重複問題(在補碼中0隻有[0000]一種表示)，也成功的把減法變成了加法，但是問題來了，為了把減法變成加法而引入了減法不是像一個笑話嗎(手動狗頭)。
這個時候我們就需要用到原碼和反碼了，我們來仔細觀察一下反碼的計算方法，對一個負整數位數為w的二進位數-n來說，它的補碼錶示為(2^w-1-n)，對比補碼的表示2^w-n，我們能夠發現補碼=反碼+1。
我們很快就能推出對於一個負整數來說，我們可以算出它的二進位相反數表示，然後對所有的位取反，最後加一，得到的就是補碼的值。這樣我們就使用反碼成功解決了減法的問題。
當然了，和反碼一樣，上面的表示都是對負整數而言，正整數的無符號碼、原碼、反碼、補碼都是一樣的~
CSAPP給出了補碼的數學公式：

同樣的這個公式我們也可以通過證明得到，並且通過這個公式我們也可以直接計算出補碼的實際值。
由此我們能推斷出由此我們能推斷出TMAX_w=2^w-1-1,TMIN_w=-2^w-1。如八位二進位原碼的範圍應該為[-128,127]。這也是為什麼在一般的程式設計語言中，無符號數據類型的負數範圍要比正數大了。
補碼的計算就十分簡單了，直接相加就可以得到答案了~(當然溢出進位依然是要捨去的。)，這也是反碼的計算原理。

一點感想

補碼的出現解決了很多問題，出於崇敬我上網搜索了補碼的發明者，結果是。。。。沒有搜索到，並且經過查證，早在1645年，Pascal的計算器用的十進位補碼。後來到了20世紀，經由馮諾依曼引入到了電腦中。
經典的理論與知識總是在流傳中愈加讓人感到先輩們的偉大，想必3個世紀之前的那位大師在使用補碼來解決計算問題時並沒有想到有一天資訊時代的崛起會讓他的發現即使到了今天也依舊熠熠生輝。