补码一位乘法（Booth算法，C语言实现）
生活随笔
收集整理的這篇文章主要介紹了
补码一位乘法（Booth算法，C语言实现）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
補碼一位乘法
首先了解下什么是補碼？
補碼概念的理解，需要先從“模”的概念開始。 我們可以把模理解為一個容器的容量。當超出這個 容量時，會自動溢出。如：我們最常見到的時鐘，其容量 是 12，過了 12 點之后，就會變為 1 點， 2 點……也就是 說，超過12的部分將被丟棄。那么，在這個例子當中，時鐘 的模就是12。模的概念可以幫助我們理解補碼的含義。
補碼的引出：假設現在時鐘的時針指向 4 點的位 置，要使其指向 3 點，可以怎么操作呢？很明顯，共有 2 種方法，順時針撥 11 格（+11），或逆時針撥 1 格（-1）。 （為了區分順時針和逆時針，我們用正數表示順時針方 向轉動的距離，負數表示逆時針方向轉動的距離） 從上面的例子，不難發現，+11 和-1 實現了同樣的 作用。主要原因是時鐘的模是 12，順時針旋轉代表加法 運算：4+11=15，而達到模的部分會自動溢出，即 15-12= 3，即到達 3 點的位置。逆時針旋轉代表減法運算：4-1= 3。在這個例子當中，+11和-1 是完全等價的。也就是說， 負數-1 可以用正數+11 代替，這樣就可以把減法運算改 為加法運算。也可以說：+11 就是-1 的補碼（模為 12 的 情況下）。
具體的補碼一位乘法（Booth算法）
Booth算法簡介
Ｂｏｏｔｈ算法也就是補碼１位乘的比較法。被乘數為［Ｘ］補，乘數為［Ｙ］補，［Ｐ］補為乘積，按執行順序得出每一步的部分積
［ Ｐ ０］ 補 ＝０， ［ Ｐ １］ 補 ＝｛［ Ｐ ０］ 補 ＋（ Ｙｎ ＋１－ Ｙｎ ）［ Ｘ ］ 補 ｝ ２－１， ?
［ Ｐｎ ＋１］ 補 ＝｛［ Ｐｎ ］ 補 ＋（ Ｙ １－ Ｙ ０）［ Ｘ ］ 補 ｝＝［ Ｘ · Ｙ ］ 補 。 Ｂｏｏｔｈ算法的運算規則如下。
１）乘數的最低位為 Ｙｎ ，在其后再添加一位 Ｙｎ ＋１，其值為０。
２） Ｙｉ ＋１與 Ｙｉ 為相鄰２位，（ Ｙｉ ＋１－ Ｙｉ ）有“ ０”，“ １”和“－１” ３種情況。
① Ｙｉ ＋１－ Ｙｉ ＝０（ Ｙｉ ＋１ Ｙｉ ＝００或１１），部分積直接右移１位。
② Ｙｉ ＋１－ Ｙｉ ＝１（ Ｙｉ ＋１ Ｙｉ ＝１０），部分積加［ Ｘ ］ 補 ，右移１位。
③ Ｙｉ ＋１－ Ｙｉ ＝－１（ Ｙｉ ＋１ Ｙｉ ＝０１），部分積加 ［－ Ｘ ］ 補 ，右移１位。 ３）按以上執行 ｎ ＋１步，最后一步（ ｉ ＝ ｎ ＋１）不移動。
具體的算法可以看看這個鏈接https://www.cnblogs.com/xisheng/p/9260861.html
小啊鵬(木木大人)的C語言算法實現（修改版）
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#include<stdlib.h>
#define M 12
char * Input_X(char a[]);//輸入函數X
char * Input_Y(char a[]);//輸入函數Y
_Bool BoolInput(char a[]);//判斷輸入是否合法
char * GetTrue_form(char a[],char code[]);//由真值求原碼
char * GetComplement(char a[],char b[]);//由原碼求補碼
char * GetComplementOperation(char a[]);//求補運算
char * Booth(char a[],char b[],char []);//補碼一位乘法（Booth算法）
char for_mean(char a);
int main()
{
char flag='Y';
while(1)
{
char X[M];//X的真值
char Y[M];//Y的真值
char X_Code[M];//X_原碼
char Y_Code[M];//y_原碼
char X_Complement_Code[M];//X_補碼
char Y_Complement_Code[M];//Y_補碼
char X_Y_Booth[M];//補碼一位乘法的結果
char *X_Code_P;//X_原碼的指針
char *Y_Code_P;//Y_原碼的指針
char *X_Complement_Code_P;//X_補碼指針
char *Y_Complement_Code_P;//X_補碼指針
Input_X(X);
Input_Y(Y);
X_Code_P=GetTrue_form(X,X_Code);
Y_Code_P=GetTrue_form(Y,Y_Code);
X_Complement_Code_P=GetComplement(X_Code,X_Complement_Code);
Y_Complement_Code_P=GetComplement(Y_Code,Y_Complement_Code);
printf("X的原碼是：%s ",GetTrue_form(X,X_Code));
printf("Y的原碼是：%s ",GetTrue_form(Y,Y_Code));
printf("X的補碼是：%s ",X_Complement_Code);
printf("Y的補碼是：%s ",Y_Complement_Code);
printf("[XY]的真值是：%s ",Booth(X_Complement_Code,Y_Complement_Code,X_Y_Booth));
for_mean(flag);
}
return 0;
}
//循環函數
char for_mean(char a)
{
char b[10];
while(1){
printf("是否需要繼續運算：（Y/N）");
fflush(stdin);
setbuf(stdin, NULL);
scanf("%s",b);
if(strlen(b)!=1)
{
printf("輸入錯誤! ");
continue;
}
setbuf(stdin, NULL);
a=b[0];
if(a=='Y'||a=='y')
{
//printf("輸入的是%c ",a);
break;
}
if(a=='n'||a=='N')
{
//printf("輸入的是%c ",a);
printf("退出中，再見！ ");
exit(0);
}
}
return a;
}
//輸入函數X
char * Input_X(char a[])
{
fflush(stdin);
printf("請輸入你的二進制真值(被乘數)X=");
scanf("%s",a);
while(1)
{
if(BoolInput(a))
break;
scanf("%s",a);
}
printf("你輸入的二進制真值X是：%s ",a);
return a;
}
//輸入函數Y
char * Input_Y(char a[])
{
fflush(stdin);
printf("請輸入你的二進制真值(乘數)Y=");
scanf("%s",a);
while(1)
{
if(BoolInput(a))
break;
scanf("%s",a);
}
printf("你輸入的二進制真值Y是：%s ",a);
return a;
}
//判斷輸入是否合法
_Bool BoolInput(char a[])
{
int count = 0; //小數點出現的次數
//判斷輸入位數是否合法
if(strlen(a)>M-2 ||strlen(a)<3)
{
printf("對不起你輸入的長度不對啊！請重新輸入:");
a=NULL;
return false;
}
//判斷輸入的第一位是否正確！
if(a[0]!='0'&&a[0]!='-')
{
printf("你輸入的第一位就錯了啊! 請重新輸入:");
a=NULL;
return false;
}
//判斷輸入為正數后的操作
if(a[0]=='0')
{
if(a[1]!='.')
{
printf("零后面應該是小數點啊，兄弟！! 請重新輸入:");
return false;
}
}
//判斷輸入為負數后的操作
if(a[0]=='-')
{
if(a[1]!='0'||a[2]!='.')
{
printf("負號后面應該接的零啊，老哥！! 請重新輸入:");
return false;
}
}
//判斷是否有除0，1，-以外的字符輸入
for(int i=1;i<strlen(a);i++)
{
if(a[i]!='0'&&a[i]!='1'&&a[i]!='.')
{
printf("老哥你輸入的不是二進制的真值啊！請重新輸入:");
a=NULL;
return false;
}
if(a[i]=='.')
{
count++;
}
}
//判斷輸入的小數點個數是否合法
if(count>1)
{
printf("老哥你輸入的小數點有%d個，這多了啊！請重新輸入",count);
a=NULL;
return false;
}
return true;
}
//由真值求原碼
char * GetTrue_form(char a[],char code[])
{
int flag=0;
//如果真值是負數符號為置為1
if(a[0]=='-')
{
code[0]='1';
if(a[1]=='0')
{
for(int i=1;i<strlen(a);i++)
{
if(a[i]=='1')
flag=1;
code[i]=a[i+1];
if(flag==0)
code[strlen(a)]='0';
}
code[strlen(a)+1]='';
return code;
}
//
else
{
for(int i=1;i<strlen(a);i++)
{
code[i]=a[i];
}
code[strlen(a)+1]='';
}
return code;
}
//反之置為0
else
{
for(int i=0;i<strlen(a);i++)
{
code[i]=a[i];
}
code[strlen(a)]='';
}
return code;
}
//原碼轉化補碼
char * GetComplement(char a[],char b[])
{
for(int i=0;i<strlen(a);i++)
{
b[i]=a[i];
}
b[strlen(a)+1]='';
//正數的補碼就是原碼
if(b[0]=='0')
{
return b;
}
//負數的補碼轉化
if(b[0]=='1')
{
int j=0; //定位低位往高位遇到的第一個'1'.
for(int i=strlen(b);i>1;i--)
{
if(b[i]=='1')
{
j=i;
break;
}
}
//具體的原碼轉補碼，低位往高位遇到的第一個'1'往前的取反，符號位不變！
for(int i=1;i<j;i++)
{
if(b[i]=='1')
{
b[i]='0';
continue;
}
if(b[i]=='0')
{
b[i]='1';
continue;
}
}
}
return b;
}
//求補運算，將一個數（包括正數和負數）所有二進制位（包括符號位和數值位）取反，然后在最低位加上1。
char * GetComplementOperation(char a[])
{
//取反
for(int i=0;i<strlen(a);i++)
{
if(a[i]=='1')
{
a[i]='0';
continue;
}
else if(a[i]=='0')
{
a[i]='1';
}
}
//加1操作
//判斷最后一位是不是0如果是0則只在最后一位加1
if(a[strlen(a)-1]=='0')
{
a[strlen(a)-1]='1';
return a;
}
for(int i=strlen(a);i>0;i--)
{
if(a[i]=='1')
{
a[i]=='0';
continue;
}
if(a[i]=='0')
{
a[i]=='1';
break;
}
}
return a;
}
//補碼一位乘法（Booth算法）
char * Booth(char a[],char b[],char d[])
{
char c='0';//進位
char b_Temp;//一位過程中需要的臨時變量
char X_ComplementOperation[M];//[-X]補
char a_Temp[M];
//首先統一位數
int X_i;//x補碼的長度
int Y_i;//y補碼的長度
int Length_Difference=0;//長度的差值
X_i=strlen(a);
Y_i=strlen(b);
printf("x的位數%d和y的位數是：%d ",X_i,Y_i);
printf("X的補碼為：%s ",a);
printf("Y的補碼為：%s ",b);
if(X_i>Y_i)
{
printf("我比Y的位數大 ");
Length_Difference=X_i-Y_i;
for(int i=0;i<Length_Difference;i++)
{
b[Y_i+i]='0';
}
b[Y_i+Length_Difference]='';
}
if(X_i<Y_i)
{
printf("我比Y的位數小 ");
Length_Difference=Y_i-X_i;
for(int i=0;i<Length_Difference;i++)
{
a[X_i+i]='0';
}
a[Y_i+Length_Difference+1]='';
}
printf(" ");
printf("統一符號位X的補碼變為：%s ",a);
printf("統一符號位Y的補碼變為：%s ",b);
printf(" ");
//把X的補碼變為雙符號位的
int X_Length=0;//X的長度
int Y_Length=0;//Y的長度
X_Length=strlen(a);
Y_Length=strlen(b);
char temp;
temp=a[0];
for(int i=strlen(a)-1;i>0;i--)
{
a[i+1]=a[i];
if(a[i]=='.')
break;
}
a[0]=temp;
a[1]=temp;
a[X_Length+1]='';
printf("將X的補碼變為雙符號位：%s ",a);
stpcpy(a_Temp,a);
//求[-X]補
GetComplementOperation(a_Temp);
for(int i=0;i<strlen(a_Temp);i++)
{
X_ComplementOperation[i]=a_Temp[i];
}
X_ComplementOperation[strlen(a_Temp)]='';
printf("X求補是：%s ",X_ComplementOperation);
//對Y的最后一位補0操作
b[Y_Length]='0';
b[Y_Length+1]='';
printf("對Y的補碼最低位加0后：%s ",b);
//具體的運算過程
X_Length=strlen(a);
Y_Length=strlen(b);
char Cn;//高位
char Cn_1;//地位
char Register[X_Length+Y_Length];//寄存器數組
//初始化寄存器數組
for(int i=0;i<X_Length;i++)
{
if(a[i]=='.')
{
Register[i]='.';
continue;
}
Register[i]='0';
}
for(int i=0;i<Y_Length;i++)
{
Register[i+X_Length]=b[i];
}
Register[X_Length+Y_Length]='';
printf("寄存器初始的數據：%s",Register);
//除去小數點Register
for(int i=0;i<strlen(Register);i++)
{
if(Register[i]=='.')
{
for(int j=i;j<strlen(Register);j++)
{
Register[j]=Register[j+1];
}
}
}
printf("寄存器初始的數據：%s ",Register);
//除去小數點X_ComplementOperation
for(int i=0;i<strlen(X_ComplementOperation);i++)
{
if(X_ComplementOperation[i]=='.')
{
for(int j=i;j<strlen(X_ComplementOperation);j++)
{
X_ComplementOperation[j]=X_ComplementOperation[j+1];
}
}
}
//除去小數點a
for(int i=0;i<strlen(a);i++)
{
if(a[i]=='.')
{
for(int j=i;j<strlen(a);j++)
{
a[j]=a[j+1];
}
}
}
//開始進行比較
char flag='D';
for(int i=0;i<Y_Length-2;i++)
{
Cn=Register[strlen(Register)-2];
Cn_1=Register[strlen(Register)-1];
if(Cn=='0'&&Cn_1=='0')
flag='A';
if(Cn=='1'&&Cn_1=='1')
flag='A';
if(Cn=='0'&&Cn_1=='1')
flag='B';
if(Cn=='1'&&Cn_1=='0')
flag='C';
printf("操作數的高位是：%c低位是：%c ",Cn,Cn_1);
switch (flag)
{
//操作1：右移一位
case 'A':
{
if(i<Y_Length-3)
{
for(int j=strlen(Register)-1;j>1;j--)
{
Register[j]=Register[j-1];
}
Register[1]=Register[0];
}
printf("移位操作后寄存器的數據：%s ",Register);
break;
}
//操作2：加上X的補，并右移一位
case 'B':
{
//加的操作
//printf("a的值是：%s ",a);
for(int j=strlen(a)-1;j>=0;j--)
{
//設置尾是否有進位數
if(j==strlen(a)-1)
{
if(Register[j]=='1'&& a[j]=='1')
{
c='1';
Register[j]='0';
continue;
}
if(Register[j]=='1'&& a[j]=='0')
{
c='0';
Register[j]='1';
continue;
}
if(Register[j]=='0'&& a[j]=='1')
{
c='0';
Register[j]='1';
continue;
}
}
if(Register[j]=='1')
{
if(a[j]=='0' && c=='0')
{
continue;
}
else if(a[j]=='0' &&c=='1')
{
Register[j]='0';
c='1';
continue;
}
else if(a[j]=='1'&& c=='0')
{
Register[j]='0';
c='1';
continue;
}
else if(a[j]=='1'&& c=='1')
{
Register[j]='1';
c='1';
continue;
}
}
if(Register[j]=='0')
{
if(a[j]=='0' && c=='0')
{
continue;
}
else if(a[j]=='0' &&c=='1')
{
Register[j]='1';
c='0';
continue;
}
else if(a[j]=='1'&& c=='0')
{
Register[j]='1';
c='0';
continue;
}
else if(a[j]=='1'&& c=='1')
{
Register[j]='0';
c='1';
continue;
}
}
}
//printf("未移位寄存器的數據：%s ",Register);
//移位的操作
if(i<Y_Length-3)
{
for(int j=strlen(Register)-1;j>1;j--)
{
Register[j]=Register[j-1];
}
Register[1]=Register[0];
}
printf("B操作后寄存器的數據：%s ",Register);
break;
}
//操作3：加上-X的補，并右移一位
case 'C':
{
//加-x補碼的操作
//printf("X_ComplementOperation的值是：%s",X_ComplementOperation);
for(int j=strlen(X_ComplementOperation)-1;j>=0;j--)
{
//設置尾是否有進位數
if(j==strlen(a)-1)
{
if(Register[j]=='1'&& a[j]=='1')
{
c='1';
Register[j]='0';
continue;
}
if(Register[j]=='1'&& a[j]=='0')
{
c='0';
Register[j]='1';
continue;
}
if(Register[j]=='0'&& a[j]=='1')
{
c='0';
Register[j]='1';
continue;
}
}
//加
if(Register[j]=='1')
{
if(X_ComplementOperation[j]=='0' && c=='0')
{
continue;
}
else if(X_ComplementOperation[j]=='0' &&c=='1')
{
Register[j]='0';
c='1';
continue;
}
else if(X_ComplementOperation[j]=='1'&& c=='0')
{
Register[j]='0';
c='1';
continue;
}
else if(X_ComplementOperation[j]=='1'&& c=='1')
{
Register[j]='1';
c='1';
continue;
}
}
if(Register[j]=='0')
{
if(X_ComplementOperation[j]=='0' && c=='0')
{
continue;
}
else if(X_ComplementOperation[j]=='0' &&c=='1')
{
Register[j]='1';
c='0';
continue;
}
else if(X_ComplementOperation[j]=='1'&& c=='0')
{
Register[j]='1';
c='0';
continue;
}
else if(a[j]=='1'&& c=='1')
{
Register[j]='0';
c='1';
continue;
}
}
}
//printf("未移位是寄存器的數據：%s ",Register);
//移位的操作
if(i<Y_Length-3)
{
for(int j=strlen(Register)-1;j>1;j--)
{
Register[j]=Register[j-1];
}
Register[1]=Register[0];
}
printf("C操作后寄存器的數據：%s ",Register);
break;
}
default:
{
printf("對不起，出現無法解決的錯誤,程序將要退出！ ");
exit(0);
}
}
}
printf("最后寄存器的數據：%s ",Register);
//轉化為補碼
for(int i=0;i<strlen(Register)-2;i++)
{
d[i]=Register[i];
}
d[strlen(Register)-2]='';
if(d[0]=='0')
{
d[1]='.';
}
if(d[0]=='1')
{
d[1]='.';
d[strlen(Register)]='';
}
printf("[X*Y]補是：%s ",d);
//轉化為真值
if(d[0]=='1')
{
d[0]='-';
d[1]='0';
for(int i=strlen(d);i>2;i--)
{
d[i]=d[i-1];
}
d[2]='.';
d[strlen(Register)]='';
}
return d;
}
我也知道大家可能主要是需要算法的具體實現，因此代碼中注解較多。
這里我也歡迎大家交流，希望大家可以指出代碼里的錯誤和不足，謝謝！
參考文獻
[1]武濤,智洋,白麗珍.三種機器碼的聯系與剖析[J].大學教育,2017(04):18-19+22.
[2]王曉東,富坤,耿恒山,秘海曉,孫曉麗.在8位微程序控制的模型計算機中Booth算法的實現[J].河北科技大學學報,2012,33(05):443-447.
下面說下我的運行環境（在window VS中可能無法運行）：
操作系統：Ubuntu16
編譯器：gcc
總結
以上是生活随笔為你收集整理的补码一位乘法（Booth算法，C语言实现）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： CSC 命令编译cs文件
- 下一篇： 工信部ICP备案后，是否还需要公安备案