深入理解布什乘法算法：原理与实现

布什算法是一种乘法算法，用于对两个二进制补码表示的有符号二进制数进行乘法运算。

当年，布什使用的台式计算器在进行移位操作时比加法运算更快，因此他设计了这种算法来提高计算速度。如今，布什算法在计算机体系结构的研究中仍然占据重要地位。下面我们就来深入探讨一下该算法的具体实现。

示例：

输入 : 0110, 0010
输出 :  qn      q[n+1]                  AC      QR     sc(step count)
                          initial         0000   0010        4
          0       0       rightShift      0000   0001        3
          1       0       A = A - BR      1010
                          rightShift      1101   0000        2
          0       1       A = A + BR      0011
                          rightShift      0001   1000        1
          0       0       rightShift      0000   1100        0

Result=1100

算法：

> 首先将被乘数放入 BR 中，将乘数放入 QR 中，

> 然后算法将根据以下条件进行操作：

> 1. 如果 Qn 和 Qn+1 相同，即为 00 或 11，则执行算术右移 1 位。

> 2. 如果 Qn Qn+1 = 01，则执行 A = A + BR，并执行算术右移 1 位。

> 3. 如果 Qn Qn+1 = 10，则执行 A = A – BR，并执行算术右移 1 位。

C++

// CPP code to implement booth‘s algorithm
#include 

using namespace std;

// function to perform adding in the accumulator
void add(int ac[], int x[], int qrn)
{
    int i, c = 0;
    
    for (i = 0; i  1) {
            ac[i] = ac[i] % 2;
            c = 1;
        }
        else
            c = 0;
    }
}

// function to find the number‘s complement
void complement(int a[], int n)
{
    int i;
    int x[8] = {0};
    x[0] = 1;
    
    for (i = 0; i < n; i++) {
        a[i] = (a[i] + 1) % 2;
    }
    add(a, x, n);
}

// function to perform right shift
void rightShift(int ac[], int qr[], int& qn, int qrn)
{
    int temp, i;
    temp = ac[0];
    qn = qr[0];
    
    cout << "\t\trightShift\t";
    
    for (i = 0; i = 0; i--)
        cout << ac[i];
    cout <= 0; i--)
        cout << qr[i];
}

// Function to implement booth's algo
void boothAlgorithm(int br[], int qr[], int mt[], int qrn, int sc)
{

    int qn = 0, ac[10] = { 0 };
    int temp = 0;
    cout << "qn\tq[n+1]\t\tBR\t\tAC\tQR\t\tsc
";
    cout << "\t\t\tinitial\t\t";
    
    display(ac, qr, qrn);
    cout << "\t\t" << sc << "
";
    
    while (sc != 0) {
        cout << qr[0] << "\t" << qn;
        
        // SECOND CONDITION
        if ((qn + qr[0]) == 1)
        {
            if (temp == 0) {
                
                // subtract BR from accumulator
                add(ac, mt, qrn);
                cout <= 0; i--)
                    cout << ac[i];
                temp = 1;
            }
            
            // THIRD CONDITION
            else if (temp == 1)
            {
                // add BR to accumulator
                add(ac, br, qrn);
                cout <= 0; i--)
                    cout << ac[i];
                temp = 0;
            }
            cout << "
\t";
            rightShift(ac, qr, qn, qrn);
        }
        
        // FIRST CONDITION
        else if (qn - qr[0] == 0)
            rightShift(ac, qr, qn, qrn);
       
        display(ac, qr, qrn);
       
        cout << "\t";
        
        // decrement counter
        sc--;
        cout << "\t" << sc <= 0; i--)
        mt[i] = br[i]; 
        
    reverse(br, br + brn);

    complement(mt, brn);

    // No. of multiplier bit
    qrn = 4;
    
    // sequence counter
    sc = qrn;
    
    // multiplier
    int qr[] = { 1, 0, 1, 0 };
    reverse(qr, qr + qrn);

    boothAlgorithm(br, qr, mt, qrn, sc);

    cout << endl
         <= 0; i--)
        cout << qr[i];
}

“

// Java code to implement booth‘s algorithm

class GFG

{

// function to perform adding in the accumulator

static void add(int ac[], int x[], int qrn)

{

int i, c = 0;

for (i = 0; i < qrn; i++)

{