計算思維下再談補碼設計思想

孫麗

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

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

中圖分類號：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

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

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

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

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

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

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

1 補碼的設計

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

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

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

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

2 補碼加減法

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

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

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

下面談談加法器和減法器的設計的幾個思考。

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

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

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

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

3 補碼乘除法

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

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

3.1 補碼一位乘法

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

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

3.2 補碼二位乘法

3.2.1 補碼二位乘法思想

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

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

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

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

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

4 結論

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

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

最后總結補碼設計的計算思維過程見圖1。

參考文獻：

[1] 袁春風.計算機組成與系統結構[M].北京：清華大學出版社，2010.

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

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