c++ - 二进制乘法器的 C++ 实现

Question

我正在尝试 32 位二进制乘法器的 C++ 实现。我只知道这样做的一种方法是

    1011   (this is 11 in decimal)      
x   1110   (this is 14 in decimal)      
   ======        
    0000   (this is 1011 x 0)       
   1011    (this is 1011 x 1, shifted one position to the left)      
  1011     (this is 1011 x 1, shifted two positions to the left)     
 1011      (this is 1011 x 1, shifted three positions to the left)   
=========    
10011010   (this is 154 in decimal).

是否有另一种方法可以做到这一点，因为我必须对更长的二进制数进行操作，所以编码起来并不那么麻烦？

score 0 · Accepted Answer

好吧，任意精度和大数字的（正确和高效）实现很麻烦，并且对于在生产代码中使用，通常建议使用经过测试的框架（例如boost、gmp等）。

但是，如果您自己实现它，我不会将数字存储为位序列，而是存储为机器字序列，unsigned int以便充分利用您的硬件 ALU 功能。因此，每个单词已经代表了许多位，并且您的 ALU 知道如何将它们相乘。

请注意，当您将数字与n数字相乘时（底数无关紧要），您将得到一个2n数字，例如 99 * 99 = 9801（底数 10）、0xFF * 0xFF = 0xFE01（底数 16）。所以，如果std::uintmax_t是std::uint64_t您的系统上，您可以将您的号码存储为std::uint32_t. 将两位数相乘时，将它们转换为std::uint64_t并相乘。高 32 位将是进行下一个高位乘法运算的部分。（实际上，您也可以std::uintmax_t直接将变量相乘，但获取结果的高位部分通常有点棘手，并且需要内联汇编才能访问相应的EDX\RDX寄存器。）

有了这些知识，学校乘法方法的实现应该很简单：只需遍历数字a[i]的所有数字a并将每个数字与数字相乘b（不要忘记传播进位）。将结果按i位数向上移动并将所有内容添加到最终结果中。

请注意，该算法在原始乘法的数量方面具有二次复杂度。如果您有（非常非常）大的数字，您还可以切换到更复杂的方法，例如 Karatsuba 甚至 FFT 和 Schönhage-Strassen。但在这种情况下，我真的建议使用库。

score 0 · Accepted Answer

由于整数类型的隐式乘法是二进制乘法，您可以直接利用它来将数字视为基数 2 ⁸、 2 ¹⁶或更高，而不是基数 2 ¹。

如果您假设 8 位数字（乘以unsigned chars），则下面的 24 位示例不如您问题中发布的 4 位乘法复杂。

           a1 a2 a3   (this is a 3 byte value)      
       x   b1 b2 b3   (this is another 3 byte value)      
           ======        
       xx xx xx xx    (this is a x b3)       
    xx xx xx xx       (this is a x b2, shifted 8 bits to the left)      
 xx xx xx xx          (this is a x b1, shifted 16 bits to the left)
 =================    
 xx xx xx xx xx xx    (this is the result).

您可以将上面的“字节”替换为short或long，并相应调整班次。

只需确保将被乘数转换为足够大的类型以在乘法之前容纳进位即可。

score 0 · Accepted Answer

是的，您可以通过使用循环来完成此操作。假设类型long是32位，那么long*long的结果就是64位。

例如，如果你有一只long A蚂蚁 a long B，并且你想计算a*b

首先，您将结果定义为long long result = 0;。然后检查B的每一位，如果位为1，则添加A << X到结果中。其中X是位的索引。一个循环就可以做到这一点。

long long AA = A;// convernt A to AA to avoid overflow
for( int index=0;i<32;++index )
{
    if( B & 0x1 )
        result += AA;
    AA <<= 1;
    B >>= 1;
}

我希望我没有犯错，这个想法可以帮助你。

score 0 · Accepted Answer

您可以使用 Booth 的乘法算法。维基百科上有更多信息：http ://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm

c++ - 二进制乘法器的 C++ 实现

4 回答 4

Related

Reference