計算思維下再談補碼設(shè)計思想

孫麗

摘要：按照計算思維過程對補碼及運算設(shè)計思想進行了闡述。論述了在計算機組成原理課程中為什么需要設(shè)計補碼，補碼能解決哪些運算問題，分別從補碼加減乘除法運算對補碼運算特性進行了討論。最后對補碼設(shè)計的計算思維過程進行了總結(jié)。

關(guān)鍵詞：計算思維；降維攻擊；補碼；運算器；計算機組成原理；計算機教育

中圖分類號：TP339 文獻標識碼：A 文章編號：1009-3044（2015）29-0070-02

Again Discuss Design idea of the complement on the Computational Thinking

SUN Li

（Chengxian College of Southeast University， Nanjing 210088， China）

Abstract： In accordance with the Computational Thinking process，Design idea of the Complement and operation is discussed. Why do we need to design complement in the computer component principle.The complement can solve what arithmetic problems. Operational characteristics of complement is related and analyzed from the aspects of addition， subtraction， multiplication and division. The final，Summary the of design idea of the complement on the Computational Thinking process.

Key words： computational thinking； dimension reduction attack； complement； ALU； computer component principle computer education

在《三體》中高等文明的二向箔可以使太陽系從三維瞬間降為二維毀滅，這個就叫降維攻擊。這讓我想到了在運算器設(shè)計中出現(xiàn)的補碼，補碼的出現(xiàn)對原碼、反碼就是降維攻擊，補碼在運算器設(shè)計中的地位至今無法撼動。

項目《基于計算思維的計算機組成原理課程研究與教學(xué)》進行中，需要圍繞計算思維概念選擇適用計算思維培養(yǎng)的教學(xué)案例，在運算器設(shè)計這一章，補碼全方位完成這一任務(wù)，因此選擇補碼作為計算思維教學(xué)案例之一。

根據(jù)項目前期對計算思維的研究，在本項目中定義的計算思維概念是：在遇到問題時，考慮用計算工具在問題可解的情況下，思考如何運用計算語言描述解決問題的過程。這個思考過程的結(jié)果是可在計算工具上運行并由計算語言表述的有先后順序的序列。

課程內(nèi)容中第二章講述運算器是怎么設(shè)計的，為了解決這一問題，出現(xiàn)了原碼。但原碼卻有負眾望，在運算器設(shè)計中，最基本的加法運算器設(shè)計不能實現(xiàn)，原碼乘除法運算器的設(shè)計又以加法器器件為基礎(chǔ)。加減器設(shè)計是運算器設(shè)計的基礎(chǔ)，這就必需有新的機器數(shù)編碼產(chǎn)生。

那么新的編碼必須做到能完成加法器設(shè)計。再分析原碼加減運算器設(shè)計不能實現(xiàn)的根本原因，就在于參加運算的兩個數(shù)值數(shù)據(jù)的符號位上，那么能設(shè)計出符號位直接參加運算的編碼嗎，如果能，就可以實現(xiàn)兩個數(shù)值數(shù)據(jù)連同符號位一起參加運算了。我們從這個設(shè)計目標出發(fā)，設(shè)計出了新的編碼，取名補碼。注意補碼是設(shè)計出來的！

下面，說說補碼的設(shè)計，然后以最簡單的核心運算：加減乘為例，討論一下補碼運算特性。（注：本文數(shù)據(jù)如未作特殊說明，皆為二進制數(shù)據(jù)）。

1 補碼的設(shè)計

新的編碼的設(shè)計目標是實現(xiàn)符號位和數(shù)值位一起參加運算。解決方案參考的是模運算，設(shè)計的主要任務(wù)是解決負數(shù)的編碼表示問題。

模運算：在一個模運算系統(tǒng)中，一個數(shù)與它除以“?！焙蟮玫降挠鄶?shù)是等價的，“鐘表”是一個典型的模運算系統(tǒng)。“?！笔怯嬃肯到y(tǒng)的計數(shù)范圍，運算時只計量小于“?！钡牟糠?，多余部分被丟棄。

模運算特征：對于給定的模運算，減去一個數(shù)等價于加上這個數(shù)的補數(shù)，根據(jù)這一特征補碼減法運算可轉(zhuǎn)換為加法運算。

綜上，新編碼補碼的定義為：首先符號位數(shù)字化（改“+”為二進制0），然后一個正數(shù)的補碼不變化（符號位0加上真值數(shù)值位，和該數(shù)原碼編碼一樣），一個負數(shù)的補碼等于模與該數(shù)絕對值之差。

2 補碼加減法

加法運算器是一個重要的基礎(chǔ)的運算器單元。

補碼加法運算規(guī)則：兩個數(shù)的和的補碼等于兩個數(shù)分別取補后再相加的和，即：[A+B]補=[A]補+[B]補 。

補碼減法運算規(guī)則：兩個數(shù)的差的補碼等于被減數(shù)取補后減去減數(shù)取負之后的補，即：[A—B]補=[A]補+[—B]補 。這里[—B]補等于[B]補的各位（含符號位）取反、末位加1。

下面談?wù)劶臃ㄆ骱蜏p法器的設(shè)計的幾個思考。

1）運算器必須有溢出處理部件對運算是否正確給出判斷。關(guān)于這個溢出判斷方法可以有多種設(shè)計方案，這里特別說明一下變形補碼也就是雙符號位補碼的溢出判斷方法。這個方法優(yōu)點：一是溢出判斷結(jié)果更加明確（00正數(shù)、11負數(shù)、01正溢出、10負溢出），其他方法做不到；二是溢出置位電路實現(xiàn)簡單，只要把兩個符號位引入一個異或門就可直接把溢出結(jié)果輸出到程序狀態(tài)寄存器的溢出位OVR。此方法缺點是增加了一位符號位的物理器件成本。

2）加法器低位進位位C-1同時也是運算器進行加減法的控制位。當進行加法時，C-1=0，執(zhí)行加法；當進行減法時，C-1=1，執(zhí)行減法。

3）取反邏輯的設(shè)計。當進行減法時，這里為了得到[—B]補，需要把[B]補的各位（含符號位）通過取反邏輯取反，末位的加1是通過加上C-1（減法時C-1=1）實現(xiàn)的。取反邏輯的設(shè)計是需要與B的位數(shù)N一樣多的N個異或門電路，每個異或門輸入一端是數(shù)據(jù)位，一端是C-1位。加法時，C-1=0，取反邏輯輸出[B]補；減法時，C-1=1，取反邏輯輸出[B]補的各位（含符號位）取反。

綜上，補碼加法器符號位和數(shù)值位一起參與運算，在加法器上增加取反邏輯及巧妙的C-1位的處理完成減法器設(shè)計。從而大大簡化了運算器的設(shè)計。這個設(shè)計簡單且性能優(yōu)異。

3 補碼乘除法

對兩個正數(shù)來說，兩個正數(shù)的補碼的乘積等于它們乘積的補碼，但乘數(shù)是負數(shù)的時候，兩個補碼的乘積不等于它們乘積的補碼。A.D.Booth算法思想解決了這個補碼乘法問題。A.D.Booth算法思想內(nèi)容是：用補碼表示兩個數(shù)進行乘法，符號位與數(shù)值位一起參與乘法運算過程，得出用補碼表示的乘法結(jié)果。根據(jù)Booth乘法算法思想，補碼乘法運算需要在最低位B0后再增加一位B-1位，以完成后項與前項的比較運算，初值為0。

補碼乘法的設(shè)計思路可行，此處我們只以補碼乘法為例說明之，因篇幅有限補碼除法略。

3.1 補碼一位乘法

補碼乘法運算被轉(zhuǎn)化為一系列的比較運算判斷是否進行加法和右移操作。補碼一位乘法具體操作是：每次通過乘數(shù)（Bi-1 –Bi）相鄰兩位乘數(shù)比較以決定+X、–X或+0；然后部分積直接右移一位（高位用符號位填充），移出的一位放入乘數(shù)B中的最高位，同時B也右移一位，把乘數(shù)移出（比較過的）一位，即剛剛比較過的B的末位移出到B-1位，B-1原數(shù)丟棄，然后對新的B的末位（Bi-1 –Bi）相鄰兩位乘數(shù)比較，重復(fù)以上過程直到處理完乘數(shù)B的所有位，注意最后一次只進行比較處理，不再移位。

補碼一位乘法中，每次相鄰兩位乘數(shù)比較判斷加或不加之后，部分積都要進行右移操作。為了存放部分積，部分積寄存器P（含雙符號位）初值為0，結(jié)果值即乘積高N位（含雙符號位）存放在部分積寄存器中，低N位存放在乘數(shù)寄存器B中。

3.2 補碼二位乘法

3.2.1 補碼二位乘法思想

為了提高補碼乘法的運算速度，可以采用二位同時處理或多位同時處理的方法，二位補碼乘法就是每次處理同時考慮乘數(shù)二位，根據(jù)乘數(shù)的兩位Bi+1和Bi以及右鄰位Bi-1的值的組合作為判斷依據(jù)一步求出兩位的部分積，只需增加少量的邏輯線路，就可以將補碼乘法的速度提高一倍，從而提高補碼乘法的速度。

3.2.2 對于補碼二位乘位算法的幾個思考

1）部分積與被乘數(shù)均采用三位符號位，這樣二位補碼乘位算法中無論做怎樣的右移操作都不會影響到中間結(jié)果符號位的最高位，所以中間結(jié)果符號位的最高位可以正確標識結(jié)果的符號位，當同步右移二位時，符號位移出的空位是用中間結(jié)果符號位填充的，當部分積與被乘數(shù)采用三個符號位時，就能保證每次移位操作的簡單與正確。

2）在二位補碼乘位運算中–X、-2X操作以+[–X]補、+[–2X]補完成。

3）奇偶處理放在二位補碼乘位運算進行之前處理，會簡化運算器設(shè)計，就是當發(fā)現(xiàn)數(shù)值位N為奇數(shù)時，我們在不影響數(shù)據(jù)實際值大小的情況下增加一位變成偶數(shù)位參加運算就可以了。

4 結(jié)論

補碼在運算器設(shè)計中，符號位和數(shù)值位一起參與運算，在加法器上增加取反邏輯及巧妙的C-1位的處理完成減法器設(shè)計，補碼乘除法運算器的設(shè)計以加法器器件為基礎(chǔ)，補碼乘除法比原碼乘除法運算器實際執(zhí)行的加法平均運算次數(shù)減少，提高了速度。

用補碼進行運算器設(shè)計，補碼加法器設(shè)計獨一無二，補碼乘除法設(shè)計的簡捷遠遠超出了原碼。補碼運算器設(shè)計成功后，反碼這個機器數(shù)編碼的功能僅僅是作為取補碼的中間過渡過程而留了下來。通過以上論述，可以這么說補碼維度高于原碼、反碼，維度更高更有殺傷力，在運算器的設(shè)計中，真真實實的上演了一場降維攻擊。

最后總結(jié)補碼設(shè)計的計算思維過程見圖1。

參考文獻：

[1] 袁春風(fēng).計算機組成與系統(tǒng)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2010.

[2] 任國林.計算機組成原理[M].北京：電子工業(yè)出版社，2010.

[3] 陳國良.計算思維導(dǎo)論[M].北京：高等教育出版社，2012.