台式算法

A. 求布斯算法举例详解

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