布思演算法——基於二進位制佇列的Java實現

摘要： 前面一篇提到二進位制佇列實現了 N位二進位制的補碼，那麼我們來實現布思演算法。 關於BinaryQueue：https://www.cnblogs.com/XT-xutao/p/10050518.html 先來思考：我們這樣實現二進位制乘法呢？ 對於無符號整數，是可以轉化為加法的：...

前面一篇提到二進位制佇列實現了 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

根據流程圖就可以實現了。

那麼程式碼怎麼實現呢？

 1 package computerOrganizationAndArchitecture.IntegerOperation;
 2 
 3 import computerOrganizationAndArchitecture.BinaryQueue;
 4 
 5 /**
 6* Created by XuTao on 2018/12/1 19:27
 7* 用BinaryQueue實現布思演算法 （Java語言）
 8*/
 9 public class Booth {
10BinaryQueue Q, M, A;// Q：乘數； M：被乘數; A: 附加
11private String n1,n2;
12public Booth(String str1, String str2) {//要進行操作的兩個二進位制數的字串模式
13this.n1=str1;
14this.n2=str2;
15int len; // 最長的長度（如果兩個二進位制不一樣長的話）
16//擴充套件短的那個
17if (n1.length() > n2.length()) {
18String s = "";
19len = n1.length() - n2.length();
20for (int i = 0; i < len; i++) {
21s += n2.charAt(0);
22}
23n2 = s + n2;
24}
25else if (n1.length()<n2.length()){
26String s = "";
27len = n2.length() - n1.length();
28for (int i = 0; i < len; i++) {
29s += n1.charAt(0);
30}
31n1 = s + n1;
32System.out.println(n1);
33}
34else len = n1.length();
35 
36Q = new BinaryQueue(n1);
37M = new BinaryQueue(n2);
38A = new BinaryQueue(len);
39int Q0 = 0; //Q的最低位，初始化為0，用於判斷要進行的操作
40 
41System.out.println(A.getStr() + " " + Q.getStr() + " " + Q0 + " " + M.getStr());
42for (int i = 0; i < len; i++) {
43if (Q.getLast() == 1 && Q0 == 0) {//1-0 模式，A= A-M，
44A = A.subtract(M);
45} else if (Q.getLast() == 0 && Q0 == 1) {
46A = A.add(M);
47}
48//AQQ0右移一位
49Q0 = Q.getLast();
50Q.shiftRight();
51Q.set(0, A.getLast());
52A.shiftRightArithmetically();
53 
54System.out.println(A.getStr() + " " + Q.getStr() + " " + Q0 + " " + M.getStr());
55}
56BinaryQueue bq = new BinaryQueue(A.getStr() + Q.getStr());
57System.out.println(A.getStr() + Q.getStr());
58System.out.println(bq.getInt());
59}
60 
61public static void main(String[] args) {
62new Booth("0011", "1111");//3 * -1 = -3
63new Booth("111111", "001111");//-1 * 15 = -15
64new Booth("011110", "001111");//30 * 15 = 450
65}
66 
67 }

demo：

AQQ0M
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