C++ 程序实现 Booth 乘法算法，用于将 2 个有符号数相乘
c++server side programmingprogramming
Booth 算法是一种乘法算法，它将两个有符号二进制数以 2 的补码表示法相乘。Booth 使用的台式计算器的移位速度比加法更快，因此他创建了该算法来提高其速度。
算法
开始 将被乘数放入 BR，将乘数放入 QR 然后该算法按照以下条件工作: 1. 如果 Qn 和 Qn+1 相同，即 00 或 11，则执行算术移位 1 位。 2.如果 Qn Qn+1 = 10，则执行 A= A + BR 并执行 1 位算术移位。 3. 如果 Qn Qn+1 = 01，则执行 A= A – BR 并执行 1 位算术移位。 结束
示例代码
#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
