乘用算法Bitshifts

在寻找有效的算法用于乘以2个大的数字，在一个论坛上遇到了C以下方法： -乘用算法Bitshifts

... 
    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; 
    } 
...

上述算法中不需要乘法指令，而使用位位移和只有加法操作（因此使它更快）。

检查该方法工作正常，但是，我没有完全知道它是如何工作的。解释会有帮助。

来源

2016-04-27 Siddhartha Ghosh

请注意一些CPU可以有非常缓慢的移位操作 - 68008曾经是一个例子。所以你的里程可能有所不同 – tofro

“因此使它更快” - 在一个不是 –

该算法是你在学校长时间乘法学习的相同的东西;除了第一个操作数是以2为底的。它有时被称为“俄罗斯乘法” –

它遍历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)。

来源

2016-04-27 04:52:05

哇，这是很好的算法，以及类似于我们做手工：

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

一个右移通过访问其第一位：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); 
}

来源

2016-04-27 05:52:32

乘用算法Bitshifts

回答

相关问题