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

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

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

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

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

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

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

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

2、真值

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

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

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

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

1、原碼

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

［+1］ 原 = 0000 0001

［-1］ 原 = 1000 0001

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

［1111 1111 ， 0111 1111］

即

［-127 ， 127］

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

2、反碼

反碼的表示方法是：

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

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

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

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

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

3、補(bǔ)碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了解決原碼做減法的問(wèn)題， 出現(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é)果的真值部分是正確的。 而唯一的問(wèn)題其實(shí)就出現(xiàn)在“0”這個(gè)特殊的數(shù)值上。 雖然人們理解上+0和-0是一樣的， 但是0帶符號(hào)是沒(méi)有任何意義的。 而且會(huì)有［0000 0000］原和［1000 0000］原兩個(gè)編碼表示0.

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

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

這樣0用［0000 0000］表示， 而以前出現(xiàn)問(wè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ǔ)碼來(lái)表示-128， 所以-128并沒(méi)有原碼和反碼表示。（對(duì)-128的補(bǔ)碼表示［1000 0000］補(bǔ)算出來(lái)的原碼是［0000 0000］原， 這是不正確的）

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

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

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

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

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

1. 往回?fù)?個(gè)小時(shí)： 6 - 2 = 4

2. 往前撥10個(gè)小時(shí)： （6 + 10） mod 12 = 4

3. 往前撥10+12=22個(gè)小時(shí)： （6+22） mod 12 =4

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

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

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

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

同余的概念

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

記作 a ≡ b （mod m）

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

舉例說(shuō)明：

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)算是很簡(jiǎn)單的。 但是負(fù)數(shù)呢？

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

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

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

開(kāi)始證明

再回到時(shí)鐘的問(wèn)題上：

回?fù)?小時(shí) = 前撥10小時(shí)

回?fù)?小時(shí) = 前撥8小時(shí)

回?fù)?小時(shí)= 前撥7小時(shí)

注意， 這里發(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是同余的。

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

反身性：

a ≡ a （mod m）

這個(gè)定理是很顯而易見(jiàn)的。

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

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

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

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

如果想看這個(gè)定理的證明， 請(qǐng)看：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)橐粋€(gè)負(fù)數(shù)， 找到了它的正數(shù)同余數(shù)。 但是并不是7-2 = 7+10， 而是 7 -2 ≡ 7 + 10 （mod 12） ， 即計(jì)算結(jié)果的余數(shù)相等。

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

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

先到這一步， -1的反碼表示是1111 1110. 如果這里將［1111 1110］認(rèn)為是原碼， 則［1111 1110］原 = -126， 這里將符號(hào)位除去， 即認(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é)果是相同的！ 而這個(gè)余數(shù)， 正式我們的期望的計(jì)算結(jié)果： 2-1=1

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

而2+126很顯然相當(dāng)于鐘表轉(zhuǎn)過(guò)了一輪， 而因?yàn)榉?hào)位是參與計(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)成原碼， 去除符號(hào)位， 則：

［0111 1111］ 原 = 127

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

（-1） mod 128 = 127

127 mod 128 = 127

2-1 ≡ 2+127 （mod 128）

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

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