c - 使用 Bitshifts 的乘法算法

在寻找乘以 2 个大数的有效算法时，在论坛中遇到了以下 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;
    }
...

上述算法不需要乘法指令，而是仅使用位移和加法运算(从而使其更快)。

检查该方法是否正常工作，但是，我不完全了解它是如何工作的。解释会有所帮助。

最佳答案

它迭代 a 中的所有 1 位，添加 b 移动适当的数量。

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

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

关于c - 使用 Bitshifts 的乘法算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36880445/