booth算法

2014/03/25 13:52
阅读数 1.8K

转自http://hi.baidu.com/renmeman/item/621697b9e74816f284dd79db

今天看到一种实现乘法的新算法——BOOTH算法,现在刚刚摸索到算法的本质,知道为什么这样做就可以实现乘法功能。废话少说,具体介绍如下:

       布斯(Booth)算法是比较好的带符号数乘法的方法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断,根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0),移位操作是向右移动。

    乘法过程中,被乘数相对于乘积的左移操作可表示为乘以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串中,不需要操作

展开阅读全文
打赏
0
7 收藏
分享
加载中
更多评论
打赏
0 评论
7 收藏
0
分享
返回顶部
顶部