c - 使用 Bitshifts 的乘法算法

Question

在寻找将 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;
    }
...

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

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

Answer 1

它正在遍历 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) .