Anzahl der Bits zählen: Wie funktioniert diese Linie? n = n &(n-1);

Ich brauche eine Erklärung, wie diese spezielle Linie funktioniert.
Ich weiß, dass diese Funktion die Anzahl der 1 Bits zählt, aber wie genau diese Zeile das rechte 1 Bit löscht?Anzahl der Bits zählen: Wie funktioniert diese Linie? n = n &(n-1);

int f(int n) { 
    int c; 
    for (c = 0; n != 0; ++c) 
     n = n & (n - 1); 
    return c; 
}

Können einige es mir kurz erklären oder einen "Beweis" geben?

Quelle

2013-03-12 BBLN

Denken Sie über lange Subtraktion und „borgen“. –

Es löscht das Bit ganz rechts, weil das rechte Bit von 'n - 1 'niemals das gleiche wie' n 'ist. – 0x499602D2

[Kernighans Bitzähltrick!] (Http: //cs.stanford.edu/~ seander/bithacks.html # CountBitsSetKernighan) – Ternary

Jede vorzeichenlose Ganzzahl '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) wird in diesem Format enden: Null, gefolgt von (k-1) 1 ist: 011 ... 1

n & (n-1) wird daher in 'k' Nullen enden: 100 ... 0 & 011 ... 1 = 000 ... 0

Daher wird & (n - 1) die ganz rechte "1" eliminieren. Bei jeder Iteration wird die rechte 1-Stelle entfernt und Sie können die Anzahl der Einsen zählen.

Quelle

2013-03-12 19:28:37 user1952500

Gilt dies für negative Werte, wenn die Plattform eine signierte Magnitudenrepräsentation anstatt eines Zweierkomplements verwendet? –

Ich habe auf Bit Manipulation aufgeräumt und stieß auf diese. 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 für n & (n-1) gleich Null?

Wir sollten sicherstellen, dass wir wissen, dass dies der einzige Weg ist, die Schleife zu durchbrechen (n != 0). Sagen wir n=8. Die Bit-Darstellung 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 00001000 und 00000111 keine ähnlichen Bits gesetzt haben, wäre das Ergebnis 00000000 (oder Null). Sie haben vielleicht bemerkt, dass die Zahl 8 nicht zufällig ausgewählt wurde. Es war ein Beispiel, bei 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? Wenn zum Beispiel n=6 ist die Bit-Darstellung 00000110 und n-1=5 oder 00000101 .Die & auf diese zwei Argumente angewendet wird und sie nur ein einziges Bit gemeinsam haben, die 4. Nun ist, n=4, die nicht Null ist, so ist erhöhen wir c und versuchen der gleiche 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 bis n aus einer Potenz von 2 gleich

Was ist c?

Es wird Inkrementieren nur durch eine jede Schleife und beginnt bei 0. c die Anzahl der Bits ist, bevor die Zahl abgeschnitten gleich einer Potenz von 2

Quelle

2016-04-01 13:30:41

Anzahl der Bits zählen: Wie funktioniert diese Linie? n = n &(n-1);

Antwort

Verwandte Themen