
_START_ARTICLE_
布斯乘法算法
_START_PARAGRAPH_
布斯乘法算法（英语：Booth's multiplication algorithm）是计算机中一种利用数的2的补码形式来计算乘法的算法。该算法由安德鲁·唐纳德·布思于1950年发明，当时他在伦敦大学柏贝克学院做晶体学研究。布斯曾使用过一种台式计算器，由于用这种计算器来做移位计算比加法快，他发明了该算法来加快计算速度。布斯算法在计算机体系结构学科中备受关注。
_START_SECTION_
算法描述
_START_PARAGRAPH_
对于N位乘数Y，布斯算法检查其2的补码形式的最后一位和一个隐含的低位，命名为y₋₁，初始值为0。对于yᵢ, i = 0, 1, ..., N - 1，考察yᵢ和yᵢ ₋ ₁。当这两位相同时，存放积的累加器P的值保持不变。当yᵢ = 0且yᵢ ₋ ₁ = 1时，被乘数乘以2ⁱ加到P中。当yᵢ = 1且yᵢ ₋ ₁ = 0时，从P中减去被乘数乘以2ⁱ的值。算法结束后，P中的数即为乘法结果。_NEWLINE_该算法对被乘数和积这两个数的表达方式并没有作规定。一般地，和乘数一样，可以采用2的补码方式表达。也可以采用其他计数形式，只要支持加减法就行。这个算法从乘数的最低位执行到最高位，从i = 0开始，接下来和2ᵢ的乘法被累加器P的算术右移所取代。较低位可以被移出，加减法可以只在P的前N位上进行。