Wie zählt diese Methode die Anzahl der 1en in Binärdarstellung?

Question

Mögliche Duplizieren:
n & (n-1) what does this expression do?

Betrachten Sie den folgenden Algorithmus:

int count(int num) 
{ 
    int ones = 0; 
    while(num) 
    { 
    ++ones; 
    num &= num - 1; 
    } 

    return ones; 
} 

Was ist die Bedeutung von num & (num-1)? Wie funktioniert es?

Answer 1

num &= num - 1; 

löscht das niedrigstwertige Bit in num.

Dieser Algorithmus zählt die gesetzten Bits, indem er sie löscht und einen Zähler inkrementiert, bis alle weg sind.

Um zu verstehen, warum es das niedrigstwertige Bit löscht, müssen Sie darüber nachdenken, was die Bits dekrementieren und natürlich verstehen, was die & Operation tut.

Subtrahieren im Binärformat funktioniert genauso wie der Prozess, in dem wir alle dezimal als Kinder unterrichtet wurden. Sie arbeiten von rechts (am wenigsten signifikant) nach links, subtrahieren einfach einzelne Ziffern, wenn möglich, und "leihen" bei Bedarf von der nächsten Ziffer.

Beim Subtrahieren von 1 von einer Binärzahl, die in einer Menge von Nullen endet, werden durch dieses "Ausleihen" und Subtrahieren alle Nullen in niedrigere Positionen als die ganz rechten 1 zu 1 und die ganz rechte 1 in eine Null umgewandelt).

den & Operator Dann Anwendung lässt alle die kleineren Ziffern Null, weil sie Null in num und setzt das am wenigsten signifikante Bit num auf Null sind, weil es null in num-1 ist.

Beide Operationen lassen die höherwertigen Stellen unverändert.

Hier ist eine gute Liste von bit twiddling hacks einschließlich dieser, die aufgrund Brian Kernighan ist.

Answer 2

Hier ist eine detailliertere (aber nicht sehr gut geschrieben!) Antwort.

Es gibt zwei Fälle: Entweder wird das niedrigstwertige Bit gesetzt, dann "num-1" wird es aufgehoben. Oder es ist nicht gesetzt, dann verwandelt num-1 alle nachgestellten Nullen in 1 und die niedrigstwertige 1 in eine 0, der Rest der Bits wird nicht geändert. Wenn Sie "und" sind, sind alle unveränderten Bits gleich, die niedrigstwertige 1, die mit einer 0 verknüpft ist, wird zu einer 0 und die anderen verbleibenden Bits sind Nullen. Dies wird hier dargestellt:

num    =  1000110111[1]0000 
num - 1   =  1000110111[0]1111 
num & (num - 1) =  1000110111[0]0000 

Ich mag darauf hinweisen, dass es oft ein Montagevorgang die Anzahl von Einsen in einem einzigen Zyklus zu zählen. Die Operation wird "popcount" genannt und kann beispielsweise in GCC mit "__builtin_popcount" aufgerufen werden, siehe this link für Details.

Answer 3

Der Algorithmus funktioniert wie Pumpe und bewegt Bits effektiv nach rechts in der Variablen "num".Die Linie

num &= num - 1; 

ist, wo die Arbeit getan ist, gibt es einen Auftrag und boolean AND-Operation zur gleichen Zeit los. Es geht nur um Bit-Arithmetik.

Pom