Jede vorzeichenlose ganze Zahl 'n' hat die folgenden letzten k Ziffern: Eine gefolgt von (k-1) Nullen: 100 ... 0 Beachten Sie, dass k 1 sein kann, in diesem Fall gibt es keine Nullen.
(n - 1) endet in folgendem Format: Null gefolgt von (k-1) 1: 011 ... 1
n & amp; (n-1) wird daher in 'k' Nullen enden: 100 ... 0 & amp; 011 ... 1 = 000 ... 0
Daher n & amp; (n - 1) wird die rechte "1" eliminieren. Bei jeder Iteration wird die rechte 1-Stelle entfernt und Sie können die Anzahl der 1 zählen.
Ich habe die Bit-Manipulation aufgefrischt und bin auf dieses Problem gestoßen. Es ist vielleicht nicht mehr nützlich für das Original-Poster (3 Jahre später), aber ich werde trotzdem antworten, um die Qualität für andere Zuschauer zu verbessern.
Was bedeutet es, dass n & (n-1) gleich null ist?
Wir sollten sicherstellen, dass wir das wissen, da dies der einzige Weg ist, die Schleife zu unterbrechen ( n != 0 ).
Sagen wir n=8 . Die Bit-Repräsentation dafür wäre 00001000 . Die Bitdarstellung für n-1 (oder 7) wäre 00000111 . Der Operator & gibt die in beiden Argumenten gesetzten Bits zurück. Da für 00001000 und 00000111 keine ähnlichen Bits gesetzt sind, wäre das Ergebnis 00000000 (oder Null).
Sie haben vielleicht bemerkt, dass die Zahl 8 nicht zufällig gewählt wurde. Es war ein Beispiel, in dem n die Potenz von 2 ist. Alle Potenzen von 2 (2,4,8,16 usw.) haben das gleiche Ergebnis.
Was passiert, wenn Sie etwas übergeben, das kein Exponent von 2 ist? Zum Beispiel, wenn n=6 , ist die Bitdarstellung 00000110 und n-1=5 oder 00000101 .Das & wird auf diese 2 Argumente angewendet und sie haben nur ein einzelnes Bit gemeinsam, das 4 ist. Jetzt, n=4 ist nicht Null, also erhöhen wir c und versuchen denselben Prozess mit n=4 . Wie wir oben gesehen haben, ist 4 ein Exponent von 2, so dass es im nächsten Vergleich die Schleife durchbricht. Es schneidet das Bit ganz rechts ab, bis n gleich einer Potenz von 2 ist.
Was ist c ?
Es wird nur für jede Schleife um eins erhöht und beginnt bei 0. c ist die Anzahl der abgeschnittenen Bits, bevor die Zahl einer Potenz von 2 entspricht.