查看“布斯乘法算法”的源代码

'''布斯乘法算法'''（{{lang-en|Booth's multiplication algorithm}}）是[[计算机]]中一种利用数的[[二补数|2的补码形式]]来计算乘法的算法。该算法由[[安德鲁·唐纳德·布思]]于1950年发明，当时他在[[伦敦大学]][[柏贝克学院]]做[[晶体学]]研究。布斯曾使用过一种[[计算器|台式计算器]]，由于用这种计算器来做移位计算比加法快，他发明了该算法来加快计算速度。布斯算法在[[计算机体系结构]]学科中备受关注。

==算法描述==
对于''N''位乘数''Y''，布斯算法检查其2的[[补码]]形式的最后一位和一个隐含的低位，命名为''y''<sub>-1</sub>，初始值为0。对于''y''<sub>''i''</sub>, ''i'' = 0, 1, ..., ''N'' - 1，考察''y''<sub>''i''</sub>和''y''<sub>''i'' - 1</sub>。当这两位相同时，存放积的[[累加器]]''P''的值保持不变。当''y''<sub>''i''</sub> = 0且''y''<sub>''i'' - 1</sub> = 1时，被乘数乘以2<sup>''i''</sup>加到''P''中。当''y''<sub>''i''</sub> = 1且''y''<sub>''i'' - 1</sub> = 0时，从''P''中减去被乘数乘以2<sup>''i''</sup>的值。算法结束后，''P''中的数即为乘法结果。

该算法对被乘数和积这两个数的表达方式并没有作规定。一般地，和乘数一样，可以采用2的补码方式表达。也可以采用其他计数形式，只要支持加减法就行。这个算法从乘数的最低位执行到最高位，从''i'' = 0开始，接下来和2<sub>''i''</sub>的乘法被累加器''P''的算术右移所取代。较低位可以被移出，加减法可以只在''P''的前''N''位上进行。<ref>
{{cite book
 | title = Signal processing handbook
 | author = Chi-hau Chen
 | publisher = CRC Press
 | year = 1988
 | isbn = 9780824779566
 | page = 234
 | url = http://books.google.com/books?id=10Pi0MRbaOYC&pg=PA234
 }}</ref>

==典型实现==
布斯算法的实现，可以通过重复地在''P''上加两个预设值''A''和 '' ''S'' ''其中的一个，然后对''P''实施算术右移。设''m''和''r''分别为被乘数和乘数，再令''x''和''y''分别为''m''和''r''中的数字位数。
#确定''A''和''S''的值，以及''P''的初始值。这三个数字的长度都应等于（''x'' + ''y'' + 1）：
##对于''A''，以''m''的值填充前x位（最靠左的位），用零填满剩下的（''y'' + 1）位；
##对于''S''，以（ - ''m''）的值填充前x位，用零填满剩下的（''y'' + 1）位；
##对于''P''：用0填满最左的''x''位，将''r''的值附加在尾部；最右一位用零占位（辅助位，当i=0时i-1=-1,指的就是这个辅助位）；
#考察''P''的最右两位：
##如果等于01，求出''P'' + ''A''的值，忽略上溢；
##如果等于10，求出''P'' + ''S''的值，忽略上溢；
##如果等于00，不做任何运算，在下一步中直接采用''P''的值；
##如果等于11，不做任何运算，在下一步中直接采用''P''的值。
#对第2步中得到的值进行算术右移一位，并将结果赋给''P''；
#重复第2步和第3步，一共做''y''次；
#舍掉''P''的最右一位，得到的即为''m''和''r''的积。

换另一种说法：把前x位用一个单独的数R0表示，中间y位用另一个数表示R1表示，辅助位用Z表示
在这里，要通过重复的把R0加上或者减去m来得到结果。具体如下：
初始值R0=0,R1=r.Z=0,此时来考查yi和yi-1这两位，在这里就是m的最后一位和Z的值。这里要说下为什么每次看的都是这两位了。在下边每次运算后都会把R0,R1,Z中的值右移一次，RO的最后一位移入R1的高位，R1的最后一位移入Z。这里要注意的是在右移R0时，如果他的最高位是1,则移位后最高位用1填充，如果最高位是0，移位后最高位用0填充。接下来要按m的最后一位和Z的值来判断怎么加减了：
##如果为01,则R0+m，进位忽略。然后R0,R1,Z右移一位，再下一步判断，直到把R1的每一位都判断过后为结束
##如果为10,则R0-m，借位忽略（只要x位的R0的值）。然后R0,R1,Z右移一位，再下一步判断，直到把R1的每一位都判断过后为结束
##如果为00或是11,则R0的值保持不变。然后R0,R1,Z右移一位，再下一步判断，直到把R1的每一位都判断过后为结束
最后是结果，结果就是R0并上R1的值。比如R0=3,R1=25,结果就是325.

==算法原理==
考虑一个由若干个0包围着若干个1的正的[[二进制]]乘数，比如00111110，积可以表达为：
: <math> M \times \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 1 \; 1 \; 0 \,^{\prime\prime} = M \times(2^5 + 2^4 + 2^3 + 2^2 + 2^1) =  M \times 62 </math>
其中，M代表被乘数。变形为下式可以使运算次数可以减为两次：
: <math> M \times \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \; 0 \; 0 \mbox{-1} \; 0 \,^{\prime\prime} = M \times(2^6 - 2^1) = M \times 62</math>。

事实上，任何二进制数中连续的1可以被分解为两个二进制数之差：

: <math> (\ldots 0 \overbrace{1 \ldots 1}^{n} 0 \ldots)_{2} \equiv (\ldots 1 \overbrace{0 \ldots 0}^{n} 0 \ldots)_{2} - (\ldots 0 \overbrace{0 \ldots 1}^{n} 0 \ldots)_2</math>。

因此，我们可以用更简单的运算来替换原数中连续为1的数字的乘法，通过加上乘数，对部分积进行[[位操作#.E7.A7.BB.E4.BD.8D|移位运算]]，最后再将之从乘数中减去。它利用了我们在针对为零的位做乘法时，不需要做其他运算，只需移位这一特点，这很像我们在做和99的乘法时利用99 = 100 − 1这一性质。这种模式可以扩展应用于任何一串数字中连续为1的部分（包括只有一个1的情况）。那么，

: <math> M \times \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 0 \; 1 \; 0 \,^{\prime\prime} = M \times(2^5 + 2^4 + 2^3 + 2^1) = M \times 58 </math>
: <math> M \times \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \mbox{-1} \; 0 \; 1 \; 0 \,^{\prime\prime} = M \times(2^6 - 2^3 + 2^1) = M \times 58</math>。

布斯算法遵从这种模式，它在遇到一串数字中的第一组从0到1的变化时（即遇到01时）执行加法，在遇到这一串连续1的尾部时（即遇到10时）执行减法。这在乘数为负时同样有效。当乘数中的连续1比较多时（形成比较长的1串时），布斯算法较一般的乘法算法执行的加减法运算少。

==参考来源==
{{reflist}}

==延伸阅读==
# Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2 [http://bwrc.eecs.berkeley.edu/Classes/icdesign/ee241_s00/PAPERS/archive/booth51.pdf]
# Collin, Andrew. [http://www.cs.man.ac.uk./CCS/res/res05.htm#e Andrew Booth's Computers at Birkbeck College]. ''Resurrection'', Issue 5, Spring 1993. London: Computer Conservation Society.
# Patterson, David and John Hennessy. ''Computer Organization and Design: The Hardware/Software Interface, Second Edition''. ISBN 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
# Stallings, William. ''Computer Organization and Architecture: Designing for performance, Fifth Edition''. ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.

==外部链接==
*[http://www.geoffknagge.com/fyp/booth.shtml Radix-4 Booth Encoding]
*[https://web.archive.org/web/20120216060633/http://www.russinoff.com/libman/text/node38.html Radix-8 Booth Encoding] in [https://web.archive.org/web/20070927194831/http://www.russinoff.com/libman/ A Formal Theory of RTL and Computer Arithmetic]
*[https://web.archive.org/web/20120429071825/http://fourier.eng.hmc.edu/e85/lectures/arithmetic_html/node10.html Booth's Algorithm]
*[http://www.ecs.umass.edu/ece/koren/arith/simulator/Booth/ Booth's Algorithm JavaScript Simulator]
*[https://web.archive.org/web/20120304074323/http://hdlsnippets.com/verilog_booth_multiplier Implementation in Verilog]
*[http://philosophyforprogrammers.blogspot.com/2011/05/booths-multiplication-algorithm-in.html Implementation in Python]
*[http://hi.baidu.com/moshu1234/blog/item/050be5cf6450c70493457ec9.html 布斯算法 (带符号的二进制乘法)]
[[Category:電腦架構]]
[[Category:计算机科学]]
[[Category:算法]]
[[Category:二进制算术]]