正整數乘法用C

Question

所以我想實現這個算法下乘以32位無符號整數，以便更好地理解它：

​​

什麼，我沒有得到的是如何實現步驟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位整數來表示的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位。