booth algorithm for multiplication仅用于乘以2个负数(-3 * -4)或一个正数和一个负数(-3 * 4)？每当我使用booth算法乘以2个正数时，我得到一个错误的结果。
例如：5 * 4
A = 101 000 0 // binary of 5 is 101
S = 011 000 0 // 2's complement of 5 is 011
P = 000 100 0 // binary of 4 is 100
x = 3 number of bits in m
y = 3 number of bits in r
m = 5
-m = m的2的补码
r = 4
@ ruakh回答后更新
5 * 4 = 20
m = 0101 is 5
r = 0100 is 4
A = 0101 0000 0
S = 1010 0000 0
P = 0000 0100 0
here 1 is the carry generated右移1位：110010000离开LSB：11001000（不等于20）
你没有为你的标志处理提供足够的空间。 5不是101，而是0101：它必须以0开头，因为以1开头的值是负数。 101实际上是-3：它是011的两个补码，即3.同样，4不是100，而是0100; 100是-4。因此，当你将101乘以100时，你实际上将-3乘以-4;这就是为什么你得到12。
Booth的算法用于有符号整数，也就是说，每个都可以是正数或负数或零。
这是一个示例C程序，它说明了将两个8位带符号（2的补码）整数相乘并获得16位有符号乘积的实现和中间结果：
#include <stdio.h>
#include <limits.h>
#include <string.h>
typedef signed char int8;
typedef short int16;
char* Num2BaseStr(unsigned long long num, unsigned base, int maxDigits)
{
static char s[sizeof(num) * CHAR_BIT + 1];
char* p = &s[sizeof(s) - 1];
memset(s, 0, sizeof(s));
do
{
*--p = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[num % base];
num /= base;
} while ((num != 0) || (p > s));
// Keep at most maxDigits digits if requested
if ((maxDigits >= 0) && (&s[sizeof(s) - 1] - p > maxDigits))
{
p = &s[sizeof(s) - 1] - maxDigits;
}
// Skip leading zeroes otherwise
else
{
while (*p == '0') p++;
}
return p;
}
int16 BoothMul(int8 a, int8 b)
{
int16 result = 0;
int16 bb = b;
int f0 = 0, f1;
int i = 8;
printf("a = %sb (%d)\n", Num2BaseStr(a, 2, 8), a);
printf("b = %sb (%d)\n", Num2BaseStr(b, 2, 8), b);
printf("\n");
while (i--)
{
f1 = a & 1;
a >>= 1;
printf(" %sb\n", Num2BaseStr(result, 2, 16));
printf("(%d%d) ", f1, f0);
if (!f1 && f0)
{
printf("+ %sb\n", Num2BaseStr(bb, 2, 16));
result += bb;
}
else if (f1 && !f0)
{
printf("- %sb\n", Num2BaseStr(bb, 2, 16));
result -= bb;
}
else
{
printf("no +/-\n");
}
printf("\n");
bb <<= 1;
f0 = f1;
}
printf("a * b = %sb (%d)\n", Num2BaseStr(result, 2, 16), result);
return result;
}
int main(void)
{
const int8 testData[][2] =
{
{ 4, 5 },
{ 4, -5 },
{ -4, 5 },
{ -4, -5 },
{ 5, 4 },
{ 5, -4 },
{ -5, 4 },
{ -5, -4 },
};
int i;
for (i = 0; i < sizeof(testData)/sizeof(testData[0]); i++)
printf("%d * %d = %d\n\n",
testData[i][0],
testData[i][1],
BoothMul(testData[i][0], testData[i][1]));
return 0;
}
输出：
a = 00000100b (4)
b = 00000101b (5)
0000000000000000b
(00) no +/-
0000000000000000b
(00) no +/-
0000000000000000b
(10) - 0000000000010100b
1111111111101100b
(01) + 0000000000101000b
0000000000010100b
(00) no +/-
0000000000010100b
(00) no +/-
0000000000010100b
(00) no +/-
0000000000010100b
(00) no +/-
a * b = 0000000000010100b (20)
4 * 5 = 20
a = 00000100b (4)
b = 11111011b (-5)
0000000000000000b
(00) no +/-
0000000000000000b
(00) no +/-
0000000000000000b
(10) - 1111111111101100b
0000000000010100b
(01) + 1111111111011000b
1111111111101100b
(00) no +/-
1111111111101100b
(00) no +/-
1111111111101100b
(00) no +/-
1111111111101100b
(00) no +/-
a * b = 1111111111101100b (-20)
4 * -5 = -20
a = 11111100b (-4)
b = 00000101b (5)
0000000000000000b
(00) no +/-
0000000000000000b
(00) no +/-
0000000000000000b
(10) - 0000000000010100b
1111111111101100b
(11) no +/-
1111111111101100b
(11) no +/-
1111111111101100b
(11) no +/-
1111111111101100b
(11) no +/-
1111111111101100b
(11) no +/-
a * b = 1111111111101100b (-20)
-4 * 5 = -20
a = 11111100b (-4)
b = 11111011b (-5)
0000000000000000b
(00) no +/-
0000000000000000b
(00) no +/-
0000000000000000b
(10) - 1111111111101100b
0000000000010100b
(11) no +/-
0000000000010100b
(11) no +/-
0000000000010100b
(11) no +/-
0000000000010100b
(11) no +/-
0000000000010100b
(11) no +/-
a * b = 0000000000010100b (20)
-4 * -5 = 20
a = 00000101b (5)
b = 00000100b (4)
0000000000000000b
(10) - 0000000000000100b
1111111111111100b
(01) + 0000000000001000b
0000000000000100b
(10) - 0000000000010000b
1111111111110100b
(01) + 0000000000100000b
0000000000010100b
(00) no +/-
0000000000010100b
(00) no +/-
0000000000010100b
(00) no +/-
0000000000010100b
(00) no +/-
a * b = 0000000000010100b (20)
5 * 4 = 20
a = 00000101b (5)
b = 11111100b (-4)
0000000000000000b
(10) - 1111111111111100b
0000000000000100b
(01) + 1111111111111000b
1111111111111100b
(10) - 1111111111110000b
0000000000001100b
(01) + 1111111111100000b
1111111111101100b
(00) no +/-
1111111111101100b
(00) no +/-
1111111111101100b
(00) no +/-
1111111111101100b
(00) no +/-
a * b = 1111111111101100b (-20)
5 * -4 = -20
a = 11111011b (-5)
b = 00000100b (4)
0000000000000000b
(10) - 0000000000000100b
1111111111111100b
(11) no +/-
1111111111111100b
(01) + 0000000000010000b
0000000000001100b
(10) - 0000000000100000b
1111111111101100b
(11) no +/-
1111111111101100b
(11) no +/-
1111111111101100b
(11) no +/-
1111111111101100b
(11) no +/-
a * b = 1111111111101100b (-20)
-5 * 4 = -20
a = 11111011b (-5)
b = 11111100b (-4)
0000000000000000b
(10) - 1111111111111100b
0000000000000100b
(11) no +/-
0000000000000100b
(01) + 1111111111110000b
1111111111110100b
(10) - 1111111111100000b
0000000000010100b
(11) no +/-
0000000000010100b
(11) no +/-
0000000000010100b
(11) no +/-
0000000000010100b
(11) no +/-
a * b = 0000000000010100b (20)
-5 * -4 = 20
5*4 =20
m=5,r=4,x=y=4
m=0101 , r=0100 , -m=1011 ,x=y=4
A=0101 0000 0
S=1011 0000 0
P=0000 0100 0
1. P=0000 0100 0 //last two bits are 00 so simply shift P
P=0000 0010 0
2. P=0000 0010 0 //last two bits are 00 so simply shift P
P=0000 0001 0
3. P=0000 0001 0 //last two bits are 10 so perform P = P+S
P=1011 0001 0
P=1101 1000 1 // after shifting P
4. P=1101 1000 1 //last two bits are 01 so perform P = P+A
P=0010 1000 1
P=0001 0100 0 // after shifting P
5. now remove LSB
the product is P=00010100(20)
我认为x应该是2而不是3 - 因为3是11，只有两位长。
下面是Booth算法的实现，根据其所谓的书“计算机组织与架构，第8版 - William Stallings”中的第9章所示的流程图。该程序将4位代表的两个数字相乘。当VERBOSE == 1时，程序显示算法的不同步骤.PS：程序将数字操作为字符串。
祝好运！
#include <stdio.h>
#define WORD 4
#define VERBOSE 1 //0
/*
* CSC 2304 - Al Akhawayn University
* Implementation of the Booth's Algorithm.
*/
void twosComplementAddition(char[], char[]);
void rightShift(char[], char);
void addition(char[], char[]);
char* twosComplementMultiplication(char M[], char Q[]) {
char C;
char *A = (char*) malloc(sizeof(char)*(2 * WORD + 1));
char processedQ[WORD+ 1];
char Q0, Q_1 = '0';
int i, j;
strcpy(A, "0000");
if (VERBOSE) {
printf("\n A | Q | M |");
printf("\n %s | %s | %s | Initial", A, Q, M);
printf("\n-------------------------------------------------------------");
}
for (i = 0, j = 1; i < WORD; i++, j++) {
Q0 = Q[WORD - 1];
if (VERBOSE) {
printf("\n %s | %s | %s | Cycle %d", A, Q, M, j);
}
if (Q0 == '0' && Q_1 == '1') {
addition(A, M);
if (VERBOSE) {
printf("\n %s | %s | %s | Addition", A, Q, M);
}
} else {
if (Q0 == '1' && Q_1 == '0') {
twosComplementAddition(A, M);
if (VERBOSE) {
printf("\n %s | %s | %s | Two's Complement", A, Q, M);
}
}
}
Q_1 = Q[WORD - 1];
rightShift(Q, A[WORD - 1]);
rightShift(A, A[0]);
if (VERBOSE) {
printf("\n %s | %s | %s | Right Shift", A, Q, M);
getch();
}
printf("\n-------------------------------------------------------------");
}
strcat(A, Q);
return A;
}
void rightShift(char reg[], char bit) {
int i;
for (i = WORD - 1; i > 0; i--) {
reg[i] = reg[i - 1];
}
reg[0] = bit;
}
void addition(char A[], char M[]) {
int i;
char c = '0';
for (i = WORD - 1; i >= 0; i--) {
if (A[i] == '0' && M[i] == '0') {
A[i] = c;
c = '0';
} else {
if ((A[i] == '1' && M[i] == '0') || (A[i] == '0' && M[i] == '1')) {
if (c == '0') {
A[i] = '1';
} else {
A[i] = '0';
}
} else {
if (A[i] == '1' && M[i] == '1') {
A[i] = c;
c = '1';
}
}
}
}
}
void twosComplementAddition(char A[], char M[]) {
int i;
char temp[WORD + 1];
for (i = 0; i < WORD; i++) {
if (M[i] == '0') {
temp[i] = '1';
} else {
temp[i] = '0';
}
}
temp[WORD] = '\0';
addition(temp, "0001");
addition(A, temp);
}
int main() {
char QQ[WORD + 1];
char M[WORD + 1];
char Q[WORD + 1];
char *result;
printf("\nBooth's Algorithm");
printf("\n*****************");
printf("\nEnter M: ");
scanf("%s", M);
printf("\nEnter Q: ");
scanf("%s", Q);
strcpy(QQ, Q);
result = twosComplementMultiplication(M, Q);
printf("\n%s * %s = %s", M, QQ, result);
printf("\n");
return 0;
}
始终建议使用Booth算法将X + 1位用于X位乘法。额外的一位用于处理符号值。这是你的方法的一个问题。没有这个，像101（十进制：5）这样的数字就像负1一样。
Booth的算法用于有符号数的乘法，其中一个应该被签名，或者两者都被签名。我们不能将Booth的算法应用于两个无符号数。
Booth的算法用于有符号数的乘法，其中一个应该被签名，或者两者都被签名。我们也可以将Booth的算法应用于两个无符号数，但我们必须检查数字是否在给定范围内。例如，如果我们采用像2 * 3这样的4位数字是可能的。如果我们做9 * 4或9 * -4或-9 * -4是不可能的，因为9或-9不在4位数的范围内，所以booth算法乘法是不可能的。