閑扯原碼，補(bǔ)碼和反碼
始發(fā)于goal00001111的專欄；允許自由轉(zhuǎn)載，但必須注明作者和出處
人類習(xí)慣使用十進(jìn)制數(shù)進(jìn)行數(shù)值計(jì)算，而計(jì)算機(jī)則采用二進(jìn)制，所以為了讓計(jì)算機(jī)幫助人類計(jì)算，首先要把十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)。本文以最簡(jiǎn)單的8位定點(diǎn)整數(shù)為例，分析了計(jì)算機(jī)存儲(chǔ)和計(jì)算數(shù)值的方法。
地球人都知道，整數(shù)有正負(fù)之分，但計(jì)算機(jī)卻只認(rèn)得“0”“1”，不知道符號(hào)“+”和“-”，所以有必要用“0”“1”來表示“+”“-”。人們規(guī)定用“0”表示“+”，用“1”表示“-”。
這樣，我們就可以表示出計(jì)算機(jī)能識(shí)別的整數(shù)了，我們把符號(hào)數(shù)值化后的二進(jìn)制數(shù)稱為機(jī)器數(shù)，相對(duì)應(yīng)的，符號(hào)沒有數(shù)值化（即仍用“+”“-”號(hào)表示）的二進(jìn)制數(shù)稱為真值。計(jì)算機(jī)只能處理機(jī)器數(shù)，不認(rèn)識(shí)真值，真值是給人類看的。
機(jī)器數(shù)有三種編碼形式，分別稱為：原碼，補(bǔ)碼和反碼。為什么要搞得這么復(fù)雜，那些計(jì)算機(jī)科學(xué)家真的是吃飽了沒事干嗎？且聽我慢慢道來：
其實(shí)篇頭已經(jīng)介紹了機(jī)器碼的一種形式——原碼，它的特點(diǎn)是有效數(shù)值部分照抄真值，符號(hào)“+”“-”分別用“0”“1”表示。
例如，十進(jìn)制數(shù)+6，它的真值是+000 0110（注意：8位二進(jìn)制數(shù)最高位是符號(hào)位，所以其真值只有7位），對(duì)應(yīng)的原碼就是0000 0110。
又如，十進(jìn)制數(shù)-6，它的真值是-000 0110，對(duì)應(yīng)的原碼就是1000 0110。
原碼表示法比較直觀，它的數(shù)值部分就是該數(shù)的絕對(duì)值，而且與真值的轉(zhuǎn)換十分方便。但是它的加減法運(yùn)算較復(fù)雜，當(dāng)兩數(shù)相加時(shí)，機(jī)器要首先判斷兩數(shù)的符號(hào)是否相同，如果相同則兩數(shù)相加，若符號(hào)不同，則兩數(shù)相減。在做減法前，還要判斷兩數(shù)絕對(duì)值的大小，然后用大數(shù)減去小數(shù)，最后再確定差的符號(hào)，換言之，用這樣一種直接的形式進(jìn)行加運(yùn)算時(shí)，負(fù)數(shù)的符號(hào)位不能與其數(shù)值部分一道參加運(yùn)算，而必須利用單獨(dú)的線路確定和的符號(hào)位。要實(shí)現(xiàn)這些操作，電路就很復(fù)雜，這顯然是不經(jīng)濟(jì)實(shí)用的。為了減少設(shè)備，解決機(jī)器內(nèi)負(fù)數(shù)的符號(hào)位參加運(yùn)算的問題，總是將減法運(yùn)算變成加法運(yùn)算，也就引進(jìn)了反碼和補(bǔ)碼這兩種機(jī)器數(shù)。
那如何將減法運(yùn)算轉(zhuǎn)化為加法運(yùn)算呢？
首先引入 “模”的概念，“模”是指一個(gè)計(jì)量系統(tǒng)的計(jì)數(shù)范圍。以我們每天用來算時(shí)間的時(shí)鐘為例，時(shí)鐘的計(jì)量范圍是0～11，所以它的模就等于12。計(jì)算機(jī)也可以看成一個(gè)計(jì)量機(jī)器，它也有一個(gè)計(jì)量范圍，即存在一個(gè)“模”。 機(jī)器字長(zhǎng)為n位的計(jì)算機(jī)的計(jì)量范圍是0～2^n-1，模=2^n。
“模”實(shí)質(zhì)上是計(jì)量器產(chǎn)生“溢出”的量，它的值在計(jì)量器上表示不出來，計(jì)量器上只能表示出模的余數(shù)。例如，雖然時(shí)鐘的模=12，但是在時(shí)鐘的指針并不能真正指向“12點(diǎn)”，“12點(diǎn)”的位置和“0點(diǎn)”是重合的！用C語(yǔ)言表示就是12%12 == 0。
任何有模的計(jì)量器，均可化減法為加法運(yùn)算。這是為什么呢？
仍然以時(shí)鐘為例，假設(shè)當(dāng)前時(shí)針指向10點(diǎn)，而準(zhǔn)確時(shí)間是6點(diǎn)，調(diào)整時(shí)間可有以下兩種撥法：
一種是倒撥4小時(shí)，即：10-4=6
另一種是順撥8小時(shí)：10+8=12+6=6
在以12為模的系統(tǒng)中，加8和減4效果是一樣的，因此凡是減4運(yùn)算，都可以用加8來代替。
對(duì)“模”12而言，8和4互為補(bǔ)數(shù)。插一句，所謂“補(bǔ)數(shù)”，實(shí)際上是模擬了數(shù)學(xué)中“補(bǔ)角”的概念，如果兩個(gè)角的度數(shù)之和為180度，我們就稱這兩個(gè)角互為補(bǔ)角。同樣的，如果在某個(gè)計(jì)量系統(tǒng)中，兩個(gè)數(shù)之和剛好等于模，則它們互為“補(bǔ)數(shù)”，例如，在以12為模的系統(tǒng)中，11和1，10和2，9和3，7和5，6和6都互為補(bǔ)數(shù)。
對(duì)于計(jì)算機(jī)，其概念和方法完全一樣。機(jī)器字長(zhǎng)為n位的計(jì)算機(jī)，設(shè)n=8， 所能表示的最大數(shù)是11111111，若再加1稱為100000000(9位)，但因只有8位，最高位1自然丟失，又回了00000000，所以8位二進(jìn)制系統(tǒng)的模為2^8。 在這樣的系統(tǒng)中減法問題可以化成加法問題，只需把減數(shù)用相應(yīng)的補(bǔ)數(shù)表示就行了。
把補(bǔ)數(shù)用到計(jì)算機(jī)對(duì)數(shù)據(jù)的處理上，就是補(bǔ)碼。補(bǔ)碼也是一種機(jī)器碼，它克服了原碼的一些缺陷，一方面使符號(hào)位能與有效值部分一起參加運(yùn)算，從而簡(jiǎn)化運(yùn)算規(guī)則；另一方面使減法運(yùn)算轉(zhuǎn)換為加法運(yùn)算，進(jìn)一步簡(jiǎn)化計(jì)算機(jī)中運(yùn)算器的線路設(shè)計(jì)。現(xiàn)代的計(jì)算機(jī)都是用補(bǔ)碼的形式來存儲(chǔ)數(shù)據(jù)和進(jìn)行算術(shù)運(yùn)算的。
那補(bǔ)碼是如何編碼的，即我們?nèi)绾螌⒁粋€(gè)整數(shù)的真值轉(zhuǎn)換為一個(gè)8位補(bǔ)碼呢？
回到最初的例子，十進(jìn)制數(shù)+6。我們已經(jīng)知道了它真值是+000 0110，原碼是0000 0110。并且用自然語(yǔ)言介紹了如何實(shí)現(xiàn)真值和原碼的轉(zhuǎn)換。但是，一個(gè)眾所周知的事實(shí)是：“自然語(yǔ)言”不如“數(shù)學(xué)語(yǔ)言”嚴(yán)謹(jǐn)！我們希望能夠用數(shù)學(xué)表達(dá)式來表示真值和原碼的關(guān)系，這就是：
設(shè)機(jī)器字長(zhǎng)為N位，真值為X，則：
[X]原 = X， 0 <= X < 2^(n-1)
[X]原 = 2^(n-1) - X， -2^(n-1) < X <= 0
如何來理解這個(gè)公式呢？
仍以十進(jìn)制數(shù)+6和-6為例：
[+6]原 = 6，把6轉(zhuǎn)換為8位二進(jìn)制數(shù)，就得到原碼0000 0110。（本文的最后將會(huì)提供一個(gè)把十進(jìn)制數(shù)轉(zhuǎn)換為機(jī)器碼的C++算法實(shí)現(xiàn)）。
[-6]原 = 2^(8-1) – (-6) = 256 + 6 = 262，，把262轉(zhuǎn)換為8位二進(jìn)制數(shù)，就得到原碼1000 0110。即最高位本來是0，加了一個(gè)2^(8-1)后，最高位就變成1了。
同樣我們給出補(bǔ)碼的數(shù)學(xué)表達(dá)式：
[X]補(bǔ) = X， 0 <= X < 2^(n-1)
[X]補(bǔ) = 2^n + X， -2^(n-1) <= X < 0
和原碼一樣，正數(shù)的補(bǔ)碼就等于真值，那如何理解負(fù)數(shù)的補(bǔ)碼呢？
例如，[-6]補(bǔ) = 2^8 + (-6) = 512 – 6 = 506。
且慢，這個(gè)506怎么這么熟悉！它不正是以2^8為模的6的“補(bǔ)數(shù)”嗎？原來負(fù)數(shù)的補(bǔ)碼就等于它的絕對(duì)值的補(bǔ)數(shù)啊！
把506轉(zhuǎn)換為8位二進(jìn)制數(shù)，就得到-6的補(bǔ)碼1111 1010。
得到某個(gè)數(shù)的補(bǔ)碼后，我們就可以把減法運(yùn)算轉(zhuǎn)化為加法運(yùn)算了。
補(bǔ)碼加法的運(yùn)算法則為：[X +Y]補(bǔ) = [X] 補(bǔ) + [Y] 補(bǔ)
例1：X =+011 0011，Y=+010 1001，求[X+Y] 補(bǔ)
解：[X +Y]補(bǔ) = [X] 補(bǔ) + [Y] 補(bǔ) = 0011 0011 + 0010 1001 = 0101 1100
例2：X =+011 0011，Y=-010 1001，求[X+Y] 補(bǔ)
解：[X +Y]補(bǔ) = [X] 補(bǔ) + [Y] 補(bǔ) = 0011 0011 + 1101 0111 = 0000 1010 （進(jìn)位溢出）
注：因?yàn)橛?jì)算機(jī)中運(yùn)算器的位長(zhǎng)是固定的（本例中只有8位），上述運(yùn)算中產(chǎn)生的最高位進(jìn)位將丟掉，所以結(jié)果不是1 0000 1010，而是0000 1010。
補(bǔ)碼減法公式：[X - Y]補(bǔ) = [X] 補(bǔ) - [Y] 補(bǔ)= [X] 補(bǔ) + [-Y] 補(bǔ)
其中：[-Y]補(bǔ)稱為負(fù)補(bǔ),求負(fù)補(bǔ)的辦法是：對(duì)補(bǔ)碼的每一位(包括符合位)求反，且未位加1。
例3：X =+011 0011，Y=+010 1001，求[X-Y] 補(bǔ)
解：[X - Y]補(bǔ) = [X] 補(bǔ) + [-Y] 補(bǔ) = 0011 0011 + 1101 0111 = 0000 1010 （進(jìn)位溢出）
例2：X =+011 0011，Y=-010 1001，求[X-Y] 補(bǔ)
解：[X - Y]補(bǔ) = [X] 補(bǔ) + [-Y] 補(bǔ) = 0011 0011 + 0010 1001 = 0101 1100
根據(jù)補(bǔ)碼加減運(yùn)算得到的結(jié)果仍然是補(bǔ)碼，若要將補(bǔ)碼轉(zhuǎn)換成原碼，只要對(duì)其再求一次補(bǔ)碼就行了。
再來說說反碼。當(dāng)初引入反碼是為了解決原碼運(yùn)算所遇到的困難，但由于反碼自身也存在一定的缺陷，加之補(bǔ)碼在機(jī)器運(yùn)算中的優(yōu)越表現(xiàn)，完全掩蓋了反碼的光芒，以至于現(xiàn)在人們之所以提到反碼，只是因?yàn)樵谟霉P算將真值轉(zhuǎn)換為補(bǔ)碼的時(shí)候，可以快一些——先將原碼轉(zhuǎn)換為反碼，然后反碼加1，就得到了補(bǔ)碼——但是對(duì)于計(jì)算機(jī)來說，反碼這個(gè)中介完全是沒有必要的。
反碼和原碼的關(guān)系很緊密，反碼表示法規(guī)定：正數(shù)的反碼與其原碼相同；負(fù)數(shù)的反碼是對(duì)其原碼逐位取反，但符號(hào)位除外。
同樣我們給出反碼的數(shù)學(xué)表達(dá)式：
[X]反 = X， 0 <= X < 2^(n-1)
[X]反 = 2^n – 1 + X， -2^(n-1) < X <= 0
從數(shù)學(xué)表達(dá)式中我們可以發(fā)現(xiàn)，整數(shù)的三種機(jī)器碼都是相同的，而負(fù)數(shù)的則不同。負(fù)數(shù)的反碼是對(duì)原碼按位求反（符合位除外），而補(bǔ)碼則等于反碼加1。這樣有了反碼這個(gè)中介，我們即使是用筆算也能夠很快地將原碼轉(zhuǎn)換為補(bǔ)碼了。例如：
[+6]反 = 6， [-6]反 = 2^(8-1) – 1 + (-6) = 255 + 6 = 261，，把261轉(zhuǎn)換為8位二進(jìn)制數(shù)，就得到反碼1111 1001。
由于-6的原碼為1000 0110，我們稍作觀察，就可找到反碼和原碼的關(guān)系。
再將反碼加1，就得到-6的補(bǔ)碼1111 1010。
現(xiàn)在明白了吧？
附錄：把十進(jìn)制數(shù)轉(zhuǎn)換為機(jī)器碼的C++程序代碼
#include <iostream>
using namespace std;
const int MAX = 32;
void Binary(char b[], int x); //將x轉(zhuǎn)換為二進(jìn)制數(shù)
void TrueForm(char b[], int x); //獲取原碼
void RadixMinus(char b[], int x); //獲取反碼
void Complement(char b[], int x); //獲取補(bǔ)碼
void TruthValue(char b[], int x);//獲取真值
int main()
{
int x = 1;
char b[MAX+1]={0};
cout << "十進(jìn)制數(shù)：" << x << endl;
TruthValue(b, x);//獲取真值
cout << "真值：" << b << endl;
TrueForm(b, x); //獲取原碼
cout << "原碼：" << b << endl;
RadixMinus(b, x);//獲取反碼
cout << "反碼：" << b << endl;
Complement(b, x);//獲取補(bǔ)碼
cout << "補(bǔ)碼：" << b << endl;
cout << "十進(jìn)制數(shù)：" << -x << endl;
TruthValue(b, -x);//獲取真值
cout << "真值：" << b << endl;
TrueForm(b, -x); //獲取原碼
cout << "原碼：" << b << endl;
RadixMinus(b, -x);//獲取反碼
cout << "反碼：" << b << endl;
Complement(b, -x);//獲取補(bǔ)碼
cout << "補(bǔ)碼：" << b << endl;
system("pause");
return 0;
}
void Binary(char b[], int x)//將x轉(zhuǎn)換為二進(jìn)制數(shù)
{
for (int i=MAX-1; i>=0; i--)
{
b[i] = (x & 1) + '0';
x >>= 1;
}
b[MAX] = '\0';
}
void TrueForm(char b[], int x) //獲取原碼：根據(jù)數(shù)學(xué)表達(dá)式求得
{
if (x >= 0)
Binary(b, x);
else
Binary(b, (1<<(MAX-1)) - x);
}
void RadixMinus(char b[], int x) //獲取反碼：正數(shù)的反碼=補(bǔ)碼；負(fù)數(shù)的反碼=補(bǔ)碼-1
{
if (x >= 0)
Binary(b, x);
else
Binary(b, x - 1);
}
void Complement(char b[], int x) //獲取補(bǔ)：數(shù)據(jù)在計(jì)算機(jī)中以補(bǔ)碼形式存儲(chǔ)，直接轉(zhuǎn)換即可
{
Binary(b, x);
}
void TruthValue(char b[], int x)//獲取真值：根據(jù)原碼獲得真值
{
TrueForm(b, x);
b[0] = (b[0] == '0') ? '+' : '-';
}
參考文獻(xiàn)：
（1）Boater的博客：《反碼和補(bǔ)碼技術(shù)是怎樣被提出的？》
http://blog.tianya.cn/blogger/post_show.asp?BlogID=227218&PostID=7046448
（2）北半球的孤獨(dú)發(fā)帖：《關(guān)于機(jī)器數(shù)的幾點(diǎn)注記》
http://forum.noi.cn/thread-29319-1-1.html
本文來自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/goal00001111/archive/2010/04/15/5490612.aspx