C ++程序，实现布斯的乘法算法来对两个有符号数相乘

Booth的算法是一种乘法算法，将两个有符号的二进制数乘以2的恭维表示法。Booth使用的台式计算器在转换时比添加时要快，并创建了算法来提高速度。

算法

Begin    Put multiplicand in BR and multiplier in QR       and then the algorithm works as per the following conditions:    1. If Qn and Qn+1 are same i.e. 00 or 11 perform arithmetic shift by 1 bit.    2. If Qn Qn+1 = 10 do A= A + BR and perform arithmetic shift by 1 bit.    3. If Qn Qn+1 = 01 do A= A – BR and perform arithmetic shift by 1 bit. End

范例程式码

#include<iostream> using namespace std; void add(int a[], int x[], int q); void complement(int a[], int n) {    int i;    int x[8] = { NULL };    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--Enter the multiplicand and multipier in signed 2's       complement form if negative--";       cout << "\n Number of multiplicand bit=";       cin >> brn;       cout << "\nmultiplicand=";       for (i = brn - 1; i >= 0; i--)          cin >> br[i]; //multiplicand       for (i = brn - 1; i >= 0; i--)          mt[i] = br[i];       complement(mt, brn);       cout << "\nNo. of multiplier bit=";       cin >> qrn;       sc = qrn;       cout << "Multiplier=";       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\tsubtracting BR\t";                   for (i = qrn - 1; i >= 0; i--)                      cout << ac[i];                   temp = 1;                }             else if (temp == 1) {                add(ac, br, qrn);                cout << "\t\tadding 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 << "Result=";    display(ac, qr, qrn); }

输出结果

--Enter the multiplicand and multipier in signed 2's complement form if negative-- Number of multiplicand bit=5 multiplicand=0 1 1 1 1 No. of multiplier bit=5 Multiplier=1 0 1 1 1 qn q[n+1] BR AC QR sc initial 00000 10111 5 1 0 subtracting BR 10001 ashr 11000 11011 4 1 1 ashr 11100 01101 3 1 1 ashr 11110 00110 2 0 1 adding BR 01101 ashr 00110 10011 1 1 0 subtracting BR 10111 ashr 11011 11001 0 Result=11011 11001