求布斯算法举例详解

布斯乘法算法（英语：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 位上进行。

怎么理解Booth算法

布思算法（booth

algorithm）的简单理解方法：

由于是第一次接触，对于其原理却一无所知，书上的解释以及网上的文章不知是自己才疏学浅还本来就是泛泛而谈，没有让我了解其本质。经过长时间的思考分析，最终找到了一种比较简单的理解方法。

举一个简单的例子，比如说计算×，在这里首先将乘数改写为 -

即

-

---------------------------------------------------

这样根据乘法分配律得×=×（0100）

类似于booth算法的重新编码形式，再将上述算式改写为

×=×0+1

+ × -1 0

最终再将上式合并到一起，可得由booth算法改写后的编码形式： × 0+10000-10

由此可见，乘数的数段"01"可以重新编码为“+1”,数段“10”可以重新编码为“-1”，数段“11”可重新编码为“0”

根据无符号二进制数乘法的过程可知，当乘数段为“00”只是对乘数进行了右移操作，故重新编码为“0”

由于上述推导过程是根据二进制数加减以及乘法分配律推导而来的，故对于由补码表示的负数乘法同样适用

如何清晰理解布斯算法Booth algorithm的原理

比较好的带符号数乘法的方法是布斯(Booth)算法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断，根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。

计算机组成原理，图中画箭头的地方，这个递推式是怎么来的呢？

在不考虑符号位的一位乘法的计算过程中

每次是根据乘数Y的最后一位，判断部分积中是否加上被乘数X

然后部分积和乘数都右移一位，依次计算，直到乘数为0

而Booth算法其实就是连带符号位一起考虑的一位乘法

在得到上图蓝框中的表达式后，可以发现，每次判断部分积中是否加上被乘数[X]补

不再根据乘数的最后一位，而是根据最后两位(Yₙ₊₁-Yₙ)来判断

若Zₙ表示部分积，初始Z₀=0

Z₁对应的乘数的最后两位为Yₙ₊₁和Yₙ，累加上(Yₙ₊₁-Yₙ)[X]补，再右移一位（乘2⁻¹）

Z₂对应的乘数的最后两位为Yₙ和Yₙ₋₁，累加上(Yₙ-Yₙ₋₁)[X]补，再右移一位（乘2⁻¹）

......

Zₙ对应的乘数的最后两位为Y₂和Y₁，累加上(Y₂-Y₁)[X]补，再右移一位（乘2⁻¹）

最后乘数Y中只剩Y₁和Yₛ，最后再加一次(Y₁-Yₛ)[X]补，即得最终的乘积[X×Y]补

2022计算机考研组成原理_第2章名词解释

第2章 数据编码和数据运算

(2001年，2002年)1.基数：在浮点数据编码中，对阶码所代表的指数值的数据，在计算机中是一个常数，不用代码表示。

(2003年)2.移码：带符号数据表示方法之一，符号位用1表示正，0表示负，其余位与补码相同。

(2004年)3.溢出：指数的值超出了数据编码所能表示的数据范围。

(2005年)4.偶校验码：让编码组代码中1的个数为偶数，违反此规律为校验错。

5.原码：带符号数据表示方法之一，一个符号位表示数据的正负，0代表正号，1代表负号，其余的代表数据的绝对值。

6.补码：带符号数据表示方法之一，正数的补码与原码相同，负数的补码是将二进制位按位取反后在最低位上加1。

7.反码：带符号数据的表示方法之一，正数的反码与原码相同，负数的反码是将二进制位按位取反。

8.阶码：在浮点数据编码中，表示小数点的位置的代码。

9.尾数：在浮点数据编码中，表示数据有效值的代码。

10.机器零：在浮点数据编码中，阶码和尾数都全为0时代表的0值。

11.上溢：指数的绝对值太大，以至大于数据编码所能表示的数据范围。

12.下溢：指数的绝对值太小，以至小于数据编码所能表示的数据范围。

13.规格化数：在浮点数据编码中，为使浮点数具有唯一的表示方式所作的规定，规定尾数部分用纯小数形式给出，而且尾数的绝对值应大于1/R，即小数点后的第一位不为零。

14.Booth算法：一种带符号数乘法，它采用相加和相减的操作计算补码数据的乘积。

15.海明距离：在信息编码中，两个合法代码对应位上编码不同的位数。

16.冯·诺依曼舍入法：浮点数据的一种舍入方法，在截去多余位时，将剩下数据的最低位置1。

17.检错码：能够发现某些错误或具有自动纠错能力的数据编码。

18.纠错码：能够发现某些错误并且具有自动纠错能力的数据编码。

19.奇校验码：让编码组代码中1的个数为奇数，违反此规律为校验错。

20.海明码：一种常见的纠错码，能检测出两位错误，并能纠正一位错误。

21.循环码：一种纠错码，其合法码字移动任意位后的结果仍然是一个合法码字。

22.桶形移位器：可将输入的数据向左、向右移动1位或多位的移位电路。

用Booth算法计算x乘以y x=0.110111,y=-0.101110 求详细的解题步骤

先求出[-x]补=1.0011

然后看[y]补=0.101(10)，为10，所以要加[-x]补，得

0.0000

+ 1.0011

= 1.0011 再右移一位得0.10011

然后看[y]补=0.10(11)，为11，所以直接右移一位得 0.010011

然后看[y]补=0.1(01)1，为01，所以要加[x]补,得

0.010011

+ 0.1101

= 1.000111 再右移一位得0.1000111

然后看[y]补=0.(10)11，为10，所以要加[-x]补，得

0.1000111

+ 1.0011

= 1.1011111 再右移一位得0.11011111

然后看[y]补=(0.1)011，为01，所以要加[x]补，得

0.11011111

+ 0.1101

= 1.10101111

因为是最后一步，所以不移位，得1.10101111

扩展资料：

Booth算法原理：

布斯算法将乘数看作从最低位开始的一串二进制数字。从最低位算起，只要这串数字为“0“，就不执行任何操作；当这串数字遇到第一个“1”时执行一次减法，即减被乘数与该位权值的乘积，而对于其后的“1”不执行任何操作；

当这串数字再变为“0”时，则遇到第一个“0”时执行一次加法，即加被乘数与该位权值的乘积，而对其后的“0”则不执行任何操作。如此一直进行到最高位 [1]  。

举例来说，假设被乘数是5，乘数是7，即进行二进制数00000101与00000111相乘。该算法将7看作为三个“1”后面跟有五个“0”的一串数字。对于第一个”1”，该算法将减去5×20，对于第二和第三个“1”，则不执行任何操作；当遇到第一个“0”时，加5×23，得到最后结果是35。