Multiplikation Algorithmus Bitshifts

Question

Während zum Multiplizieren 2 große Zahlen für einen effizienten Algorithmus sucht, kam über die unter c-Methode in einem Forum: -

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

Die obige algo erfordert keinen Multiplikationsbefehl, sondern nutzt bitshift und nur Additionsoperation (wodurch es schneller wird).

Überprüft, dass die Methode richtig funktioniert, aber ich verstehe nicht ganz, wie es funktioniert. Eine Erklärung wäre hilfreich.

Answer 1

Es iteriert über alle 1 Bits in a, b hinzugefügt verschoben die entsprechende Menge.

Zuerst beachten Sie, dass, wenn a11001 ist, kann es als 10000 + 1000 + 1 behandelt werden, so a * b(10000*b) + (1000*b) + (1*b) ist. Dann notieren Sie, dass 10000*b nur b << 4 ist.

Jedes Mal, wenn die Schleife durchlaufen wird, wird b um 1 nach links verschoben, um den aktuellen Verschiebungsbetrag anzuzeigen, und a wird um 1 nach rechts verschoben, so dass das niederwertige Bit getestet werden kann. In diesem Beispiel fügt es schließlich b + (b << 3) + (b << 4) hinzu, was nur (1*b) + (1000*b) + (10000*b) ist.

Answer 2

Wow, es ist schön Algorithmus ist, und ähnlich dem, was wir von Hand tun:

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

wir also binäre tun:

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

ein rechts verschoben sein erstes Bit zuzugreifen, indem : if (a & 1)
b für jede Position nach links verschoben Führen Sie eine Stellenverschiebung wie oben

Dies ist genau das, was wir tun, wenn von Hand

Multiplikation

Ich schlage vor, uint64_t von

#include<stdint.h> 

für gute und klare Art der Programmierung zu verwenden:

#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); 
}