前面一篇提到二进制队列实现了 N位二进制的补码，那么我们来实现布思算法。

关于BinaryQueue：https://www.cnblogs.com/XT-xutao/p/10050518.html

 

先来思考：我们这样实现二进制乘法呢？

对于无符号整数，是可以转化为加法的：

那么补码形式呢？好像一些也是可以用上面这种转化为加法的：

 

上面被乘数-7是小于0的，但是乘数为负的时候好像就不能工作了，因为不能正确地得出部分积。

怎么办呢？

还有一种方法： 就是在乘之前先判断符号，如果异号，则结果为负，用他们的绝对值形式乘就可以了，最后加符号就行。

但是，这种方法似乎太麻烦了，我们更偏向于——布思算法（BOOTH）

布思算法是基于： 2^n+2^n-1......2^n-k  =  2^(n+1) - 2^(n-k)

它有两大优点：

1.避免了如上的那种复杂操作。

2.减少了不必要的加法，节约了时间。

 

那么在计算机底层是怎么实现的呢？

可以用几个寄存器搞定：

A：附加寄存器，初始化0

Q：乘数寄存器

M：被乘数寄存器

Q0：乘数的最低位，初始化0

根据流程图就可以实现了。最后的结果是AQ寄存器里的值。

 

更新：前面讲那个BinaryQueue方法不好，直接用字符串形式的二进制表示更简单：

1     public String multiply(String Q,String M){ 2         char Q0 = '0'; 3         String A = get01(Q.length(),"0"); 4         for (int i=0;i

 

那么代码怎么实现（BinaryQueue）呢？

1 package com.computerOrganizationAndArchitecture.IntegerOperation; 2  3 import com.computerOrganizationAndArchitecture.BinaryQueue; 4  5 /** 6  * Created by XuTao on 2018/12/1 19:27 7  * 用BinaryQueue实现布思算法 （Java语言） 8  */ 9 public class Booth {10     BinaryQueue Q, M, A;  // Q：乘数； M：被乘数; A: 附加11     private String n1,n2;12     public Booth(String str1, String str2) {
    //要进行操作的两个二进制数的字符串模式13         this.n1=str1;14         this.n2=str2;15         int len; // 最长的长度（如果两个二进制不一样长的话）16         //扩展短的那个17         if (n1.length() > n2.length()) {18             String s = "";19             len = n1.length() - n2.length();20             for (int i = 0; i < len; i++) {21                 s += n2.charAt(0);22             }23             n2 = s + n2;24         }25         else if (n1.length()

0000 0011 0 1111   第0周期

0000 1001 1 1111   第1周期

0000 0100 1 1111   第2周期

1111 1010 0 1111   第3周期

1111 1101 0 1111   第4周期

结果：

11111101

-3

000000 111111 0 001111

111000 111111 1 001111

111100 011111 1 001111

111110 001111 1 001111

111111 000111 1 001111

111111 100011 1 001111

111111 110001 1 001111

111111110001

-15

000000 011110 0 001111

000000 001111 0 001111

111000 100111 1 001111

111100 010011 1 001111

111110 001001 1 001111

111111 000100 1 001111

000111 000010 0 001111

000111000010

450