文档介绍：Booth算法的实现
一、目的和要求
采用BOOTH算法,编程实现二进制数的乘法运算,进而了解计算机中定点运算的过程
二、BOOTH算法的算法思想
Booth算法是比较好的带符号数乘法的方法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断,根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0),移位操作是向右移动。 BOOTH算法的算法思想是让乘数近似于某个较大的整值,然后用这个数值与被乘数的乘积减去其对应这个整值数的补数与被乘数的乘积来进行计算,从而提高了乘法的运算效率。
三、BOOTH算法原理
Booth算法为补码一位乘,其具体实现过程为:给末位添加一个附加位x,与乘数的最后一位组成判断条件来决定部分积作何操作。其中,乘数最后一位与x一共有四种组合情况分别为:00,01,10,11。四种情况的具体操作分别为:00,部分积右移一位,01 部分积加被乘数的补码再右移一位形成新的部分积,10部分积加[-x]的补码后右移一位形成新的部分积,11部分积右移一位。
四、程序实现过程
此算法由主函数和一个求补函数,一个booth算法构成。
主函数
在主函数中,首先需要输入x的绝对值,x的符号以及y的绝对值,y的符号,其次,需要根据输入的值去调用求补函数求出x,y和(-x)的补码,最后再根据对booth函数的调用求得由booth算法实现的乘法的结果
求补函数
在求补函数中,在执行过程中需要先判断其符号位,根据其符号位求补,如果这个需要求补的数为正数则其补码就是这个正数,如果这个数是负数,则需要对其除符号位按位取反,再在末位加一。末位加一时需注意,若最后一位为零,则置末位为1,进位标志为零,反之,若最后一位为一,置末位为0,进位标志为1,向前进位。

在Booth算法的实现中,包括加法和移位两种操作。实现算法时,乘法运算前A寄存器被清零,作为初始部分积。Q寄存器末位清零,作为附加位的初态。被乘数的补码存在X中(双符号位),乘数的补码在Q高n+1位中,计数器C存放乘数的位数n。乘法开始后,根据Q寄存器末两位Qn,Qn+1的状态决定部分积与被乘数相加还是相减,或是不加也不减,然后按补码规则进行算数移位,这样重复n次。最后,根据Q的末两位状态决定部分积与被乘数相加还是相减,或是不加也不减,但不必移位,这样便可得到最后结果。
五、程序框图
求补函数
主函数
开始
输入X真值
输入X的符号
求X的补码
输入Y的真值
输入Y的符号
求Y的补码
输出Y的补码
输出-X的补码
输出Y的补码
Booth算法
输出结果
结束
开始
Int b
Buffer[0]=sign
Sign=0
X补=X
绝对值按位取反
末位加一
求得补码
输出补码
结束

Booth算法执行框图
开始
0→A,0→Qn+1
被乘数(补码)→X
乘数(补码)→Q
n→C
QnQn+1
(A)-(D) →A
(A)+(D) →A
A,Q同时算数右移一位
(C)-1→C
C=0?
QnQn+1
(A)+(X) →A
(A)-(X) →A
结束
01
10
00