數(shù)組實現(xiàn)Booth算法

1、計算機(jī)組成原理綜合訓(xùn)練項目報告書項目名稱 Booth算法的實現(xiàn) 班級： 計升本14-1 學(xué)號： 1406980120 姓名： sun 成績： 電子與信息工程學(xué)院計算機(jī)科學(xué)系Booth 算法思想比較法是由Booth夫婦首先提出來的，故又稱Booth算法。它采用相加和相減的操作計算補(bǔ)碼數(shù)據(jù)的乘積。Booth算法對乘數(shù)從低位開始判斷，根據(jù)兩個數(shù)據(jù)位的情況決定進(jìn)行加法減法還是僅僅移位操作。判斷的兩個數(shù)據(jù)位為當(dāng)前位及其右邊的位(初始時需要增加一個輔助位0)，移位操作是向右移動。程序?qū)崿F(xiàn)過程說明本次實驗我是通過GCC編譯器使用C語言來寫的，為了了解Booth算法的核心思想，我使用的是數(shù)組來實現(xiàn)Booth算

2、法的。通過對數(shù)組內(nèi)元素的移動來實現(xiàn)移位操作。加一個附加位。通過判斷附加位和乘數(shù)末尾的數(shù)差值來判斷移位加、減（其實是通過加被乘數(shù)的負(fù)數(shù)來實現(xiàn)）、還是只移位。我是使用函數(shù)模塊實現(xiàn)局部功能，主要函數(shù)如下：int D_BB(int arry);/求補(bǔ)函數(shù)int D2B(int arry,int num); /十進(jìn)制轉(zhuǎn)換為二進(jìn)制int rmove(int arry_s,int arry_b,int a,int b); /右移函數(shù)int arry_len(const int arry); /有效位長度void regulate(int arry);/校正數(shù)組void arry_add(int arry_a

3、,const int arry_b,int k);/數(shù)組求和int Booth(int Num_a,int _Num_a,int Num_b);booth算法程序流程圖圖1. 程序流程圖調(diào)試結(jié)果截圖圖2. BOOTH算法運(yùn)行圖設(shè)計中遇到的問題剛開始的時候，我想利用數(shù)組來實現(xiàn)BOOTH算法，想要把函數(shù)中的數(shù)組返回到主調(diào)函數(shù)中去，就把被調(diào)函數(shù)設(shè)置為指針型的函數(shù)。后來發(fā)現(xiàn)這種方法不行。通過查找相關(guān)書籍，發(fā)現(xiàn)其實將數(shù)組作為參數(shù)，數(shù)組從主調(diào)函數(shù)進(jìn)入被調(diào)函數(shù)后，修改被調(diào)函數(shù)的數(shù)組數(shù)據(jù)時主調(diào)函數(shù)中的數(shù)組數(shù)據(jù)也同時改變。這是因為數(shù)組傳址，相當(dāng)于直接對原數(shù)組直接操作。設(shè)計中的不足及其改進(jìn)措施 在顯示乘數(shù)和被乘數(shù)

4、的補(bǔ)碼時，沒有控制輸出的格式，而采用以16位的數(shù)組全部輸出該輸。可以使用for循環(huán)加上乘數(shù)(被乘數(shù))的原碼有效位來控制輸出的格式。源程序代碼/* * Booth算法 - by sun * */#include <stdio.h>#include <stdlib.h>#define N 16/* - - - 函數(shù)聲明部分 - - - */int D_BB(int arry);/求補(bǔ)函數(shù)int D2B(int arry,int num); /十進(jìn)制轉(zhuǎn)換為二進(jìn)制int rmove(int arry_s,int arry_b,int a,int b); /右移函數(shù)int arr

5、y_len(const int arry); /有效位長度void regulate(int arry);/校正數(shù)組void arry_add(int arry_a,const int arry_b,int k);/數(shù)組求和int Booth(int Num_a,int _Num_a,int Num_b);booth算法/* - - - 函數(shù)定義部分 - - - */int D_BB(int arry)/求補(bǔ)函數(shù)int i,sign = 1;for(i = N-1;i >= 0;i- ) if(0 = arryi) arryi = 1; else arryi = 0; arryN-1 =

6、 arryN-1 + 1; for(i = N-1; i >=0 && (1 = sign);i-) if(2 = arryi) && (1 = sign) ) arryi = 0; arryi-1 = arryi-1 + 1; else if(3 = arryi) && (1 = sign) ) arryi = 1; arryi-1 = arryi-1 + 1; else sign = 0; return 0;int D2B(int arry,int num) /十進(jìn)制轉(zhuǎn)換為二進(jìn)制 int i = N-1; int sign = 1; i

7、f(num>0) while(num > 0) arryi = num % 2; num = num / 2; i-; else if(0 = num)/避免0=num 出現(xiàn)的錯誤 return 0; else num = -num; while(num > 0 ) arryi = num % 2; num = num / 2; i-; D_BB(arry);/求補(bǔ) return 0;int rmove(int arry_s,int arry_b,int a,int b) /右移函數(shù) int i,temp = arry_sN-1; for(i=N-1;i>N-a-1;i

8、-) arry_si = arry_si-1; for(i=N-1;i>N-b-1;i-)arry_bi = arry_bi-1;arry_bi = temp; return 0;int arry_len(const int arry) /有效位長度 int i = 0,k; int arrN; for(k=0;k<N;k+) arrk = arryk; if(1 = arri) D_BB(arr); do i+; while(0 = arri); else do i+; while(0 = arryi && i<N); return (N-i);void r

9、egulate(int arry)/校正數(shù)組 int i; for(i = N-1;i>= 0;i-) if(2 = arryi) arryi = 0; arryi-1 = arryi-1 + 1; else if(3 = arryi) arryi = 1; arryi-1 = arryi-1 + 1; void arry_add(int arry_a,const int arry_b,int k)/數(shù)組求和 int i; for(i = N-1;i >= N-k-2;i- ) arry_ai = arry_ai + arry_bi; regulate(arry_a);/* - -

10、 - - Booth算法 - - - */int Booth(int Num_a,int _Num_a,int Num_b) int i,t,mark,annex = 0; /標(biāo)志位，附加位 int sumN = 0;/部分積數(shù)組 int len_a,len_b; /乘數(shù)的長度 len_a = arry_len(Num_a); len_b = arry_len(Num_b); printf(" t部分積tt乘數(shù)tt附加位n"); for(t = len_b;t >=0;t-) printf(" t"); for(i=N-len_a-2;i<N

11、;i+) if(i = N-len_a)/兩位乘符號分隔點 printf("."); printf("%-d",sumi); printf("tt"); for(i=N-len_b-1;i<N;i+) printf("%-d",Num_bi); printf("tt%-dn",annex); mark = annex - Num_bN-1; if(-1 = mark)/部分積加-X,移位 annex = Num_bN-1; arry_add(sum,_Num_a,len_a); print

12、f("+t"); for(i = N-len_a-2;i<N;i+) if(i = N-len_a) printf("."); printf("%d",_Num_ai); printf("n- - - - - - - - - - - - - - - - - - - - - n t"); for(i = N-len_a-2;i<N;i+) if(i = N-len_a)/兩位乘符號分隔點 printf("."); printf("%d",sumi); printf(

13、"tt"); for(i=N-len_b-1;i<=N-t-2;i+) printf("%d",Num_bi); printf("n"); if(0 = t) break; rmove(sum,Num_b,len_a,len_b); else if(1 = mark)/部分積加X，移位 annex = Num_bN-1; arry_add(sum,Num_a,len_a); printf("+t"); for(i = N-len_a-2;i<N;i+) if(i = N-len_a) /兩位乘符號分隔點

14、 printf("."); printf("%d",Num_ai); printf("n- - - - - - - - - - - - - - - - - - - - - n t"); for(i = N-len_a-2;i<N;i+) if(i = N-len_a)/兩位乘符號分隔點 printf("."); printf("%d",sumi); printf("tt"); for(i=N-len_b-1;i<=N-t-2;i+) printf("%d

15、",Num_bi); printf("n"); if(0 = t) break; rmove(sum,Num_b,len_a,len_b); else/只移位 annex = Num_bN-1; if(0 = t) break; rmove(sum,Num_b,len_a,len_b); printf("X×Y = "); for(i=N-len_a-1;i<N;i+) if(i = N-len_a)/符號分隔點 printf("."); printf("%d",sumi); for(i

16、= N-len_b-1;i<N-1;i+) printf("%d",Num_bi); printf("n"); return 0;/* - - - - - - Main函數(shù) - - - - - - - - */int main(void) int aN=0,bN=0,_aN=0; int x,y,i; printf("輸入被乘數(shù):n"); scanf("%d",&x);printf("輸入乘數(shù):n"); scanf("%d",&y); D2B(a,x);/乘數(shù)的補(bǔ)碼 D2B(_a,-x);/被乘數(shù)的負(fù)補(bǔ) D2B(b,y);/被乘數(shù)的補(bǔ)碼 printf("%d Binray is:n",x); for(i = 0;i< N;i+) printf("%d",ai); printf(&qu