轉載需首行注明原地址
本章參考 車向泉老師的公開課《計算機系統(tǒng)中的數(shù)據(jù)表示》
目標：真正理解為什么要有補碼余黎，明白補碼的各種性質
目錄
- 原碼
- 模運算
- 補碼
- 補碼的性質
- 計算機不會存小數(shù)點件豌， 多一個小數(shù)點向臀，意味著數(shù)據(jù)需要多占一位逾一，而且計算起來分飞，需要拆分小數(shù)點后進行運算婿失，所以計算機存的都是定點數(shù)（提前就拆分好，避免運算時拆分）剿吻。
而浮點數(shù)可以用兩個定點數(shù)表示窍箍，所以以下我們研究的各種存儲編“碼”都是針對定點數(shù)而言。
1. 原碼
大家都知道計算機里面存的是2進制和橙，而實際的數(shù)據(jù)是有正負之分的仔燕，為了標識正負，很容易想到給數(shù)加上一個進制位魔招。
于是就有了原碼晰搀，規(guī)定加0表示正數(shù)，加1表示負數(shù)办斑。
-
定義：
整體來講：
原碼就是首位用0表示正數(shù)外恕，1表示負數(shù)，所以非常簡單直觀乡翅。
這種簡單和直觀會帶來很多個頭疼的問題：
1 +0和-0,0不唯一了
2 加減運算及其復雜
例如：要計算 A - B鳞疲，首先要判斷A和B的數(shù)的正負和大小，以此來判斷最終的正負及運算規(guī)則蠕蚜，比如A>B,A+B- (+表示正尚洽，A+表示A是正數(shù)，同理靶累，B-表示B是負數(shù))腺毫，那么實際上算A+|B|，如果A<B,A+B+挣柬，那么實際上應該算 B-A潮酒，結果上放上負號，如果....
無疑邪蛔，這樣的設計放到運算器上急黎，可能今天就沒有PC了，那么這種運算最致命的地方在哪里？ 為什么會如此復雜勃教？
其根源在于： +-號無法帶入運算淤击，這時，數(shù)可能是正負故源，運算可能是加減遭贸，同時A，B本身還有大小心软，則可能出現(xiàn)222共計16種情況。那么如何把+-號帶入計算機呢著蛙？
首先必須了解計算最基本的運算删铃，然后帶入正負，通過正數(shù)求負數(shù)踏堡。
2. 模運算
計算機有個非常討人厭的且無可避免的情況猎唁，“溢出“,因為計算機的字長是有限的，而計算的數(shù)可以生成無限的結果顷蟆。那么當計算出來的數(shù)超過字長诫隅，應該怎么處理呢?
- 一般來說有兩個處理方法，一個返回錯誤帐偎，一個將無法表示的位丟棄(溢出)逐纬。
- 返回錯誤這當然沒什么好說，盡管"溢出"同樣讓人"不爽"削樊。但是還是應該研究溢出豁生，建立“溢出”模型。
于是便有了模運算（這并不是歷史漫贞，我是瞎推測的）
模運算定義：
在一個運算系統(tǒng)內甸箱，若A、B迅脐、M滿足以下關系：A=B+K*M (K為整數(shù))芍殖，則記作A≡B(mod M)。
一個很形象的例子：時鐘谴蔑，我把時鐘上任意一個時間豌骏，撥動一圈，它又回到撥動前的時間树碱。而“溢出”的就是一個天的時間肯适，這和計算機內部非常像。
3. 補碼
知道了計算機最基本的運算規(guī)則：有模運算成榜。那么應該帶入正號來求出負數(shù)框舔。
首先，還是規(guī)定首位為0就是正數(shù)。例如正數(shù)A刘绣。
那么負數(shù)可以看成：-A（0<=A<M,M為模）
已知：A=B+K*M 樱溉，可得 ：-A = -A + M ，
同時：已知0<=A<M , 可得 ：(-A+M) > 0纬凤。
這相當于用一個正數(shù) (-A+M) 表示出一個負數(shù) -A 福贞。
同理可得，A = A+M停士。
由此挖帘，可以得出補碼的定義：
對于任意一個數(shù) X ，都有X = X + M （X mod M）恋技。
推廣到計算機（假設字長為n）拇舀，可以得到定義：
（注意：負數(shù)部分=號，是強制規(guī)定蜻底，例如8位字長機器碼對應10000000骄崩，我們強制認定為-128）
4.補碼的性質
4.1 補碼的符號位
由此可知，首位0一定是正數(shù)薄辅，首位1一定是負數(shù)要拂。
4.2 補碼中的0唯一
4.3 補碼的范圍
假設機器字長為n。
定點小數(shù)：
-1 <= x < 1- 2^(-(n-1))==> 1.0 ~ 0.111....1 (n-1個1)定點整數(shù)：
-2^(n-1) <= x <= 2^(n-1)-1==>1000...0 ~ 0999..9
4.4 補碼站楚、真值脱惰、原碼間的相互轉換
4.4.1 真值 => 補碼
x為真值
- 當 x >= 0 ，補碼==真值==原碼
- 當 x <= 0
假設字長為n窿春， |x|代表數(shù)值位
小數(shù)：
x補 = 2 + x // -1 <= x <= 2^(-(n-1)
= 1+(1-2^(-(n-1)))-|x| + 2^(-(n-1)) // 1+ 0.111...1 - |x| + 0.000...1
= 符號位為一 + |x|全部位按位取反 + 末位加一
//x為-1時枪芒，|x|=1，溢出了谁尸，結果為0舅踪。按位取反+1后繼續(xù)溢出為0，符號位設置1良蛮，結果剛好對-1（主要原因是-1這個是強制認定的值）
整數(shù)：
x補 = 2^n + x // -2^(n-1) <= x < 0
=2^(n-1) + (2^(n-1) - 1) - |x| + 1
=符號位為一 + |x|全部位按位取反 + 末位加一
由此抽碌，得到一個經(jīng)驗"按位取反，末尾加一"
然而决瞳，這個多了一個“加一”货徙，計算機多跑了一次，有辦法優(yōu)化嗎皮胡？
我們發(fā)現(xiàn)痴颊，可以從左往右早第一個1，1和1右邊的不變屡贺，左邊的按位取反蠢棱。
例如 锌杀，-0.10100100 ，可以一步寫出答案1.01011100泻仙。
4.4.2 補碼 => 真值
假設字長為n糕再，x為補碼
小數(shù)：
x真 = x - 2
= -(1-2^(-(n-1)) - (x-1) + 2^(-(n-1)) // -(0.111..1 - 數(shù)值位 + 0.000...1)
= -(補碼數(shù)值位按位取反 + 0.000...1)
整數(shù):
x真 = x - 2^n
= -(2^(n-1)-1 - (x-2^(n-1)) + 1)// -(111...1 - 數(shù)值位 + 1)
=- (補碼數(shù)值位按位取反 + 1)
同 真值轉補碼，補碼轉真值也可以優(yōu)化：
從左往右早第一個1玉转，1和1右邊的不變突想，左邊的按位取反，再加上-號究抓。
4.5 符號的擴展
原則：擴展后猾担，不能影響大小。
正數(shù)：
小數(shù)尾位補0刺下，整數(shù)高位補0垒探，因為補碼等于真值，所以擴展后保持不變怠李。
負數(shù)：
- 小數(shù)：末尾補0
- 整數(shù)：高位補1
簡單證明下整數(shù)：（注意，x為什么可以替換蛤克，因為我們是擴展符號位捺癞，而x擴展前后必須想等）
4.6 補碼的算術右移
所以，定點小數(shù)构挤，正數(shù)右移高位補0髓介，負數(shù)高位補1
我們推導一下定點整數(shù)：
正數(shù)：
[1/2x補] = 1/2x = 1/2x補
負數(shù)：
[1/2x補] = 2^n + 1/2x
=2^n + 1/2(-2^n + x補)
=2^(n-1) + 1/2x補
所以，定點整數(shù)筋现，正數(shù)右移高位補0唐础，負數(shù)高位補1
由此，可以得到結論矾飞，正數(shù)右移一膨，高位補0，負數(shù)右移高位補1洒沦。
4.7 補碼的算術左移
這里主要的問題：算術左移會讓模變大豹绪，否則溢出。
