今天看到一种实现乘法的新算法——BOOTH算法,现在刚刚摸索到算法的本质,知道为什么这样做就可以实现乘法功能。废话少说,具体介绍如下:
布斯(Booth)算法是比较好的带符号数乘法的方法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断,根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0),移位操作是向右移动。
乘法过程中,被乘数相对于乘积的左移操作可
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示为乘以2,设y=y0,yly2…yn为被乘数,x为乘数,每次循环中的运算可表示为对于x(yi+1-yi)2^(n-i)项的加法运算(i=n,n-1,…,1,0)。这样, Booth算法所计算的结果可表示为:(被乘数是两数相乘的后者,如A×B中的被乘数是A,但是这里貌似与这个没有关系)
x×(0-yn)×2^0
+x×(yn-yn-1)×2^1
…
+x×(y1-y0)×2^n
=x×(-y0×2^n +y1×2^(n-1) +y2×2^(n-2)+……+yn×2^0)
=x×y(这里切记一点y0是符号位)
Booth算法表示如下表所示。在Booth算法中,操作的方式取决于表达式(yi+1-yi)的值,这个表达式的值所代表的操作为:
0 无操作
+1 加x
-1 减x
Booth算法操作表示
yi yi+1 操作说明
0 0 无处于0串中,不需要操作
0 1 加x 1串的结尾
1 0 减x 1串的开始
1 1 无处于1串中,不需要操作
例:用Booth算法计算2×(-3)。
解:[2]补=0010,[-3]补=1101,在乘法开始之前,R0和R1中的初始值为0000和1101,R2中的值为0010。
在乘法的第一个循环中,判断R1的最低位和辅助位为10,所以进入步骤1c,将R0的值减去
R2的值,结果1110送人R0,然后进入第二步,将R0和Rl右移一位,R0和R1的结果为1111、0110,辅助位为l。
在第二个循环中,首先判断Rl的最低位和辅助位为0l,所以进入步骤1b,作加法,
R0+R2=1111+0010,结果0001送入R0,这时R0R1的内容为0001 0110,在第二步右移后变为0000 1011,辅助位为0。
在第三次循环中,判断位为10,进入步骤lc,R0减去R2,结果1110送入R0,R1不变;步骤2移位后R0和R1的内容为1111 0101,辅助位为1。
第四次循环时,因两个判断位为11,所以不作加减运算,向右移位后的结果为1111 1010,这就是运算结果(—6)。(结果result={R0,R1})
在每次移位都是{R0,R1}同时移位。
用Booth补码一位乘法计算2 ×(-3)的过程
循环
步骤
乘积
(R0, R1, P)初始值
0000 1101 0
第一次循环
1c:减0010
1110 1101 0
2:右移1位
1111 0110 1
第二次循环
1b:加0010
0001 0110 1
2:右移1位
0000 1011 0
第三次循环
1c:减0010
1110 1011 0
2:右移1位
1111 0101 1
第四次循环
1a:无操作
1111 0101 1
2:右移1位
1111 1010 1
继续阅读
浙公网安备 33021202002483