c - C 中的无符号整型乘法

Question

所以我尝试用 C 语言实现这个算法来乘以 32 位无符号整数，以便更好地理解它:

Step 1:  Test multiplier-0

Step 2:  if 1, add multiplicand to left half of product
        and place the result in the left half of 
        the product register


Step 3:  shift multiplier right 1 bit

Step 4:  shift product register right 1 bit

我没有得到的是如何实现步骤2。它说将被乘数添加到乘积的左半部分并存储在乘积寄存器的左半部分中。我对如何仅添加到产品的左半部分感到困惑。我该怎么办？

编辑:这是我带来的东西，但它没有给我正确的答案，我不确定出了什么问题。请帮忙!

long unsigned UnsignedMult(unsigned multiplicand, unsigned multiplier){

    unsigned int temp32a, temp32b;
    unsigned long temp64;
    unsigned long product;

    int i;

    product = multiplier;
    temp32b = multiplicand;


    for(i=0; i < 32; i++){
        if((product & 1)==1){ //add
           temp64 = product;
           temp64 = temp64 >> 32;
           temp32a = temp64;
           product = BinaryAdd(temp32a, temp32b); 
        }

        product = product >>= 1;

    }
    return product;
}

int BinaryAdd(int in1, int in2){

    int sum, carry;
    sum = in1 ^ in2; // x XOR y
    carry = in1 & in2; // x AND y carry in
    int i;    
    for (i = 0; i < 32; i++) {
        carry = carry << 1; 
        in1 = sum; 
        in2 = carry; 
        sum = in1 ^ in2; //calculate sum
        carry = in1 & in2; //find carry out
    }
    return sum;
}

Answer 1

您的乘积寄存器的长度需要为 64 位，才能允许两个 32 位整数相乘。希望你有uint64_t在您的编译器中可用来表示这一点(stdint.h)。

要进行加法，您可以将被乘数放入 64 位整数中，将其左移 32 位，然后将其添加到 64 位乘积寄存器中。

类似于:

uint64_t tmpMulti;
uint64_t productRegister = 0;
uint32_t multiplicand = 123;

tmpMulti = multiplicand;
tmpMulti <<= 32;
productRegister += tmpMulti;

(对于任何语法错误，我深表歉意，我已经很长时间没有编写 C 代码了)

出于兴趣，我尝试自己实现它。这似乎有效:

#include <stdio.h>
#include <stdint.h>

void main(int argc, char* argv[])
{
    uint32_t multiplier = 17;
    uint32_t multiplicand = 12;

    uint64_t productRegister = multiplier;

    for (int n = 0; n < 32; n++) {
        if (productRegister & 1 == 1) {
            productRegister += ((uint64_t)multiplicand) << 32;
        }
        productRegister >>= 1;
    }

    printf("Result: %d\n", productRegister);
}

下面的代码没有使用<stdint.h> ，并使用两个 32 位 int 来表示 64 位乘积寄存器。它不会尝试处理溢出，并假设答案适合 32 位。

#include <stdio.h>

void main(int argc, char* argv[])
{
    unsigned int multiplier = 17;
    unsigned int multiplicand = 12;

    unsigned int productRegisterLower = multiplier;
    unsigned int productRegisterUpper = 0;

    for (int n = 0; n < 32; n++) {
        if (productRegisterLower & 1 == 1) {
            productRegisterUpper += multiplicand;
        }
        productRegisterLower >>= 1;
        productRegisterLower |= productRegisterUpper << 31;
        productRegisterUpper >>= 1;
    }

    printf("Result: %d\n", productRegisterLower);
}

为了处理乘积寄存器的右移，它将上半部分的最低有效位移动到下半部分的最高有效位。为此，它:

• 将下半部分向右移动 1 位。
• 获取上半部分的副本并将其左移 31 位，以便最低有效位现在位于左侧，其余值为零。
• 将其与下半部分进行或运算，以复制移位后的位。
• 将上半部分向右移动 1 位。