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

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

2、法的。通過(guò)對(duì)數(shù)組內(nèi)元素的移動(dòng)來(lái)實(shí)現(xiàn)移位操作。加一個(gè)附加位。通過(guò)判斷附加位和乘數(shù)末尾的數(shù)差值來(lái)判斷移位加、減（其實(shí)是通過(guò)加被乘數(shù)的負(fù)數(shù)來(lái)實(shí)現(xiàn)）、還是只移位。我是使用函數(shù)模塊實(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); /有效位長(zhǎng)度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è)計(jì)中遇到的問(wèn)題剛開(kāi)始的時(shí)候，我想利用數(shù)組來(lái)實(shí)現(xiàn)BOOTH算法，想要把函數(shù)中的數(shù)組返回到主調(diào)函數(shù)中去，就把被調(diào)函數(shù)設(shè)置為指針型的函數(shù)。后來(lái)發(fā)現(xiàn)這種方法不行。通過(guò)查找相關(guān)書(shū)籍，發(fā)現(xiàn)其實(shí)將數(shù)組作為參數(shù)，數(shù)組從主調(diào)函數(shù)進(jìn)入被調(diào)函數(shù)后，修改被調(diào)函數(shù)的數(shù)組數(shù)據(jù)時(shí)主調(diào)函數(shù)中的數(shù)組數(shù)據(jù)也同時(shí)改變。這是因?yàn)閿?shù)組傳址，相當(dāng)于直接對(duì)原數(shù)組直接操作。設(shè)計(jì)中的不足及其改進(jìn)措施 在顯示乘數(shù)和被乘數(shù)

4、的補(bǔ)碼時(shí)，沒(méi)有控制輸出的格式，而采用以16位的數(shù)組全部輸出該輸?？梢允褂胒or循環(huán)加上乘數(shù)(被乘數(shù))的原碼有效位來(lái)控制輸出的格式。源程序代碼/* * 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); /有效位長(zhǎng)度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)的錯(cuò)誤 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) /有效位長(zhǎng)度 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ù)的長(zhǎng)度 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)/兩位乘符號(hào)分隔點(diǎn) 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)/兩位乘符號(hào)分隔點(diǎn) 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(jué)，移位 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) /兩位乘符號(hào)分隔點(diǎn)

14、 printf("."); printf("%d",Num_ai); printf("n- - - - - - - - - - - - - - - - - - - - - n t"); for(i = N-len_a-2;i<N;i+) if(i = N-len_a)/兩位乘符號(hào)分隔點(diǎn) 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)/符號(hào)分隔點(diǎn) 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