二進制補碼一位乘法規律的推導

摘要:計算機采用補碼運算，速度快效率高，但其遞推公式推導復雜。補碼乘法也是《計算機組成原理》課程的難點。文章從補碼與真值的關系出發，首先推導出補碼的右移公式，最終給出了二進制補碼一位乘法規則的較全面的推導過程。

關鍵詞:機器數;真值;補碼;補碼陣列乘法器

中圖分類號:TP332文獻標識碼:A文章編號:1009-3044(2009)25-7278-03

A Detailed Derivation of the Rules about Two's Complement Multiplication

SUN Qi-liang

(University of Ji'nan， Ji'nan 250022， China)

Abstract: The computer using two's complement is faster and more efficient，but the derivation of the rules about two's complement multiplication is Complex.Two's complement multiplication is also a difficulty of the course \"Principles of Computer Organization\".This article starts from the relations of two's complement and the true value.First，it deduces a formula about the shifting to right of two's complement.Finally，it gives the detailed rules about two's complement multiplication.

Key words: machine number; true value; two's complement; two's complement array multiplier

在計算機中表示的帶符號的二進制數稱為“機器數”。這個數本身稱為“真值”。機器數有四種表示形式:原碼、反碼、補碼和移碼。其中補碼在加減法的運算中具有許多優勢，所以在計算機系統中，數值一般用補碼來表示(存儲)。補碼乘法的遞推公式較復雜，《計算機組成原理》課程的一般教材介紹的并不詳細。此補碼一位乘法公式的推導過程如下:

1 真值和補碼之間的關系

設[x]補=x0.x1x2…xn

當x≥0時，

當x≤0時，

真值和補碼的關系:

2 補碼的右移

在補碼機器中，一個數不論其正負，連同符號位向右移一位，符號位保持不變，就等于乘1/2。

設[x]補=x0.x1x2…xn

寫成補碼的形式，即得:

要得到[2-I x]補，連同符號位右移i位即可。

3 補碼一位乘法規則

設被乘數[x]補=x0.x1.x2…xn

乘數[y]補=y0.y1.y2…yn

均為任意符號，則有補碼乘法算式:

[x·y]補=[x]補·y

或:

證明:

1) 當被乘數x符號任意，乘數y符號為正時:

根據補碼定義:

[x]補= x0.x1x2…xn=2+x=2n+1+x (mod2)

[y]補=0.y1y2…yn=y

∴[x]補·[y]補=2n+1·y+x·y=2(y1y2…yn)+x·y

由于(y1y2…yn)是大于或等于1的正整數，根據模運算性質(大于2的部分全部丟掉)有:

2(y1y2…yn)=2

∴[x]補·[y]補=2+x·y=[ x·y]補 (mod2)

即: [ x·y]補=[x]補·[y]

2) 當被乘數x符號任意，乘數y符號為負時:

[x]補= x0.x1x2…xn

[y]補=1.y1y2…yn=2+y(mod2)

∵y=[y]補-2=1.y1y2…yn-2=0.y1y2…yn-1

∴x·y=x(0.y1y2…yn-1)=x(0.y1y2…yn)-x

[ x·y]補=[x(0.y1y2…yn)]補-[x]補

又因(0.y1y2…yn)>0

[x(0.y1y2…yn)]補=[x]補(0.y1y2…yn)

所以:

證畢。

為推導出邏輯實現的分步算法，將上式展開得到各項部分積累加的形式。

注:yn+1是增加的附加位，初值為0

將上式改為接近于分步運算邏輯實現的遞推關系。

注:最后一步不移位。

由此可見，每次都是在前次部分積的基礎上，由(yi+1-yi)決定對[x]補的操作，然后再右移一位，得到新的部分積，即

1)如果yn=yn+1，則部分積[zi]加0，再右移一位;

2)如果ynyn+1=01，則部分積[zi]加[x]補，再右移一位;

3)如果yn=yn+1，則部分積[zu]加[-x]補，再右移一位;

如此重復n+1步，但最后一步不移位。包括一位符號位，所得乘積為2n+1位，其中n為尾數位數。算法流程圖如圖1。

4 結束語

推導過程的關鍵是首先推導出公式[x·y]補=[x]補·y，然后是對公式的展開過程和增加的附加位yn+1。而得出這一公式的前提是1和2兩個推論，即真值與補碼之間的關系和補碼的右移。需要注意循環n+1次，每次右移一位，但是最后一次不移位，這是在驗證補碼運算規則時經常出現的一個錯誤。

參考文獻:

[1] 王愛英.計算機組成與結構[M].北京:清華大學出版社，2001:74-78.

[2] 唐朔飛.計算機組成原理[M].北京:高等教育出版社，2008:243-258

[3] 鄭緯民，湯志忠.計算機系統結構[M].北京:清華大學出版社，1998:39-42

[4] 白中英.計算機組成原理[M].3版.北京:科學出版社，2001:42.

[5] 白中英.計算機組成原理題解、題庫與實驗[M].3版.北京:科學出版社，2001:20.

[6] 李澄舉.一般化全加器在陣列乘法器設計中的典型應用[J].嘉應學院學報，2006，24(3):64.

[7] 彭海云.直接補碼陣列乘法的手工計算方法[J].電子工程師，2008，34(2):63-64.

[8] 胡同瑞.補碼一位乘法遞推公式的正確推導[J].高師理科學刊，2007(3):75.