Wie funktioniert dieser Code, um die Anzahl der 1-Bits zu zählen?

Lesezeit: 6 Minuten

Benutzeravatar von herohuyongtao
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.

int count_one(int x)
{
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
    return x;
}

  • 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

Dieser Algorithmus verwendet x sowohl als Quelle der Berechnung als auch als Speicher. Denken Sie zuerst darüber nach, was die Bitmasken sind:

0x55 = 01010101
0x33 = 00110011
0x0f = 00001111
0xff = 11111111

Gehen wir mit einem 8-Bit-Beispiel: a = 01101010

a & 0x55 = 01000000; (a >> 1) & 0x55 = 00010101 

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

Benutzeravatar von Łukasz Kidziński
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.

Für gerade Bits:

num:  10 11 00 11 11 00 01 10
mask: 01 01 01 01 01 01 01 01
res:  00 01 00 01 01 00 01 00

Für ungerade Bits:

num>>1: 01 01 10 01 11 10 00 11
mask:   01 01 01 01 01 01 01 01
res:    01 01 00 01 01 00 00 01

Wir addieren diese Ergebnisse und erhalten Summen in nachfolgenden Paaren

01 10 00 10 10 00 01 01

Wir wiederholen dasselbe mit folgenden Masken und entsprechenden Verschiebungen

2nd: 0011 0011 0011 0011
3rd: 0000 1111 0000 1111
4th: 0000 0000 1111 1111

Und wir bekommen:

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.

x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));

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.

x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));

Wir machen das Gleiche wie oben, dieses Mal summieren wir jedes Paar von 4 Bits zu jedem Satz von 8 Bits.

x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));

Wir summieren dann jedes 8-Bit-Paar zu jedem 16-Bit-Paar (die obere und untere Hälfte von x).

x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));

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.

x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));

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.

1437220cookie-checkWie funktioniert dieser Code, um die Anzahl der 1-Bits zu zählen?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy