Chương trình C++ triển khai thuật toán nhân Booth cho 2 số có dấu

Thuật toán Booth là một thuật toán nhân thực hiện phép nhân hai số nhị phân có dấu trong ký pháp bù 2. Booth sử dụng các máy tính bàn có tốc độ dịch chuyển nhanh hơn phép cộng và đã tạo ra thuật toán này để tăng tốc độ tính toán.

Thuật toán

Bắt đầu
    Đặt số bị nhân vào BR và số nhân vào QR
    Sau đó thuật toán hoạt động theo các điều kiện sau:
    1. Nếu Qn và Qn+1 giống nhau (00 hoặc 11): thực hiện dịch chuyển số học 1 bit.
    2. Nếu Qn Qn+1 = 10: thực hiện A = A + BR rồi dịch chuyển số học 1 bit.
    3. Nếu Qn Qn+1 = 01: thực hiện A = A - BR rồi dịch chuyển số học 1 bit.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

void add(int a[], int x[], int q);
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);
}

void add(int ac[], int x[], int q) {
    int i, c = 0;
    for (i = 0; i < q; i++) {
        ac[i] = ac[i] + x[i] + c;
        if (ac[i] > 1) {
            ac[i] = ac[i] % 2;
            c = 1;
        } else {
            c = 0;
        }
    }
}

void ashr(int ac[], int qr[], int &qn, int q) {
    int temp, i;
    temp = ac[0];
    qn = qr[0];
    cout << "\t\tashr\t\t";
    for (i = 0; i < q - 1; i++) {
        ac[i] = ac[i + 1];
        qr[i] = qr[i + 1];
    }
    qr[q - 1] = temp;
}

void display(int ac[], int qr[], int qrn) {
    int i;
    for (i = qrn - 1; i >= 0; i--)
        cout << ac[i];
    cout << " ";
    for (i = qrn - 1; i >= 0; i--)
        cout << qr[i];
}

int main(int argc, char **argv) {
    int mt[10], br[10], qr[10], sc, ac[10] = { 0 };
    int brn, qrn, i, qn, temp;

    cout << "\n--Nhập số bị nhân và số nhân ở dạng bù 2 có dấu nếu âm--";
    cout << "\n Số bit của số bị nhân = ";
    cin >> brn;
    cout << "\nSố bị nhân = ";
    for (i = brn - 1; i >= 0; i--)
        cin >> br[i];
    for (i = brn - 1; i >= 0; i--)
        mt[i] = br[i];
    complement(mt, brn);

    cout << "\nSố bit của số nhân = ";
    cin >> qrn;
    sc = qrn;
    cout << "Số nhân = ";
    for (i = qrn - 1; i >= 0; i--)
        cin >> qr[i];

    qn = 0;
    temp = 0;
    cout << "qn\tq[n+1]\t\tBR\t\tAC\tQR\t\tsc\n";
    cout << "\t\t\tinitial\t\t";
    display(ac, qr, qrn);
    cout << "\t\t" << sc << "\n";

    while (sc != 0) {
        cout << qr[0] << "\t" << qn;
        if ((qn + qr[0]) == 1) {
            if (temp == 0) {
                add(ac, mt, qrn);
                cout << "\t\ttrừ BR\t";
                for (i = qrn - 1; i >= 0; i--)
                    cout << ac[i];
                temp = 1;
            } else if (temp == 1) {
                add(ac, br, qrn);
                cout << "\t\tcộng BR\t";
                for (i = qrn - 1; i >= 0; i--)
                    cout << ac[i];
                temp = 0;
            }
            cout << "\n\t";
            ashr(ac, qr, qn, qrn);
        } else if (qn - qr[0] == 0) {
            ashr(ac, qr, qn, qrn);
        }
        display(ac, qr, qrn);
        cout << "\t";
        sc--;
        cout << "\t" << sc << "\n";
    }
    cout << "Kết quả = ";
    display(ac, qr, qrn);
}

Kết quả đầu ra

--Nhập số bị nhân và số nhân ở dạng bù 2 có dấu nếu âm--
Số bit của số bị nhân = 5
Số bị nhân = 0 1 1 1 1
Số bit của số nhân = 5
Số nhân = 1 0 1 1 1
qn  q[n+1]      BR      AC      QR      sc
                initial         00000 10111   5
1   0   trừ BR  10001   ashr    11000 11011   4
1   1   ashr    11100 01101   3
1   1   ashr    11110 00110   2
0   1   cộng BR 01101   ashr    00110 10011   1
1   0   trừ BR  10111   ashr    11011 11001   0
Kết quả = 11011 11001