《计算机组成与体系结构（原书第4版）》 —2.4.5　计算机、算术和布斯算法

2.4.5　计算机、算术和布斯算法

本章介绍的计算机算术可能看起来很简单、直接，但它在计算机体系结构中是一个主要的研究领域。主要重点是对可以在软件、固件或硬件中实现的算术函数的实现。这个领域的研究人员正在设计更高级的中央处理单元、开发高性能算术电路以及为嵌入式系统特定应用电路领域做出贡献。他们正在研究算法和新的硬件以实现快速加法、减法、乘法和除法，以及快速浮点运算。研究人员正在寻找使用非传统方法的方案，如快速先行进位原理、剩余算术和布斯算法。布斯算法是一个这样的好例子，在有符号的2的补码数情境下，它给你一个如何通过巧妙的算法增强一个简单算术运算的概念。

当乘以一个用2的补码表示的数时，虽然布斯算法通常会提高性能，但我们有引入该算法的另一个动机。在2.4.2节中，我们介绍了2的补码的例子并且看到这个数可以当作无符号数。我们只需执行“常规”加法，如下例所示：

对于2的补码执行减法操作也是如此。但是，现在考虑用铅笔和纸计算一下用2的补码表示的数标准的乘法过程：

“常规”乘法明显地产生了不正确的结果。对于这个问题有许多种解决方案，如将两个值转换为正数，执行常规乘法，然后记住是一个还是两个数为负数，以确定结果是正还是负。布斯算法不仅解决了这个困境，而且还加速了乘法进程。

布斯算法的一般思路是当乘数中存在连续的0或1时，乘法的速度会加快。容易看到连续的0能提高性能。例如，如果我们使用经过考验的手算方法，发现计算978×1001比计算978×999更容易。这是因为在1001中有两个零。但是，如果重写这两个问题如下所示：

就可以看到这两个问题事实上在难度上是相等的。

我们的目标是利用以二进制数表示的一串数字的优势，这与使用一串0的优势大致相同。我们可以使用上面的重写方法。例如，二进制数0110可以被重写为1000-0010=-0010+1000。这两个数被替换为一个“-”（由字符串中最右边的1决定），后跟一个“+”（由字符串中最左边的1向左移动一个位置来确定）。

考虑下面的标准乘法示例：

布斯算法的想法是当我们看到一串1最右边的1时用减法替换乘数中的一串1（或减去0011），随后为一串1最左边的1之后的位加1（或加001100）。对于一串1的中间位，我们现在可以使用简单的移位：

在布斯算法中，如果被乘数和乘数都是n位2的补码数，那么结果是一个2n位2的补码数。因此，当我们执行中间步骤时，必须将n位数字扩展到2n位。如果需要扩展的数字是负数，那么我们必须扩展符号。例如，值10002（-8）扩展到8位将是111110002。我们连续操作乘数中的位，完成一个步骤移位一次。但是，我们感兴趣的是乘数中的位对，并根据以下规则进行操作：

1.如果当前乘数位为1且前一位为0，则我们处于数字串1的开始位置，因此从乘积中减去被乘数（或加上对应的负数）。

2.如果当前乘数位为0且前一位为1，则我们处于数字串1的末尾位置，因此将被乘数加到乘积中。

3.如果它是一对00或一对11，则不执行算术运算（处在数字串0或数字串1的中间），只需移动。这个算法的优势就在这一步：我们现在可以把数字串1当作数字串0来看待，除了移位不做任何事情。

注意：第一次在乘数中选择一个位对时，我们应该假设一个虚构的0为“前一个”位。然后我们简单地向左移动一位作为下一对。

例2.26说明了使用布斯算法和带符号的4位2的补码，计算乘法-3×5的过程。

例2.26在4位2的补码中，-3表示为11012。扩展至8位变为111111012。它的补码是000000112。当我们看到在乘数中最右边的1时，它是一个数字串1的开头，所以把它看作数字串10：

例2.27让我们来看53×126这个更大的例子：

注意，我们没有显示超出需要的扩展符号位并且只使用了最右边的16位。在乘数中整个1的数字串被一个减法（加11001011）后跟一个加法所替换。在中间要做的只是简单移位，移位对计算机来说很容易（我们将在第3章中看到）。如果计算机执行加法所需的时间比移位所需的时间长很多，那么布斯算法可以大大提高性能。这当然一定程度上取决于乘数。如果乘数有0或1的数字串，则算法会实现得很好。如果乘数由0或1交替的数字串组成（最坏的情况），则使用布斯算法可能比标准方法需要更多的操作。

计算机通过加法和移位存储在寄存器中的值来执行布斯算法。这时需要一个名为算术移位的特殊类型的移位来保留符号位。许多书只是对寄存器的算术移位和加法操作阐述了布斯算法，并且看起来与前面的方法完全不同。我们介绍的布斯算法更类似于大家都熟悉的铅笔和纸的方法，但它等同于别处介绍的计算机算法。

已经有许多为快速乘法开发的算法，但是很多都不适用于有符号乘法。布斯算法不仅允许在大多数情况下能更快地执行乘法，而且它还能在应用于有符号数时带来更多的好处。