深入探求反碼和補(bǔ)碼

本篇文章講解了計(jì)算機(jī)的原碼， 反碼和補(bǔ)碼。 并且進(jìn)行了深入探求了為何要使用反碼和補(bǔ)碼， 以及更進(jìn)一步的論證了為何可以用反碼， 補(bǔ)碼的加法計(jì)算原碼的減法。 論證部分如有不對的地方請各位牛人幫忙指正！ 希望本文對大家學(xué)習(xí)計(jì)算機(jī)基礎(chǔ)有所幫助！

一、機(jī)器數(shù)和真值

在學(xué)習(xí)原碼， 反碼和補(bǔ)碼之前， 需要先了解機(jī)器數(shù)和真值的概念。

1、機(jī)器數(shù)

一個數(shù)在計(jì)算機(jī)中的二進(jìn)制表示形式， 叫做這個數(shù)的機(jī)器數(shù)。機(jī)器數(shù)是帶符號的，在計(jì)算機(jī)用一個數(shù)的最高位存放符號， 正數(shù)為0， 負(fù)數(shù)為1.

比如，十進(jìn)制中的數(shù) +3 ，計(jì)算機(jī)字長為8位，轉(zhuǎn)換成二進(jìn)制就是00000011。如果是 -3 ，就是 10000011 。

那么，這里的 00000011 和 10000011 就是機(jī)器數(shù)。

2、真值

因?yàn)榈谝晃皇欠栁唬詸C(jī)器數(shù)的形式值就不等于真正的數(shù)值。例如上面的有符號數(shù) 10000011，其最高位1代表負(fù)，其真正數(shù)值是 -3 而不是形式值131（10000011轉(zhuǎn)換成十進(jìn)制等于131）。所以，為區(qū)別起見，將帶符號位的機(jī)器數(shù)對應(yīng)的真正數(shù)值稱為機(jī)器數(shù)的真值。

例：0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = –000 0001 = –1

二、原碼， 反碼， 補(bǔ)碼的基礎(chǔ)概念和計(jì)算方法。

在探求為何機(jī)器要使用補(bǔ)碼之前， 讓我們先了解原碼， 反碼和補(bǔ)碼的概念。對于一個數(shù)， 計(jì)算機(jī)要使用一定的編碼方式進(jìn)行存儲。 原碼， 反碼， 補(bǔ)碼是機(jī)器存儲一個具體數(shù)字的編碼方式。

1、原碼

原碼就是符號位加上真值的絕對值， 即用第一位表示符號， 其余位表示值。 比如如果是8位二進(jìn)制：

［+1］ 原 = 0000 0001

［-1］ 原 = 1000 0001

第一位是符號位。 因?yàn)榈谝晃皇欠栁唬?所以8位二進(jìn)制數(shù)的取值范圍就是：

［1111 1111 ， 0111 1111］

即

［-127 ， 127］

原碼是人腦最容易理解和計(jì)算的表示方式。

2、反碼

反碼的表示方法是：

正數(shù)的反碼是其本身

負(fù)數(shù)的反碼是在其原碼的基礎(chǔ)上， 符號位不變，其余各個位取反。

［+1］ = ［00000001］ 原 = ［00000001］ 反

［-1］ = ［10000001］ 原 = ［11111110］ 反

可見如果一個反碼表示的是負(fù)數(shù)， 人腦無法直觀的看出來它的數(shù)值。 通常要將其轉(zhuǎn)換成原碼再計(jì)算。

3、補(bǔ)碼

補(bǔ)碼的表示方法是：

正數(shù)的補(bǔ)碼就是其本身

負(fù)數(shù)的補(bǔ)碼是在其原碼的基礎(chǔ)上， 符號位不變， 其余各位取反， 最后+1. （即在反碼的基礎(chǔ)上+1）

［+1］ = ［00000001］ 原 = ［00000001］ 反 = ［00000001］ 補(bǔ)

［-1］ = ［10000001］ 原 = ［11111110］ 反 = ［11111111］ 補(bǔ)

對于負(fù)數(shù)， 補(bǔ)碼表示方式也是人腦無法直觀看出其數(shù)值的。 通常也需要轉(zhuǎn)換成原碼在計(jì)算其數(shù)值。

三、為何要使用原碼， 反碼和補(bǔ)碼

在開始深入學(xué)習(xí)前， 我的學(xué)習(xí)建議是先“死記硬背”上面的原碼， 反碼和補(bǔ)碼的表示方式以及計(jì)算方法。

現(xiàn)在我們知道了計(jì)算機(jī)可以有三種編碼方式表示一個數(shù)。 對于正數(shù)因?yàn)槿N編碼方式的結(jié)果都相同：

［+1］ = ［00000001］ 原 = ［00000001］ 反 = ［00000001］ 補(bǔ)

所以不需要過多解釋。 但是對于負(fù)數(shù)：

［-1］ = ［10000001］ 原 = ［11111110］ 反 = ［11111111］ 補(bǔ)

可見原碼， 反碼和補(bǔ)碼是完全不同的。 既然原碼才是被人腦直接識別并用于計(jì)算表示方式， 為何還會有反碼和補(bǔ)碼呢？

首先， 因?yàn)槿四X可以知道第一位是符號位， 在計(jì)算的時候我們會根據(jù)符號位， 選擇對真值區(qū)域的加減。 （真值的概念在本文最開頭）。 但是對于計(jì)算機(jī)， 加減乘數(shù)已經(jīng)是最基礎(chǔ)的運(yùn)算， 要設(shè)計(jì)的盡量簡單。 計(jì)算機(jī)辨別“符號位”顯然會讓計(jì)算機(jī)的基礎(chǔ)電路設(shè)計(jì)變得十分復(fù)雜！ 于是人們想出了將符號位也參與運(yùn)算的方法。 我們知道， 根據(jù)運(yùn)算法則減去一個正數(shù)等于加上一個負(fù)數(shù)， 即： 1-1 = 1 + （-1） = 0 ， 所以機(jī)器可以只有加法而沒有減法， 這樣計(jì)算機(jī)運(yùn)算的設(shè)計(jì)就更簡單了。

于是人們開始探索 將符號位參與運(yùn)算， 并且只保留加法的方法。 首先來看原碼：

計(jì)算十進(jìn)制的表達(dá)式： 1-1=0

1 - 1 = 1 + （-1） = ［00000001］ 原 + ［10000001］ 原 = ［10000010］ 原 = -2

如果用原碼表示， 讓符號位也參與計(jì)算， 顯然對于減法來說， 結(jié)果是不正確的。這也就是為何計(jì)算機(jī)內(nèi)部不使用原碼表示一個數(shù)。

為了解決原碼做減法的問題， 出現(xiàn)了反碼：

計(jì)算十進(jìn)制的表達(dá)式： 1-1=0

1 - 1 = 1 + （-1） = ［0000 0001］ 原 + ［1000 0001］ 原= ［0000 0001］ 反 + ［1111 1110］ 反 = ［1111 1111］ 反 = ［1000 0000］ 原 = -0

發(fā)現(xiàn)用反碼計(jì)算減法， 結(jié)果的真值部分是正確的。 而唯一的問題其實(shí)就出現(xiàn)在“0”這個特殊的數(shù)值上。 雖然人們理解上+0和-0是一樣的， 但是0帶符號是沒有任何意義的。 而且會有［0000 0000］原和［1000 0000］原兩個編碼表示0.

于是補(bǔ)碼的出現(xiàn)， 解決了0的符號以及兩個編碼的問題：

1-1 = 1 + （-1） = ［0000 0001］ 原 + ［1000 0001］ 原 = ［0000 0001］ 補(bǔ) + ［1111 1111］ 補(bǔ) = ［0000 0000］ 補(bǔ)=［0000 0000］ 原

這樣0用［0000 0000］表示， 而以前出現(xiàn)問題的-0則不存在了。而且可以用［1000 0000］表示-128：

（-1） + （-127） = ［1000 0001］ 原 + ［1111 1111］ 原 = ［1111 1111］ 補(bǔ) + ［1000 0001］ 補(bǔ) = ［1000 0000］ 補(bǔ)

-1-127的結(jié)果應(yīng)該是-128， 在用補(bǔ)碼運(yùn)算的結(jié)果中， ［1000 0000］補(bǔ) 就是-128. 但是注意因?yàn)閷?shí)際上是使用以前的-0的補(bǔ)碼來表示-128， 所以-128并沒有原碼和反碼表示。（對-128的補(bǔ)碼表示［1000 0000］補(bǔ)算出來的原碼是［0000 0000］原， 這是不正確的）

使用補(bǔ)碼， 不僅僅修復(fù)了0的符號以及存在兩個編碼的問題， 而且還能夠多表示一個最低數(shù)。 這就是為什么8位二進(jìn)制， 使用原碼或反碼表示的范圍為［-127， +127］， 而使用補(bǔ)碼表示的范圍為［-128， 127］。

因?yàn)闄C(jī)器使用補(bǔ)碼， 所以對于編程中常用到的32位int類型， 可以表示范圍是： ［-231， 231-1］ 因?yàn)榈谝晃槐硎镜氖欠栁弧６褂醚a(bǔ)碼表示時又可以多保存一個最小值。

四、原碼， 反碼， 補(bǔ)碼 再深入

計(jì)算機(jī)巧妙地把符號位參與運(yùn)算， 并且將減法變成了加法， 背后蘊(yùn)含了怎樣的數(shù)學(xué)原理呢？

將鐘表想象成是一個1位的12進(jìn)制數(shù)。 如果當(dāng)前時間是6點(diǎn)， 我希望將時間設(shè)置成4點(diǎn)， 需要怎么做呢？我們可以：

1. 往回?fù)?個小時： 6 - 2 = 4

2. 往前撥10個小時： （6 + 10） mod 12 = 4

3. 往前撥10+12=22個小時： （6+22） mod 12 =4

2，3方法中的mod是指取模操作， 16 mod 12 =4 即用16除以12后的余數(shù)是4.

所以鐘表往回?fù)埽p法）的結(jié)果可以用往前撥（加法）替代！

現(xiàn)在的焦點(diǎn)就落在了如何用一個正數(shù)， 來替代一個負(fù)數(shù)。 上面的例子我們能感覺出來一些端倪， 發(fā)現(xiàn)一些規(guī)律。 但是數(shù)學(xué)是嚴(yán)謹(jǐn)?shù)摹?不能靠感覺。

首先介紹一個數(shù)學(xué)中相關(guān)的概念： 同余

同余的概念

兩個整數(shù)a，b，若它們除以整數(shù)m所得的余數(shù)相等，則稱a，b對于模m同余

記作 a ≡ b （mod m）

讀作 a 與 b 關(guān)于模 m 同余。

舉例說明：

4 mod 12 = 4

16 mod 12 = 4

28 mod 12 = 4

所以4， 16， 28關(guān)于模 12 同余。

負(fù)數(shù)取模

正數(shù)進(jìn)行mod運(yùn)算是很簡單的。 但是負(fù)數(shù)呢？

下面是關(guān)于mod運(yùn)算的數(shù)學(xué)定義：

上面是截圖， “取下界”符號找不到如何輸入（word中粘貼過來后亂碼）。 下面是使用“L”和“J”替換上圖的“取下界”符號：

x mod y = x - y L x / y J

上面公式的意思是：

x mod y等于 x 減去 y 乘上 x與y的商的下界。

以 -3 mod 2 舉例：

-3 mod 2

= -3 - 2xL -3/2 J

= -3 - 2xL-1.5J

= -3 - 2x（-2）

= -3 + 4 = 1

所以：

（-2） mod 12 = 12-2=10

（-4） mod 12 = 12-4 = 8

（-5） mod 12 = 12 - 5 = 7

開始證明

再回到時鐘的問題上：

回?fù)?小時 = 前撥10小時

回?fù)?小時 = 前撥8小時

回?fù)?小時= 前撥7小時

注意， 這里發(fā)現(xiàn)的規(guī)律！

結(jié)合上面學(xué)到的同余的概念。實(shí)際上：

（-2） mod 12 = 10

10 mod 12 = 10

-2與10是同余的。

（-4） mod 12 = 8

8 mod 12 = 8

-4與8是同余的。

距離成功越來越近了。 要實(shí)現(xiàn)用正數(shù)替代負(fù)數(shù)， 只需要運(yùn)用同余數(shù)的兩個定理：

反身性：

a ≡ a （mod m）

這個定理是很顯而易見的。

線性運(yùn)算定理：

如果a ≡ b （mod m），c ≡ d （mod m） 那么：

（1）a ± c ≡ b ± d （mod m）

（2）a * c ≡ b * d （mod m）

如果想看這個定理的證明， 請看：http://baike.baidu.com/view/79282.htm

所以：

7 ≡ 7 （mod 12）

（-2） ≡ 10 （mod 12）

7 -2 ≡ 7 + 10 （mod 12）

現(xiàn)在我們?yōu)橐粋€負(fù)數(shù)， 找到了它的正數(shù)同余數(shù)。 但是并不是7-2 = 7+10， 而是 7 -2 ≡ 7 + 10 （mod 12） ， 即計(jì)算結(jié)果的余數(shù)相等。

接下來回到二進(jìn)制的問題上， 看一下： 2-1=1的問題。

2-1=2+（-1） = ［0000 0010］ 原 + ［1000 0001］ 原= ［0000 0010］ 反 + ［1111 1110］ 反

先到這一步， -1的反碼表示是1111 1110. 如果這里將［1111 1110］認(rèn)為是原碼， 則［1111 1110］原 = -126， 這里將符號位除去， 即認(rèn)為是126.

發(fā)現(xiàn)有如下規(guī)律：

（-1） mod 127 = 126

126 mod 127 = 126

即：

（-1） ≡ 126 （mod 127）

2-1 ≡ 2+126 （mod 127）

2-1 與 2+126的余數(shù)結(jié)果是相同的！ 而這個余數(shù)， 正式我們的期望的計(jì)算結(jié)果： 2-1=1

所以說一個數(shù)的反碼， 實(shí)際上是這個數(shù)對于一個膜的同余數(shù)。 而這個膜并不是我們的二進(jìn)制， 而是所能表示的最大值！ 這就和鐘表一樣， 轉(zhuǎn)了一圈后總能找到在可表示范圍內(nèi)的一個正確的數(shù)值！

而2+126很顯然相當(dāng)于鐘表轉(zhuǎn)過了一輪， 而因?yàn)榉栁皇菂⑴c計(jì)算的， 正好和溢出的最高位形成正確的運(yùn)算結(jié)果。

既然反碼可以將減法變成加法， 那么現(xiàn)在計(jì)算機(jī)使用的補(bǔ)碼呢？ 為什么在反碼的基礎(chǔ)上加1， 還能得到正確的結(jié)果？

2-1=2+（-1） = ［0000 0010］ 原 + ［1000 0001］ 原 = ［0000 0010］ 補(bǔ) + ［1111 1111］ 補(bǔ)

如果把［1111 1111］當(dāng)成原碼， 去除符號位， 則：

［0111 1111］ 原 = 127

其實(shí)， 在反碼的基礎(chǔ)上+1， 只是相當(dāng)于增加了膜的值：

（-1） mod 128 = 127

127 mod 128 = 127

2-1 ≡ 2+127 （mod 128）

此時， 表盤相當(dāng)于每128個刻度轉(zhuǎn)一輪。 所以用補(bǔ)碼表示的運(yùn)算結(jié)果最小值和最大值應(yīng)該是［-128， 128］。

但是由于0的特殊情況， 沒有辦法表示128， 所以補(bǔ)碼的取值范圍是［-128， 127］