补码一位乘法
-
首先了解下什么是补码？
补码概念的理解，需要先从“模”的概念开始。 我们可以把模理解为一个容器的容量。当超出这个 容量时，会自动溢出。如：我们最常见到的时钟，其容量 是 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