C 语言 BOOTHS 算法

2024年8月28日 | 阅读 7 分钟

Booth算法是一种用于乘两个带符号的二进制值的乘法算法。该算法在计算机数学中经常使用，由Andrew Donald Booth于1951年开发。

该技术通过减少乘法所需的加法运算次数来提高处理效率。它通过执行一系列移位和加法来实现这一点，这些操作可以通过简单的硬件电路轻松完成。

在本文中，我们将介绍Booth方法，并向您展示如何使用C编程语言来实现它。

Booth算法

这些观察结果构成了Booth算法的基础

可以使用左移操作来乘以二。
可以进行右移操作，如除以二。
如果一个二进制数由一串连续的1然后是0组成，我们可以用一个单一的1然后相同数量的0来替换这个字符串，得到的数字将等于原始数字。

这些发现使得可以使用以下步骤来定义Booth算法：

将初始值设置为0。
考虑将要相乘的两个二进制数表示为二的补码。
为了使乘数的长度等于被乘数的长度，请在乘数右侧添加一个零位。
从乘数最右边的位开始，一次检查两位。
如果前两位是0和1，则从乘积中减去被乘数。
如果两位都是1和0，则通过被乘数将乘积加倍。
将乘数右移一位。
重复步骤4-7，直到检查完所有乘数位。

在C中的应用

既然我们已经看到了一个例子，现在让我们在C编程语言中实现Booth算法。我们将创建一个函数，该函数接收两个带符号的二进制值作为输入，并输出两个值的和。

该函数将接受两个参数：指向表示被乘数和乘数的数组的指针。由于每个数字有n位，每个数组的长度将是n位。假定数组已经是二的补码形式。

让我们来看一下这个函数是如何实现的。

#include <stdio.h>
#include <stdlib.h>

int* booth_multiplication(int* m, int* q, int n) {
    int* product = (int*) malloc(2 * n * sizeof(int)); 
    for (int i = 0; i < 2 * n; i++) {
        product[i] = 0; 
    }

    int* a = (int*) malloc(n * sizeof(int)); 
    for (int i = 0; i < n; i++) {
        a[i] = 0; 
    }

    int q0 = 0; 
    for (int i = 0; i < n; i++) {
        if (q0 == 0 && q[n-1] == 1) { 
            for (int j = 0; j < n; j++) {
                if (a[j] == 0) { 
                    a[j] = m[j];
                }
                else { 
                    a[j] = ~m[j] + 1;
                }
            }
        }
        else if (q0 == 1 && q[n-1] == 0) { // Case 2: q0 = 1, q[n-1] = 0
            for (int j = 0; j < n; j++) {
                if (a[j] == 0) { 
                    a[j] = ~m[j] + 1;
                }
                else { 
                    a[j] = m[j];
                }
            }
        }
        q0 = q[n-1];
        for (int j = n-1; j > 0; j--) {
            q[j] = q[j-1];
            a[j] = a[j-1];
        }
        q[0] = a[0];
    }

    for (int i = 0; i < n; i++) {
        product[i] = a[i];
    }

    free(a); 
    return product;
}

为了理解它的工作原理，让我们逐步分解这个实现。

我们的第一步是为乘积和数组分配内存。与存储方法中使用的寄存器值的数组不同，乘积数组将携带乘法的最终结果。两个数组的初始值均为0。

int* product = (int*) malloc(2 * n * sizeof(int));
for (int i = 0; i < 2 * n; i++) {
    product[i] = 0;
}

int* a = (int*) malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
    a[i] = 0;
}

接下来，我们通过遍历乘数的每一位来运行Booth算法。我们使用两个变量q0和q[n-1]来跟踪乘数的最新位和前一位。

int q0 = 0;
for (int i = 0; i < n; i++) {
    if (q0 == 0 && q[n-1] == 1) {
        // Case 1: q0 = 0, q[n-1] = 1
        // Add multiplicand to a if a[j] = 0
        // Subtract multiplicand from a if a[j] = 1
    }
    else if (q0 == 1 && q[n-1] == 0) {
        // Case 2: q0 = 1, q[n-1] = 0
        // Subtract multiplicand from a if a[j] = 0
        // Add multiplicand to a if a[j] = 1
    }

    // Shift a and q to the right
    q0 = q[n-1];
    for (int j = n-1; j > 0; j--) {
        q[j] = q[j-1];
        a[j] = a[j-1];
    }
    q[0] = a[0];
}

在每次迭代中，将当前乘数位与前一位进行比较，其中有两种情况：q0 = 0, q[n-1] = 1，或 q0 = 1, q[n-1] = 0。然后，根据a的当前位的值，通过加或减被乘数来对a寄存器执行必要的操作。

将a寄存器的当前位复制到q的最低有效位，同时将a和q都向右移动一位。然后，我们对每个乘数位再次执行此过程。

在释放a寄存器使用的内存并将其内容复制到乘积数组后，我们返回乘积数组。

for (int i= 0; i < n; i++) {
product[i] = a[i];
}

free(a);
return product;

示例

这是使用Booth算法来乘两个带符号值的C程序的源代码。C程序已成功编译并执行。下面还显示了程序的输出。

#include <stdio.h>
#include <math.h>

int a = 0,b = 0, c = 0, a1 = 0, b1 = 0, com[5] = { 1, 0, 0, 0, 0};
int anum[5] = {0}, anumcp[5] = {0}, bnum[5] = {0};
int acomp[5] = {0}, bcomp[5] = {0}, pro[5] = {0}, res[5] = {0};

void binary(){
     a1 = fabs(a);
     b1 = fabs(b);
     int r, r2, i, temp;
     for (i = 0; i < 5; i++){
           r = a1 % 2;
           a1 = a1 / 2;
           r2 = b1 % 2;
           b1 = b1 / 2;
           anum[i] = r;
           anumcp[i] = r;
           bnum[i] = r2;
           if(r2 == 0){
                bcomp[i] = 1;
           }
           if(r == 0){
                acomp[i] =1;
           }
     }

   c = 0;
   for ( i = 0; i < 5; i++){
           res[i] = com[i]+ bcomp[i] + c;
           if(res[i] >= 2){
                c = 1;
           }
           else
                c = 0;
           res[i] = res[i] % 2;
     }
   for (i = 4; i >= 0; i--){
     bcomp[i] = res[i];
   }

   if (a < 0){
      c = 0;
     for (i = 4; i >= 0; i--){
           res[i] = 0;
     }
     for ( i = 0; i < 5; i++){
           res[i] = com[i] + acomp[i] + c;
           if (res[i] >= 2){
                c = 1;
           }
           else
                c = 0;
           res[i] = res[i]%2;
     }
     for (i = 4; i >= 0; i--){
           anum[i] = res[i];
           anumcp[i] = res[i];
     }

   }
   if(b < 0){
     for (i = 0; i < 5; i++){
           temp = bnum[i];
           bnum[i] = bcomp[i];
           bcomp[i] = temp;
     }
   }
}
void add(int num[]){
    int i;
    c = 0;
    for ( i = 0; i < 5; i++){
           res[i] = pro[i] + num[i] + c;
           if (res[i] >= 2){
                c = 1;
           }
           else{
                c = 0;
           } 
           res[i] = res[i]%2;
     }
     for (i = 4; i >= 0; i--){
         pro[i] = res[i];
         printf("%d",pro[i]);
     }
   printf(":");
   for (i = 4; i >= 0; i--){
           printf("%d", anumcp[i]);
     }
}
void arshift(){
    int temp = pro[4], temp2 = pro[0], i;
    for (i = 1; i < 5  ; i++){
       pro[i-1] = pro[i];
    }
    pro[4] = temp;
    for (i = 1; i < 5  ; i++){
        anumcp[i-1] = anumcp[i];
    }
    anumcp[4] = temp2;
    printf("\nAR-SHIFT: ");
    for (i = 4; i >= 0; i--){
        printf("%d",pro[i]);
    }
    printf(":");
    for(i = 4; i >= 0; i--){
        printf("%d", anumcp[i]);
    }
}

void main(){
   int i, q = 0;
   printf("\t\tBOOTH'S MULTIPLICATION ALGORITHM");
   printf("\nEnter two numbers to multiply: ");
   printf("\nBoth must be less than 16");
   //simulating for two numbers each below 16
   do{
        printf("\nEnter A: ");
        scanf("%d",&a);
        printf("Enter B: ");
        scanf("%d", &b);
     }while(a >=16 || b >=16);

    printf("\nExpected product = %d", a * b);
    binary();
    printf("\n\nBinary Equivalents are: ");
    printf("\nA = ");
    for (i = 4; i >= 0; i--){
        printf("%d", anum[i]);
    }
    printf("\nB = ");
    for (i = 4; i >= 0; i--){
        printf("%d", bnum[i]);
    }
    printf("\nB'+ 1 = ");
    for (i = 4; i >= 0; i--){
        printf("%d", bcomp[i]);
    }
    printf("\n\n");
    for (i = 0;i < 5; i++){
           if (anum[i] == q){
               printf("\n-->");
               arshift();
               q = anum[i];
           }
           else if(anum[i] == 1 && q == 0){
              printf("\n-->");
              printf("\nSUB B: ");
              add(bcomp);
              arshift();
              q = anum[i];
           }
           else{
              printf("\n-->");
              printf("\nADD B: ");
              add(bnum);
              arshift();
              q = anum[i];
           }
     }

     printf("\nProduct is = ");
     for (i = 4; i >= 0; i--){
           printf("%d", pro[i]);
     }
     for (i = 4; i >= 0; i--){
           printf("%d", anumcp[i]);
     }
}

输出

BOOTH'S MULTIPLICATION ALGORITHM
Enter two numbers to multiply: 
Both must be less than 16
Enter A: 1
Enter B: 11
Expected product = 11

Binary Equivalents are: 
A = 00001
B = 01011
B'+ 1 = 10101

-->
SUB B: 10101:00001
AR-SHIFT: 11010:10000
-->
ADD B: 00101:10000
AR-SHIFT: 00010:11000
-->
AR-SHIFT: 00001:01100
-->
AR-SHIFT: 00000:10110
-->
AR-SHIFT: 00000:01011
Product is = 0000001011

结论

总之，Booth算法是用于表示为2的补码的带符号整数的二进制乘法的有用技术。与传统的乘法技术相比，该过程仅需要根据乘数位值进行移位和加或减被乘数。我们提供了一个基于位运算的Booth方法在C语言中的实现，并附带一个实际应用。

下一个主题C语言中的字符填充程序

← 上一个下一个 →

C 语言 BOOTHS 算法

Booth算法

在C中的应用

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言 BOOTHS 算法

Booth算法

在C中的应用

结论

相关帖子

C 语言序列点

C 语言 Kruskal 算法

反转数字

C 语言中相加 2 个字符串

斐波那契数列

C 语言 abs() 函数

C 语言相加两个二进制数的程序

C 语言优先级调度程序

C 语言中的大 O 记法

C 语言局部标签

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器