Wie funktioniert dieser Code, um die Anzahl der 1-Bits zu zählen?
Lesezeit: 6 Minuten
herohuyongtao
Ich habe den folgenden Code gefunden, um die Anzahl zu zählen 1-bits in binärer Darstellung für gegebene ganze Zahl. Kann jemand erklären, wie es funktioniert? Und wie werden die Bitmasken für eine solche Aufgabe ausgewählt? Danke.
Wenn wir diese beiden addieren, erhalten wir die Bitzahl jedes Zwei-Bit-Paares. Dieses Ergebnis ist höchstens 0x10da die Maske für jede Addition nur ein Bit gesetzt hat.
Nun verwenden wir die 0x33 Maske, denken Sie daran, dass alle aufeinanderfolgenden 2 Bits das Ergebnis der ersten Operation enthalten. Mit dieser Maske maskieren wir aufeinanderfolgende 4 Bits und fügen sie hinzu. Dieses Ergebnis ist höchstens 0x100. So geht es mit den anderen Masken weiter, bis wir das Ergebnis haben x.
Probieren Sie es auf Papier aus, es wird nach ein paar Schritten ziemlich klar sein.
Ich suchte nach einer wissenschaftlicheren Lösung. Ich meine, es ist nichts falsch an Ihrer Antwort, aber ich weiß immer noch nicht, wie die Bitmasken ausgewählt wurden.
– Silviu Burcea
15. Januar 2014 um 8:21 Uhr
Die Masken selektieren immer längere aufeinanderfolgende Bits (da der Algorithmus mit 32-Bit-Ints arbeitet, benötigen Sie mehr Masken als in meinem Beispiel). Kannst du mir sagen, was genau du nicht verstehst? Denn für mich ist es ziemlich offensichtlich, nachdem ich es auf dem Papier gemacht habe.
– Frauref
15. Januar 2014 um 8:33 Uhr
@SilviuBurcea das ist die einzig offensichtliche Wahl für die Masken, wie würdest du es sonst machen?
– Harald
15. Januar 2014 um 8:34 Uhr
Lukasz Kidziński
Es ist ein Teile-und-Herrsche-Ansatz. Beachten Sie, dass die erste Zeile Ihnen die Summe der nachfolgenden Paare, die nächste die Summe der nachfolgenden Quadrupel, … und schließlich die Anzahl der Bits gibt.
Beispiel (16 Bit, also betrachten Sie Ihren Code ohne die letzte Zeile)
1011001111000110
In der Faustlinie nehmen wir & mit geraden Bits und ungeraden Bits um eins verschoben. Dann fügen wir hinzu.
2nd: 0011 0010 0010 0010 // 3 set in the first four, 2 in other quadrupels
3rd: 0000 0101 0000 0100 // 5 bits set in the first eight, 4 in the rest
4th: 0000 0000 0000 1001 // 9 bits in total
Um dies einfacher zu erklären, lassen Sie mich annehmen, dass eine Ganzzahl 4 Bit lang ist und jedes Bit als 1,2,3,4 dargestellt wird. Um die Nummer zu bekommen 1-bitskannst du zuerst die Summe von 1 und 2 und die Summe von 3 und 4 bilden und diese Summen dann addieren.
x & (0x5) wird 1 und 3 beseitigen, und x & (0xa) eliminiert 2 und 4. x & (0x5) + (x & (0xa) >> 1) verwendet 1 2 Bits, um die Summe von 1 und 2 zu speichern, und verwendet 3 4 Bits, um die Summe von 3 und 4 zu speichern. x & (0x5) + (x & (0xa) >> 1) ist gleich wie x & (0x5) + (x >> 1) & (0x5).
Jetzt haben wir die Summen von 1 2 und 3 4 alle in x gespeichert, wir können das Ergebnis erhalten, nachdem wir sie addiert haben. Das gleiche wie oben, x & (0x3) erhält die Summe von 3 4 und x & (0x12) erhält die Summe 1 2. x & (0x3) + (x & (0x12)) >> 2 wird das Endergebnis erhalten. x & (0x3) + (x & (0x12)) >> 2 ist gleich wie x & (0x3) + (x >> 2) & (0x3).
So können Sie sehen, was im Inneren passiert. In Ihrem Fall können Sie in der ersten Zeile die Summe von 1 2 und 3 4 und 5 6 erhalten und weitermachen. Und in der zweiten Zeile erhalten Sie die Summe aus 1 2 3 4 und 5 6 7 8 und machen weiter. Wenn Sie dies also 5 Mal tun, erhalten Sie die Anzahl aller 32 Bits.
Die erste Zeile behandelt die Ganzzahl als ein Array von 16 2-Bit-Ganzzahlen, das Ergebnis des Ausdrucks ist 0, wenn 0 Bits im 2-Bit-Paar gesetzt wurden, 1, wenn 1 Bit im 2-Bit-Paar gesetzt wurde (01 bin oder 10 bin) und 2, wenn beide Bits des 2-Bit-Paares gesetzt waren. Dies liegt daran, dass wir das niedrigere von jeweils zwei Bits von betrachten xund das niedrigere von jeweils zwei Bits von x um eins nach rechts verschoben; addieren sie zusammen. Wir wissen, dass außerhalb der 2-Bit-Paare keine Überträge auftreten, da unsere Summanden auf 0 oder 1 begrenzt sind. Das Ergebnis wird dann wieder in gespeichert x.
Die nächste Zeile macht das Gleiche, behandelt diesmal alle 2 Bits als separate Ganzzahl und speichert ihre Summe in allen 4 Bits, die die beiden Summanden früher belegten. Nach dieser Operation wird die Ganzzahl im Wesentlichen zu einem Array von 8 4-Bit-Ganzzahlen. Vor der Operation ist jeder Summand entweder 0, 1 oder 2 (dezimal), da er den Zählwerten der letzten Zeile entspricht. Aus diesem Grund wissen wir, dass jede Summe nicht größer als 4 sein wird. Da jedes 4-Bit-int einen maximalen Wert von 15 (dezimal) hat, wissen wir, dass dies auch nicht überlaufen wird. Wie oben wird das Ergebnis wieder in gespeichert x.
Wir summieren nun die obere und untere Hälfte von xund wir haben einen 32-Bit-Wert, der gleich der Anzahl der Bits ist, die im Wert von festgelegt sind x.
Der Schlüssel hier ist, dass jeder Schritt eine paarweise Bitzählung an Ort und Stelle durchführt, bis wir die Gesamtzahl der Bits in der 32-Bit-Ganzzahl selbst haben.
14372200cookie-checkWie funktioniert dieser Code, um die Anzahl der 1-Bits zu zählen?yes
Ist das für Hausaufgaben?
– Frauref
15. Januar 2014 um 8:00 Uhr
Sehen graphics.stanford.edu/~seander/bithacks.htmlsuchen Sie nach “Zählbits gesetzt, parallel”.
– paxdiablo
15. Januar 2014 um 8:02 Uhr
@Femaref Nein, ist es nicht. Ich möchte nur herausfinden, wie es funktioniert.
– herohuyongtao
15. Januar 2014 um 8:04 Uhr
Sehr ähnliche Frage mit einer sehr schönen Erklärung 🙂 stackoverflow.com/a/10874449/1051677
– Silviu Burcea
15. Januar 2014 um 8:26 Uhr