轉(zhuǎn)載需首行注明原地址
本章參考 車向泉老師的公開課《計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)表示》
目標(biāo)：真正理解為什么要有補(bǔ)碼，明白補(bǔ)碼的各種性質(zhì)
目錄
- 原碼
- 模運(yùn)算
- 補(bǔ)碼
- 補(bǔ)碼的性質(zhì)
- 計(jì)算機(jī)不會存小數(shù)點(diǎn)， 多一個小數(shù)點(diǎn)，意味著數(shù)據(jù)需要多占一位，而且計(jì)算起來，需要拆分小數(shù)點(diǎn)后進(jìn)行運(yùn)算，所以計(jì)算機(jī)存的都是定點(diǎn)數(shù)（提前就拆分好，避免運(yùn)算時(shí)拆分）。
而浮點(diǎn)數(shù)可以用兩個定點(diǎn)數(shù)表示，所以以下我們研究的各種存儲編“碼”都是針對定點(diǎn)數(shù)而言。
1. 原碼
大家都知道計(jì)算機(jī)里面存的是2進(jìn)制，而實(shí)際的數(shù)據(jù)是有正負(fù)之分的，為了標(biāo)識正負(fù)，很容易想到給數(shù)加上一個進(jìn)制位。
于是就有了原碼，規(guī)定加0表示正數(shù)，加1表示負(fù)數(shù)。
-
定義：
整體來講：
原碼就是首位用0表示正數(shù)，1表示負(fù)數(shù)，所以非常簡單直觀。
這種簡單和直觀會帶來很多個頭疼的問題：
1 +0和-0,0不唯一了
2 加減運(yùn)算及其復(fù)雜
例如：要計(jì)算 A - B，首先要判斷A和B的數(shù)的正負(fù)和大小，以此來判斷最終的正負(fù)及運(yùn)算規(guī)則，比如A>B,A+B- (+表示正，A+表示A是正數(shù)，同理，B-表示B是負(fù)數(shù))，那么實(shí)際上算A+|B|，如果A<B,A+B+，那么實(shí)際上應(yīng)該算 B-A，結(jié)果上放上負(fù)號，如果....
無疑，這樣的設(shè)計(jì)放到運(yùn)算器上，可能今天就沒有PC了，那么這種運(yùn)算最致命的地方在哪里？ 為什么會如此復(fù)雜？
其根源在于： +-號無法帶入運(yùn)算，這時(shí)，數(shù)可能是正負(fù)，運(yùn)算可能是加減，同時(shí)A，B本身還有大小，則可能出現(xiàn)222共計(jì)16種情況。那么如何把+-號帶入計(jì)算機(jī)呢？
首先必須了解計(jì)算最基本的運(yùn)算，然后帶入正負(fù)，通過正數(shù)求負(fù)數(shù)。
2. 模運(yùn)算
計(jì)算機(jī)有個非常討人厭的且無可避免的情況，“溢出“,因?yàn)橛?jì)算機(jī)的字長是有限的，而計(jì)算的數(shù)可以生成無限的結(jié)果。那么當(dāng)計(jì)算出來的數(shù)超過字長，應(yīng)該怎么處理呢?
- 一般來說有兩個處理方法，一個返回錯誤，一個將無法表示的位丟棄(溢出)。
- 返回錯誤這當(dāng)然沒什么好說，盡管"溢出"同樣讓人"不爽"。但是還是應(yīng)該研究溢出，建立“溢出”模型。
于是便有了模運(yùn)算（這并不是歷史，我是瞎推測的）
模運(yùn)算定義：
在一個運(yùn)算系統(tǒng)內(nèi)，若A、B、M滿足以下關(guān)系：A=B+K*M (K為整數(shù))，則記作A≡B(mod M)。
一個很形象的例子：時(shí)鐘，我把時(shí)鐘上任意一個時(shí)間，撥動一圈，它又回到撥動前的時(shí)間。而“溢出”的就是一個天的時(shí)間，這和計(jì)算機(jī)內(nèi)部非常像。
3. 補(bǔ)碼
知道了計(jì)算機(jī)最基本的運(yùn)算規(guī)則：有模運(yùn)算。那么應(yīng)該帶入正號來求出負(fù)數(shù)。
首先，還是規(guī)定首位為0就是正數(shù)。例如正數(shù)A。
那么負(fù)數(shù)可以看成：-A（0<=A<M,M為模）
已知：A=B+K*M ，可得 ：-A = -A + M ，
同時(shí)：已知0<=A<M , 可得 ：(-A+M) > 0。
這相當(dāng)于用一個正數(shù) (-A+M) 表示出一個負(fù)數(shù) -A 。
同理可得，A = A+M。
由此，可以得出補(bǔ)碼的定義：
對于任意一個數(shù) X ，都有X = X + M （X mod M）。
推廣到計(jì)算機(jī)（假設(shè)字長為n），可以得到定義：
（注意：負(fù)數(shù)部分=號，是強(qiáng)制規(guī)定，例如8位字長機(jī)器碼對應(yīng)10000000，我們強(qiáng)制認(rèn)定為-128）
4.補(bǔ)碼的性質(zhì)
4.1 補(bǔ)碼的符號位
由此可知，首位0一定是正數(shù)，首位1一定是負(fù)數(shù)。
4.2 補(bǔ)碼中的0唯一
4.3 補(bǔ)碼的范圍
假設(shè)機(jī)器字長為n。
定點(diǎn)小數(shù)：
-1 <= x < 1- 2^(-(n-1))==> 1.0 ~ 0.111....1 (n-1個1)定點(diǎn)整數(shù)：
-2^(n-1) <= x <= 2^(n-1)-1==>1000...0 ~ 0999..9
4.4 補(bǔ)碼、真值、原碼間的相互轉(zhuǎn)換
4.4.1 真值 => 補(bǔ)碼
x為真值
- 當(dāng) x >= 0 ，補(bǔ)碼==真值==原碼
- 當(dāng) x <= 0
假設(shè)字長為n， |x|代表數(shù)值位
小數(shù)：
x補(bǔ) = 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時(shí)，|x|=1，溢出了，結(jié)果為0。按位取反+1后繼續(xù)溢出為0，符號位設(shè)置1，結(jié)果剛好對-1（主要原因是-1這個是強(qiáng)制認(rèn)定的值）
整數(shù)：
x補(bǔ) = 2^n + x // -2^(n-1) <= x < 0
=2^(n-1) + (2^(n-1) - 1) - |x| + 1
=符號位為一 + |x|全部位按位取反 + 末位加一
由此，得到一個經(jīng)驗(yàn)"按位取反，末尾加一"
然而，這個多了一個“加一”，計(jì)算機(jī)多跑了一次，有辦法優(yōu)化嗎？
我們發(fā)現(xiàn)，可以從左往右早第一個1，1和1右邊的不變，左邊的按位取反。
例如 ，-0.10100100 ，可以一步寫出答案1.01011100。
4.4.2 補(bǔ)碼 => 真值
假設(shè)字長為n，x為補(bǔ)碼
小數(shù)：
x真 = x - 2
= -(1-2^(-(n-1)) - (x-1) + 2^(-(n-1)) // -(0.111..1 - 數(shù)值位 + 0.000...1)
= -(補(bǔ)碼數(shù)值位按位取反 + 0.000...1)
整數(shù):
x真 = x - 2^n
= -(2^(n-1)-1 - (x-2^(n-1)) + 1)// -(111...1 - 數(shù)值位 + 1)
=- (補(bǔ)碼數(shù)值位按位取反 + 1)
同 真值轉(zhuǎn)補(bǔ)碼，補(bǔ)碼轉(zhuǎn)真值也可以優(yōu)化：
從左往右早第一個1，1和1右邊的不變，左邊的按位取反，再加上-號。
4.5 符號的擴(kuò)展
原則：擴(kuò)展后，不能影響大小。
正數(shù)：
小數(shù)尾位補(bǔ)0，整數(shù)高位補(bǔ)0，因?yàn)檠a(bǔ)碼等于真值，所以擴(kuò)展后保持不變。
負(fù)數(shù)：
- 小數(shù)：末尾補(bǔ)0
- 整數(shù)：高位補(bǔ)1
簡單證明下整數(shù)：（注意，x為什么可以替換，因?yàn)槲覀兪菙U(kuò)展符號位，而x擴(kuò)展前后必須想等）
4.6 補(bǔ)碼的算術(shù)右移
所以，定點(diǎn)小數(shù)，正數(shù)右移高位補(bǔ)0，負(fù)數(shù)高位補(bǔ)1
我們推導(dǎo)一下定點(diǎn)整數(shù)：
正數(shù)：
[1/2x補(bǔ)] = 1/2x = 1/2x補(bǔ)
負(fù)數(shù)：
[1/2x補(bǔ)] = 2^n + 1/2x
=2^n + 1/2(-2^n + x補(bǔ))
=2^(n-1) + 1/2x補(bǔ)
所以，定點(diǎn)整數(shù)，正數(shù)右移高位補(bǔ)0，負(fù)數(shù)高位補(bǔ)1
由此，可以得到結(jié)論，正數(shù)右移，高位補(bǔ)0，負(fù)數(shù)右移高位補(bǔ)1。
4.7 補(bǔ)碼的算術(shù)左移
這里主要的問題：算術(shù)左移會讓模變大，否則溢出。
