使用位移的乘法算法

Question

在寻找一种有效的算法来乘以两个大数时，我在论坛上发现了以下C语言方法：

...
    typedef unsigned long long ULL;

    ULL multiply (ULL a,ULL b)
    {
      ULL result = 0;
      while(a > 0)
      {
        if(a & 1)
        {
          result += b;
        }
        a >>= 1;
        b <<= 1;    
      }

      return result;
    }
...

上述算法无需乘法操作，而只使用位移和加法操作（因此更快）。

我检查过该方法的正确性，但我并不完全理解它是如何工作的。有一个解释会很有帮助。

- Siddhartha Ghosh

---

请注意，某些CPU的移位操作可能非常缓慢 - 68008曾经是一个例子。因此，您的结果可能会有所不同。 - tofro

因此使其更快 - M.M

算法与你在学校学习的长乘法是一样的，只不过第一个操作数是以二进制形式表示的。它有时被称为“俄罗斯乘法”。 - M.M

Answer 1

它遍历了a中的所有1位，将b向左移适当的量后加上它。

首先，注意如果a是11001，它可以被视为10000+1000+1，因此a * b是(10000*b) + (1000*b) + (1*b)。 然后，请注意10000*b就是b << 4。

每次循环时，b向左移1以反映当前移位量，并且a向右移1，以便可以测试低位。在这个例子中，它最终添加了b+(b << 3)+(b << 4)，这只是(1*b) + (1000*b) + (10000*b)。

- Tom Karzes

Answer 2

哇，这是一个不错的算法，类似于我们手工操作的方式：

123*  
456=  
6*(123)+  
50*(123)+ //this means one digit shift, nice and easy  
400*(123) //this means two digits shift, nice and easy  

所以让我们来谈谈二进制：

101*  //b  
110=  //a  
0*(101)+    
10*(101)+ //=1*(1010) //one digit shift  
100*(101) //=1*(10100) //two digits shift  

a向右移位以访问其第一位，方法如下：if(a&1)
b向左移位以进行每个位置的数字移位，与上述操作相同

这正是我们手动乘法所做的

我建议使用来自uint64_t

#include<stdint.h>

为了良好和清晰的编程风格：

#include<stdint.h> 
uint64_t multiply(uint64_t a, uint64_t b)
{
    uint64_t result = 0;
    while (a > 0)
    {
        if (a & 1)
        {
            result += b;
        }
        a >>= 1;
        b <<= 1;
    }
    return result;
}

int main() {
    uint64_t a = 123;
    uint64_t b = 456;
    uint64_t c = multiply(a, b);
}

- user6169399