Wie zählt man die Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl?

868

8 Bits, die die Zahl 7 darstellen, sehen folgendermaßen aus:

00000111

Es werden drei Bits gesetzt.

Was sind Algorithmen, um die Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl zu bestimmen?

Matt Howells
quelle
101
Dies ist das Hamming-Gewicht übrigens.
Purfideas
11
Was ist eine reale Anwendung dafür? (Dies ist nicht als Kritik zu
verstehen
8
Berechnung des Paritätsbits (nachschlagen), das als einfache Fehlererkennung in der Kommunikation verwendet wurde.
Dialecticus
8
@ Dialecticus, die Berechnung eines Paritätsbits ist billiger als die Berechnung des Hamming-Gewichts
finnw
15
@spookyjon Angenommen, Sie haben ein Diagramm als Adjazenzmatrix dargestellt, das im Wesentlichen ein bisschen gesetzt ist. Wenn Sie die Anzahl der Kanten eines Scheitelpunkts berechnen möchten, müssen Sie das Hamming-Gewicht einer Zeile im Bit-Set berechnen.
Fuz

Antworten:

850

Dies ist als " Hamming Weight ", "Popcount" oder "Sideways Addition" bekannt.

Der "beste" Algorithmus hängt wirklich davon ab, auf welcher CPU Sie sich befinden und wie Ihr Nutzungsmuster ist.

Einige CPUs haben einen einzigen eingebauten Befehl, um dies zu tun, und andere haben parallele Befehle, die auf Bitvektoren wirken. Die parallelen Anweisungen (wie x86 popcntauf CPUs, auf denen sie unterstützt werden) sind mit ziemlicher Sicherheit am schnellsten. Bei einigen anderen Architekturen ist möglicherweise ein langsamer Befehl implementiert, der mit einer mikrocodierten Schleife implementiert ist, die ein Bit pro Zyklus testet ( Zitieren erforderlich ).

Eine vorab ausgefüllte Tabellensuchmethode kann sehr schnell sein, wenn Ihre CPU über einen großen Cache verfügt und / oder Sie viele dieser Anweisungen in einer engen Schleife ausführen. Es kann jedoch unter den Kosten eines "Cache-Fehlers" leiden, bei dem die CPU einen Teil der Tabelle aus dem Hauptspeicher abrufen muss. (Suchen Sie jedes Byte einzeln nach, um die Tabelle klein zu halten.)

Wenn Sie wissen, dass Ihre Bytes meistens Nullen oder meistens Einsen sind, gibt es für diese Szenarien sehr effiziente Algorithmen.

Ich glaube, ein sehr guter Allzweckalgorithmus ist der folgende, der als "paralleler" oder "SWAR-Algorithmus mit variabler Genauigkeit" bekannt ist. Ich habe dies in einer C-ähnlichen Pseudosprache ausgedrückt. Möglicherweise müssen Sie es anpassen, um für eine bestimmte Sprache zu funktionieren (z. B. mit uint32_t für C ++ und >>> in Java):

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

Für JavaScript: coerce zu integer mit |0für die Leistung: ändern Sie die erste Zeilei = (i|0) - ((i >> 1) & 0x55555555);

Dies hat das beste Worst-Case-Verhalten aller diskutierten Algorithmen und kann daher effizient mit allen Verwendungsmustern oder Werten umgehen, die Sie darauf werfen.


Wie dieser SWAR-Bithack funktioniert:

i = i - ((i >> 1) & 0x55555555);

Der erste Schritt ist eine optimierte Version der Maskierung, um die ungeraden / geraden Bits zu isolieren, zu verschieben, um sie auszurichten, und um sie hinzuzufügen. Dies führt effektiv 16 separate Additionen in 2-Bit-Akkumulatoren durch ( SWAR = SIMD Within A Register ). Wie (i & 0x55555555) + ((i>>1) & 0x55555555).

Der nächste Schritt nimmt die ungeraden / geraden acht dieser 16x 2-Bit-Akkumulatoren und addiert sie erneut, wodurch 8x 4-Bit-Summen erzeugt werden. Die i - ...Optimierung ist diesmal nicht möglich, daher wird nur vor / nach dem Schalten maskiert. Die Verwendung derselben 0x33...Konstante beide Male anstelle 0xccc...vor dem Verschieben ist eine gute Sache, wenn Sie für ISAs kompilieren, die 32-Bit-Konstanten in Registern separat erstellen müssen.

Der letzte Schritt (i + (i >> 4)) & 0x0F0F0F0Fzum Verschieben und Hinzufügen wird auf 4x 8-Bit-Akkumulatoren erweitert. Es maskiert nach dem Hinzufügen statt vorher, da der Maximalwert in einem 4-Bit-Akkumulator ist 4, wenn alle 4 Bits der entsprechenden Eingangsbits gesetzt wurden. 4 + 4 = 8, was immer noch in 4 Bits passt, so dass ein Übertrag zwischen Nibble-Elementen in unmöglich ist i + (i >> 4).

Bisher ist dies nur eine ganz normale SIMD mit SWAR-Techniken und einigen cleveren Optimierungen. Wenn Sie für zwei weitere Schritte mit demselben Muster fortfahren, kann dies auf 2x 16-Bit und dann auf 1x 32-Bit-Anzahl erweitert werden. Auf Maschinen mit schneller Hardware-Multiplikation gibt es jedoch einen effizienteren Weg:

Sobald wir wenige "Elemente" haben, kann eine Multiplikation mit einer magischen Konstante alle Elemente zum obersten Element zusammenfassen . In diesem Fall Byte-Elemente. Das Multiplizieren erfolgt durch Verschieben und Addieren nach links, sodass eine Multiplikation der x * 0x01010101Ergebnisse erfolgt x + (x<<8) + (x<<16) + (x<<24). Unsere 8-Bit-Elemente sind breit genug (und klein genug), dass dies keinen Übertrag in die oberen 8 Bits erzeugt.

Eine 64-Bit-Version davon kann 8x 8-Bit-Elemente in einer 64-Bit-Ganzzahl mit einem 0x0101010101010101-Multiplikator ausführen und das High-Byte mit extrahieren >>56. Es sind also keine zusätzlichen Schritte erforderlich, sondern nur breitere Konstanten. Dies ist, was GCC __builtin_popcountllauf x86-Systemen verwendet, wenn die Hardwareanweisung popcntnicht aktiviert ist. Wenn Sie hierfür eingebaute oder intrinsische Funktionen verwenden können, geben Sie dem Compiler die Möglichkeit, zielspezifische Optimierungen vorzunehmen.


Mit voller SIMD für breitere Vektoren (z. B. Zählen eines ganzen Arrays)

Dieser bitweise SWAR-Algorithmus könnte parallelisiert werden, um in mehreren Vektorelementen gleichzeitig statt in einem einzelnen Ganzzahlregister ausgeführt zu werden, um eine Beschleunigung auf CPUs mit SIMD, aber ohne verwendbaren Popcount-Befehl zu erreichen. (zB x86-64-Code, der auf jeder CPU ausgeführt werden muss, nicht nur auf Nehalem oder höher.)

Der beste Weg, Vektoranweisungen für Popcount zu verwenden, ist normalerweise die Verwendung eines variablen Shuffle, um eine Tabellensuche für 4 Bits gleichzeitig für jedes Byte parallel durchzuführen. (Die 4 Bits indizieren eine 16-Eintragstabelle, die in einem Vektorregister gehalten wird).

Auf Intel-CPUs kann der Hardware-64- Bit- Popcnt-Befehl eine bitparallele SSSE3 PSHUFB-Implementierung um etwa den Faktor 2 übertreffen , jedoch nur, wenn Ihr Compiler dies genau richtig macht . Andernfalls kann SSE deutlich voraus sein. Neuere Compilerversionen sind sich des Problems der falschen Abhängigkeit von popcnt von Intel bewusst .

Verweise:

Matt Howells
quelle
87
Ha! Ich liebe die NumberOfSetBits () -Funktion, aber viel Glück beim Durchführen einer Codeüberprüfung. :-)
Jason S
37
Vielleicht sollte es verwendet werden unsigned int, um leicht zu zeigen, dass es frei von Anzeichen von Komplikationen ist. Wäre es uint32_tauch sicherer, wenn Sie auf allen Plattformen das bekommen, was Sie erwarten?
Craig McQueen
35
@nonnb: Eigentlich ist der Code, wie geschrieben, fehlerhaft und muss gewartet werden. >>ist implementierungsdefiniert für negative Werte. Das Argument muss geändert (oder umgewandelt) werden unsigned, und da der Code 32-Bit-spezifisch ist, sollte er wahrscheinlich verwendet werden uint32_t.
R .. GitHub STOP HELPING ICE
6
Es ist nicht wirklich magisch. Es werden Bitsätze hinzugefügt, dies jedoch mit einigen cleveren Optimierungen. Der in der Antwort angegebene Wikipedia-Link erklärt gut, was los ist, aber ich gehe Zeile für Zeile. 1) Zählen Sie die Anzahl der Bits in jedem Bitpaar hoch und setzen Sie diese Anzahl in dieses Bitpaar (Sie haben 00, 01 oder 10). Das "clevere" Bit hier ist das Subtrahieren, das eine Maske vermeidet. 2) Fügen Sie Paare dieser Bitpaarsummen zu den entsprechenden Knabbereien hinzu. Hier ist nichts kluges, aber jedes Knabbern hat jetzt den Wert 0-4. (Fortsetzung)
Dash-Tom-Bang
8
Ein weiterer Hinweis: Dies erstreckt sich auf 64- und 128-Bit-Register, indem einfach die Konstanten entsprechend erweitert werden. Interessanterweise (für mich) sind diese Konstanten auch ~ 0/3, 5, 17 und 255; die ersten drei sind 2 ^ n + 1. Dies alles macht mehr Sinn, je mehr Sie darauf starren und unter der Dusche darüber nachdenken. :)
Dash-Tom-Bang
214

Berücksichtigen Sie auch die integrierten Funktionen Ihrer Compiler.

Auf dem GNU-Compiler können Sie beispielsweise einfach Folgendes verwenden:

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

Im schlimmsten Fall generiert der Compiler einen Aufruf einer Funktion. Im besten Fall gibt der Compiler eine CPU-Anweisung aus, um denselben Job schneller auszuführen.

Die GCC-Eigenschaften funktionieren sogar plattformübergreifend. Popcount wird zum Mainstream in der x86-Architektur, daher ist es sinnvoll, jetzt das Intrinsic zu verwenden. Andere Architekturen haben die Popcount seit Jahren.


Unter x86 können Sie dem Compiler mitteilen, dass er Unterstützung für popcntAnweisungen mit -mpopcntoder -msse4.2zur Aktivierung der Vektoranweisungen übernehmen kann, die in derselben Generation hinzugefügt wurden. Siehe GCC x86-Optionen . -march=nehalem(oder -march=welche CPU auch immer Ihr Code annehmen und einstellen soll) könnte eine gute Wahl sein. Das Ausführen der resultierenden Binärdatei auf einer älteren CPU führt zu einem Fehler mit unzulässigen Anweisungen.

Verwenden Sie -march=native (mit gcc, clang oder ICC), um Binärdateien für den Computer zu optimieren, auf dem Sie sie erstellen .

MSVC bietet eine Eigenschaft für den x86- popcntBefehl , aber im Gegensatz zu gcc ist es eine Eigenschaft für die Hardware-Anweisung und erfordert Hardware-Unterstützung.


Verwenden std::bitset<>::count()anstelle eines eingebauten

Theoretisch sollte jeder Compiler, der weiß, wie man effizient für die Ziel-CPU zählt, diese Funktionalität über ISO C ++ verfügbar machen std::bitset<>. In der Praxis ist der Bit-Hack AND / shift / ADD in einigen Fällen für einige Ziel-CPUs möglicherweise besser geeignet.

Für Zielarchitekturen, bei denen Hardware-Popcount eine optionale Erweiterung ist (wie x86), verfügen nicht alle Compiler über eine std::bitset, die diese nutzt, wenn sie verfügbar ist. Zum Beispiel hat MSVC keine Möglichkeit, die popcntUnterstützung zur Kompilierungszeit zu aktivieren , und verwendet immer eine Tabellensuche , auch mit /Ox /arch:AVX(was SSE4.2 impliziert, obwohl es technisch gesehen ein separates Feature-Bit für gibtpopcnt .)

Aber zumindest erhalten Sie etwas Portables, das überall funktioniert, und mit gcc / clang mit den richtigen Zieloptionen erhalten Sie Hardware-Popcount für Architekturen, die dies unterstützen.

#include <bitset>
#include <limits>
#include <type_traits>

template<typename T>
//static inline  // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value,  unsigned >::type 
popcount(T x)
{
    static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");

    // sizeof(x)*CHAR_BIT
    constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
    // std::bitset constructor was only unsigned long before C++11.  Beware if porting to C++03
    static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");

    typedef typename std::make_unsigned<T>::type UT;        // probably not needed, bitset width chops after sign-extension

    std::bitset<bitwidth> bs( static_cast<UT>(x) );
    return bs.count();
}

Siehe asm von gcc, clang, icc und MSVC im Godbolt-Compiler-Explorer.

x86-64 gcc -O3 -std=gnu++11 -mpopcntgibt Folgendes aus :

unsigned test_short(short a) { return popcount(a); }
    movzx   eax, di      # note zero-extension, not sign-extension
    popcnt  rax, rax
    ret
unsigned test_int(int a) { return popcount(a); }
    mov     eax, edi
    popcnt  rax, rax
    ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
    xor     eax, eax     # gcc avoids false dependencies for Intel CPUs
    popcnt  rax, rdi
    ret

PowerPC64 gcc -O3 -std=gnu++11gibt aus (für die intarg-Version):

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

Diese Quelle ist überhaupt nicht x86-spezifisch oder GNU-spezifisch, sondern lässt sich nur für x86 mit gcc / clang / icc gut kompilieren.

Beachten Sie auch, dass der Fallback von gcc für Architekturen ohne Popcount für einzelne Befehle eine Tabellensuche nach Byte ist. Dies ist zum Beispiel für ARM nicht wunderbar .

Peter Cordes
quelle
5
Ich bin damit einverstanden, dass dies im Allgemeinen eine gute Vorgehensweise ist, aber unter XCode / OSX / Intel wurde festgestellt, dass langsamer Code generiert wird als bei den meisten hier veröffentlichten Vorschlägen. Siehe meine Antwort für Details.
5
Der Intel i5 / i7 verfügt über den SSE4-Befehl POPCNT, der dies unter Verwendung von Allzweckregistern ausführt. GCC auf meinem System gibt diese Anweisung nicht mit dieser Eigenschaft aus, da noch keine Option -march = nehalem vorhanden ist.
Matja
3
@matja, mein GCC 4.4.1 gibt die popcnt-Anweisung aus, wenn ich mit -msse4.2
Nils Pipenbrinck
74
benutze c ++ 's std::bitset::count. Nach dem Inlinen wird dies zu einem einzigen __builtin_popcountAufruf kompiliert .
Deft_code
1
@nlucaroni Nun ja. Zeiten ändern sich. Ich habe diese Antwort im Jahr 2008 geschrieben. Heutzutage haben wir native Popcount und die intrinsische wird zu einer einzigen Assembler-Anweisung kompiliert, wenn die Plattform dies zulässt.
Nils Pipenbrinck
184

Meiner Meinung nach ist die "beste" Lösung die, die von einem anderen Programmierer (oder dem ursprünglichen Programmierer zwei Jahre später) ohne ausführliche Kommentare gelesen werden kann. Vielleicht möchten Sie die schnellste oder klügste Lösung, die einige bereits bereitgestellt haben, aber ich bevorzuge jederzeit die Lesbarkeit gegenüber der Klugheit.

unsigned int bitCount (unsigned int value) {
    unsigned int count = 0;
    while (value > 0) {           // until all bits are zero
        if ((value & 1) == 1)     // check lower bit
            count++;
        value >>= 1;              // shift bits, removing lower bit
    }
    return count;
}

Wenn Sie mehr Geschwindigkeit wünschen (und davon ausgehen, dass Sie diese gut dokumentieren, um Ihren Nachfolgern zu helfen), können Sie eine Tabellensuche verwenden:

// Lookup table for fast calculation of bits set in 8-bit unsigned char.

static unsigned char oneBitsInUChar[] = {
//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)
//  =====================================================
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
    : : :
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};

// Function for fast calculation of bits set in 16-bit unsigned short.

unsigned char oneBitsInUShort (unsigned short x) {
    return oneBitsInUChar [x >>    8]
         + oneBitsInUChar [x &  0xff];
}

// Function for fast calculation of bits set in 32-bit unsigned int.

unsigned char oneBitsInUInt (unsigned int x) {
    return oneBitsInUShort (x >>     16)
         + oneBitsInUShort (x &  0xffff);
}

Obwohl diese auf bestimmten Datentypgrößen beruhen, sind sie nicht so portabel. Da jedoch viele Leistungsoptimierungen ohnehin nicht portierbar sind, ist dies möglicherweise kein Problem. Wenn Sie Portabilität wünschen, würde ich mich an die lesbare Lösung halten.

paxdiablo
quelle
21
Anstatt durch 2 zu teilen und als "Verschiebungsbits ..." zu kommentieren, sollten Sie einfach den Verschiebungsoperator (>>) verwenden und den Kommentar weglassen.
Indiv
9
würde es nicht mehr Sinn zu ersetzen macht if ((value & 1) == 1) { count++; }mit count += value & 1?
Ponkadoodle
21
Nein, die beste Lösung ist in diesem Fall nicht die am besten lesbare. Hier ist der beste Algorithmus der schnellste.
NikiC
21
Das ist ganz deine Meinung, @nikic, obwohl du mich natürlich ablehnen kannst. In der Frage, wie "am besten" zu quantifizieren ist, wurde nicht erwähnt, dass die Wörter "Leistung" oder "schnell" nirgends zu sehen sind. Deshalb habe ich mich für lesbar entschieden.
Paxdiablo
3
Ich lese diese Antwort 3 Jahre später und finde sie die beste Antwort, da sie lesbar ist und mehr Kommentare enthält. Zeitraum.
Waka-Waka-Waka
98

Aus Hacker's Delight, p. 66, Abbildung 5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

Wird in ~ 20-ish-Anweisungen (archabhängig) ausgeführt, keine Verzweigung.

Hacker's Delight ist herrlich! Sehr empfehlenswert.

Kevin Little
quelle
8
Die Java-Methode Integer.bitCount(int)verwendet genau diese Implementierung.
Marco Bolis
Wir haben ein kleines Problem damit - wie würde sich das ändern, wenn wir uns nur um 16-Bit-Werte anstatt um 32-Bit kümmern würden?
Jeremy Blum
Vielleicht ist die Freude der Hacker entzückend, aber ich würde jedem, der dies nennt, einen guten Tritt geben, popanstatt population_count(oder pop_cntwenn Sie eine Abkürzung haben müssen). @ MarcoBolis Ich gehe davon aus, dass dies für alle Java-Versionen gilt, aber offiziell wäre dies implementierungsabhängig :)
Maarten Bodewes
Und dies erfordert keine Multiplikationen, wie der Code in der akzeptierten Antwort.
Alex
Beachten Sie, dass bei der Verallgemeinerung auf 64-Bit ein Problem auftritt. Das Ergebnis kann aufgrund der Maske nicht 64 sein.
Albert van der Horst
76

Ich denke, der schnellste Weg - ohne Nachschlagetabellen und Popcount zu verwenden - ist der folgende. Es zählt die gesetzten Bits mit nur 12 Operationen.

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

Dies funktioniert, weil Sie die Gesamtzahl der gesetzten Bits zählen können, indem Sie sie in zwei Hälften teilen, die Anzahl der gesetzten Bits in beiden Hälften zählen und sie dann addieren. Auch als Divide and ConquerParadigma bekannt. Lassen Sie uns ins Detail gehen ..

v = v - ((v >> 1) & 0x55555555); 

Die Anzahl der Bits in zwei Bits sein kann 0b00, 0b01oder 0b10. Versuchen wir das mit 2 Bits herauszufinden.

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

Dies war erforderlich: Die letzte Spalte zeigt die Anzahl der gesetzten Bits in jedem Zwei-Bit-Paar. Wenn die zwei Bit - Zahl wird >= 2 (0b10)dann anderzeugt 0b01, sonst erzeugt es 0b00.

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

Diese Aussage sollte leicht verständlich sein. Nach der ersten Operation haben wir die Anzahl der gesetzten Bits in jeweils zwei Bits, jetzt addieren wir diese Anzahl in jeweils 4 Bits.

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

Wir fassen dann das obige Ergebnis zusammen und geben uns die Gesamtzahl der gesetzten Bits in 4 Bits. Die letzte Aussage ist die schwierigste.

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

Lassen Sie es uns weiter aufschlüsseln ...

v + (v >> 4)

Es ist ähnlich wie bei der zweiten Aussage; Stattdessen zählen wir die gesetzten Bits in 4er-Gruppen. Wir wissen - aufgrund unserer vorherigen Operationen -, dass jedes Halbbyte die Anzahl der gesetzten Bits enthält. Schauen wir uns ein Beispiel an. Angenommen, wir haben das Byte 0b01000010. Dies bedeutet, dass für das erste Halbbyte 4 Bit und für das zweite Halbbyte 2 Bit festgelegt sind. Jetzt addieren wir diese Knabbereien.

0b01000010 + 0b01000000

Es gibt uns die Anzahl der gesetzten Bits in einem Byte im ersten Halbbyte 0b01100010und daher maskieren wir die letzten vier Bytes aller Bytes in der Zahl (verwerfen sie).

0b01100010 & 0xF0 = 0b01100000

Jetzt enthält jedes Byte die Anzahl der gesetzten Bits. Wir müssen sie alle zusammen addieren. Der Trick besteht darin, das Ergebnis mit 0b10101010einer interessanten Eigenschaft zu multiplizieren . Wenn unsere Nummer vier Bytes hat A B C D, führt dies zu einer neuen Nummer mit diesen BytesA+B+C+D B+C+D C+D D . Für eine 4-Byte-Nummer können maximal 32 Bit gesetzt werden, die als dargestellt werden können 0b00100000.

Jetzt brauchen wir nur noch das erste Byte, das die Summe aller gesetzten Bits in allen Bytes enthält, und wir bekommen es durch >> 24. Dieser Algorithmus wurde für 32 bitWörter entwickelt, kann jedoch leicht für 64 bitWörter geändert werden .

vidit
quelle
Worum geht es c = ? Sieht so aus, als sollte es beseitigt werden. Schlagen Sie außerdem einen zusätzlichen Parensatz A "(((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24" vor, um einige klassische Warnungen zu vermeiden.
chux
4
Ein wichtiges Merkmal ist , dass diese 32-Bit - Routine für beide funktioniert popcount(int v)und popcount(unsigned v). Berücksichtigen Sie für die Portabilität popcount(uint32_t v)usw. den Teil * 0x1010101.
chux
Soße ? (Buch, Link, Namen der Invetoren usw.) wäre SEHR willkommen. Denn dann können wir das in unsere Codebasen mit einem Kommentar einfügen, woher es kommt.
v.oddou
1
Ich denke, zur besseren Übersichtlichkeit sollte die letzte Zeile wie folgt geschrieben werden: return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;Wir müssen also keine Buchstaben zählen, um zu sehen, was Sie tatsächlich tun (da Sie die erste verworfen haben 0, dachte ich versehentlich, Sie hätten das falsche (gespiegelte) Bitmuster als Maske verwendet - bis ich feststellte, dass es nur 7 Buchstaben gibt und nicht 8).
Emem
Diese Multiplikation mit 0x01010101 kann je nach Prozessor langsam sein. In meinem alten PowerBook G4 war beispielsweise 1 Multiplikation ungefähr so ​​langsam wie 4 Additionen (nicht so schlecht wie Division, wobei 1 Division ungefähr so ​​langsam war wie 23 Additionen).
George Koehler
54

Ich langweilte mich und plante eine Milliarde Iterationen von drei Ansätzen. Der Compiler ist gcc -O3. CPU ist alles, was sie in das Macbook Pro der 1. Generation stecken.

Am schnellsten ist mit 3,7 Sekunden Folgendes:

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
    return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}

Der zweite Platz geht an denselben Code, aber es werden 4 Bytes anstelle von 2 Halbwörtern nachgeschlagen. Das dauerte ungefähr 5,5 Sekunden.

Der dritte Platz geht an den Bit-Twiddling-Ansatz „Seitwärtsaddition“, der 8,6 Sekunden dauerte.

Der vierte Platz geht an GCCs __builtin_popcount () mit beschämenden 11 Sekunden.

Das Zählen nacheinander war etwas langsamer, und es langweilte mich, darauf zu warten, dass es abgeschlossen war.

Wenn Sie also vor allem Wert auf Leistung legen, verwenden Sie den ersten Ansatz. Wenn Sie sich interessieren, aber nicht genug, um 64 KB RAM dafür auszugeben, verwenden Sie den zweiten Ansatz. Verwenden Sie andernfalls den lesbaren (aber langsamen) Einzelbit-zu-Zeit-Ansatz.

Es ist schwer, sich eine Situation vorzustellen, in der Sie den Bit-Twiddling-Ansatz verwenden möchten.

Edit: Ähnliche Ergebnisse hier .

Mike F.
quelle
49
@Mike, Der tabellenbasierte Ansatz ist unschlagbar, wenn sich die Tabelle im Cache befindet. Dies geschieht in Mikro-Benchmarks (z. B. Millionen von Tests in einer engen Schleife). Ein Cache-Miss dauert jedoch ungefähr 200 Zyklen, und selbst der naivste Popcount wird hier schneller sein. Es kommt immer auf die Anwendung an.
Nils Pipenbrinck
10
Wenn Sie diese Routine nicht einige Millionen Mal in einer engen Schleife aufrufen, haben Sie keinen Grund, sich überhaupt um ihre Leistung zu kümmern, und können genauso gut den naiven, aber lesbaren Ansatz verwenden, da der Leistungsverlust vernachlässigbar ist. Und FWIW, die 8-Bit-LUT wird innerhalb von 10 bis 20 Anrufen cache-heiß.
6
Ich denke nicht, dass es so schwer ist, sich eine Situation vorzustellen, in der dies ein Blattaufruf ist, der von der Methode in Ihrer App ausgeht, die tatsächlich das schwere Heben ausführt. Je nachdem, was sonst noch los ist (und was eingefädelt wird), könnte die kleinere Version gewinnen. Es wurden viele Algorithmen geschrieben, die ihre Kollegen aufgrund der besseren Referenzlokalität schlagen. Warum nicht auch das?
Jason
Versuchen Sie dies mit clang, es ist wesentlich intelligenter bei der Implementierung von integrierten Funktionen.
Matt Joiner
3
GCC gibt keine Popcont-Anweisungen aus, es sei denn, es wird mit -msse4.2 aufgerufen. Dieser Fall ist schneller als 'seitwärts addieren'.
lvella
54

Wenn Sie Java verwenden, wird dies von der integrierten Methode ausgeführt Integer.bitCount.

Noether
quelle
Wenn sun verschiedene APIs bereitgestellt hat, muss im Hintergrund eine Logik verwendet werden, oder?
Vallabh Patade
2
Als Randnotiz verwendet die Implementierung von Java denselben Algorithmus, auf den Kevin Little hingewiesen hat .
Marco Bolis
2
Abgesehen von der Implementierung ist dies wahrscheinlich die klarste Absichtserklärung für Entwickler, die Ihren Code nach Ihnen (oder wenn Sie 6 Monate später darauf
zurückkommen
31
unsigned int count_bit(unsigned 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;
}

Lassen Sie mich diesen Algorithmus erklären.

Dieser Algorithmus basiert auf dem Divide and Conquer-Algorithmus. Angenommen, es gibt eine 8-Bit-Ganzzahl 213 (11010101 in Binär), funktioniert der Algorithmus folgendermaßen (jedes Mal, wenn zwei Nachbarblöcke zusammengeführt werden):

+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x
|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge
|    0 0 1 1    |    0 0 1 0    |  <- second time merge
|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)
+-------------------------------+
abcdabcd987
quelle
7
Dieser Algorithmus ist die Version, die Matt Howells veröffentlicht hat, bevor er dahingehend optimiert wurde, dass er nicht mehr lesbar ist.
Lefteris E
29

Dies ist eine dieser Fragen, bei denen es hilfreich ist, Ihre Mikroarchitektur zu kennen. Ich habe gerade zwei Varianten unter gcc 4.3.3 zeitlich festgelegt, die mit -O3 unter Verwendung von C ++ - Inlines kompiliert wurden, um den Funktionsaufruf-Overhead zu eliminieren, eine Milliarde Iterationen, wobei die laufende Summe aller Zählungen beibehalten wurde, um sicherzustellen, dass der Compiler nichts Wichtiges entfernt, und rdtsc für das Timing verwendet ( Takt genau).

inline int pop2 (vorzeichenloses x, vorzeichenloses y)
{
    x = x - ((x >> 1) & 0x55555555);
    y = y - ((y >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    y = y + (y >> 8);
    x = x + (x >> 16);
    y = y + (y >> 16);
    return (x + y) & 0x000000FF;
}}

Das unveränderte Hacker's Delight benötigte 12,2 Gigacycles. Meine parallele Version (doppelt so viele Bits) läuft in 13.0 Gigacycles. Auf einem 2,4-GHz-Core-Duo verstrichen insgesamt 10,5 Sekunden für beide. 25 Gigacycles = etwas mehr als 10 Sekunden bei dieser Taktfrequenz, daher bin ich zuversichtlich, dass mein Timing stimmt.

Dies hat mit Befehlsabhängigkeitsketten zu tun, die für diesen Algorithmus sehr schlecht sind. Ich könnte die Geschwindigkeit mit einem Paar 64-Bit-Registern wieder fast verdoppeln. In der Tat, wenn ich klug wäre und x + ya etwas früher hinzufügen würde, könnte ich einige Schichten rasieren. Die 64-Bit-Version mit einigen kleinen Verbesserungen würde sogar herauskommen, aber wieder doppelt so viele Bits zählen.

Mit 128-Bit-SIMD-Registern, einem weiteren Faktor von zwei, und den SSE-Befehlssätzen gibt es oft auch clevere Abkürzungen.

Es gibt keinen Grund, warum der Code besonders transparent ist. Die Schnittstelle ist einfach, der Algorithmus kann an vielen Stellen online referenziert werden und ist für umfassende Unit-Tests zugänglich. Der Programmierer, der darauf stößt, könnte sogar etwas lernen. Diese Bitoperationen sind auf Maschinenebene äußerst natürlich.

OK, ich habe mich für die optimierte 64-Bit-Version entschieden. Für diese eine Größe von (unsigned long) == 8

inline int pop2 (vorzeichenloses langes x, vorzeichenloses langes y)
{
    x = x - ((x >> 1) & 0x5555555555555555);
    y = y - ((y >> 1) & 0x5555555555555555);
    x = (x & 0x333333333333333333) + ((x >> 2) & 0x3333333333333333);
    y = (y & 0x333333333333333333) + ((y >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
    x = x + y; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x + (x >> 32); 
    return x & 0xFF;
}}

Das sieht ungefähr richtig aus (ich teste aber nicht sorgfältig). Jetzt kommen die Timings bei 10,70 Gigacycles / 14,1 Gigacycles heraus. Diese spätere Zahl summierte sich auf 128 Milliarden Bits und entspricht 5,9 Sekunden, die auf dieser Maschine verstrichen sind. Die nicht parallele Version beschleunigt ein kleines bisschen, weil ich im 64-Bit-Modus arbeite und 64-Bit-Register etwas besser mag als 32-Bit-Register.

Mal sehen, ob es hier ein bisschen mehr OOO-Pipelining gibt. Das war etwas komplizierter, also habe ich tatsächlich ein bisschen getestet. Jeder Term allein ergibt 64, alle zusammen 256.

inline int pop4 (vorzeichenloses langes x, vorzeichenloses langes y, 
                unsigned long u, unsigned long v)
{
  Aufzählung {m1 = 0x5555555555555555, 
         m2 = 0x333333333333333333, 
         m3 = 0x0F0F0F0F0F0F0F0F, 
         m4 = 0x000000FF000000FF};

    x = x - ((x >> 1) & m1);
    y = y - ((y >> 1) & m1);
    u = u - ((u >> 1) & m1);
    v = v - ((v >> 1) & m1);
    x = (x & m2) + ((x >> 2) & m2);
    y = (y & m2) + ((y >> 2) & m2);
    u = (u & m2) + ((u >> 2) & m2);
    v = (v & m2) + ((v >> 2) & m2);
    x = x + y; 
    u = u + v; 
    x = (x & m3) + ((x >> 4) & m3);
    u = (u & m3) + ((u >> 4) & m3);
    x = x + u; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & m4; 
    x = x + (x >> 32);
    return x & 0x000001FF;
}}

Ich war für einen Moment aufgeregt, aber es stellte sich heraus, dass gcc Inline-Streiche mit -O3 spielt, obwohl ich das Inline-Schlüsselwort in einigen Tests nicht verwende. Wenn ich gcc Streiche spielen lasse, dauert eine Milliarde Aufrufe von pop4 () 12,56 Gigacycles, aber ich habe festgestellt, dass Argumente als konstante Ausdrücke gefaltet werden. Eine realistischere Zahl scheint 19,6 gc für eine weitere Beschleunigung von 30% zu sein. Meine Testschleife sieht jetzt so aus und stellt sicher, dass jedes Argument anders genug ist, um zu verhindern, dass gcc Streiche spielt.

   hitime b4 = rdtsc (); 
   für (vorzeichenloses langes i = 10L * 1000 * 1000 * 1000; i <11L * 1000 * 1000 * 1000; ++ i) 
      summe + = pop4 (i, i ^ 1, ~ i, i | 1); 
   Trefferzeit e4 = rdtsc (); 

In 8,17 Sekunden summierten sich 256 Milliarden Bits. Funktioniert für 32 Millionen Bit auf 1,02 Sekunden, wie in der 16-Bit-Tabellensuche angegeben. Kann nicht direkt verglichen werden, da die andere Bank keine Taktrate angibt, aber es sieht so aus, als hätte ich den Rotz aus der 64-KB-Tabellenausgabe geschlagen, was in erster Linie eine tragische Verwendung des L1-Cache ist.

Update: beschlossen, das Offensichtliche zu tun und pop6 () zu erstellen, indem vier weitere doppelte Zeilen hinzugefügt wurden. Kam auf 22,8 gc, 384 Milliarden Bits summiert in 9,5s verstrichen. Es gibt also weitere 20% jetzt bei 800 ms für 32 Milliarden Bits.

user183351
quelle
2
Die beste Nicht-Assembler-Form wie diese habe ich gesehen, wie 24 32-Bit-Wörter gleichzeitig abgewickelt wurden. dalkescientific.com/writings/diary/popcnt.c , stackoverflow.com/questions/3693981/… , dalkescientific.com/writings/diary/archive/2008/07/05/…
Matt Joiner
28

Warum nicht iterativ durch 2 teilen?

count = 0
während n> 0
  if (n% 2) == 1
    count + = 1
  n / = 2  

Ich stimme zu, dass dies nicht das schnellste ist, aber "das Beste" ist etwas mehrdeutig. Ich würde jedoch argumentieren, dass "am besten" ein Element der Klarheit haben sollte

Daniel
quelle
Das wird funktionieren und ist leicht zu verstehen, aber es gibt schnellere Methoden.
Matt Howells
2
Es sei denn , Sie das eine tun LOT , würde die Auswirkungen auf die Leistung vernachlässigbar sein. Wenn alle Dinge gleich sind, stimme ich Daniel zu, dass "am besten" impliziert, dass "nicht wie Kauderwelsch liest".
2
Ich habe bewusst nicht "am besten" definiert, um eine Vielzahl von Methoden zu erhalten. Seien wir ehrlich, wenn wir das Niveau dieser Art von Bit-Twiddling erreicht haben, suchen wir wahrscheinlich nach etwas überschnellem, das aussieht, als hätte ein Schimpanse es getippt.
Matt Howells
6
Schlechter Code. Ein Compiler könnte einen guten daraus machen, aber in meinen Tests hat GCC dies nicht getan. Ersetzen Sie (n% 2) durch (n & 1); UND viel schneller als MODULO. Ersetzen Sie (n / = 2) durch (n >> = 1); Bitshifting viel schneller als Division.
Mecki
6
@Mecki: In meinen Tests, gcc (4.0, O3) hat die offensichtlichen Optimierungen tun.
26

Das Bit-Twiddling von Hacker's Delight wird viel deutlicher, wenn Sie die Bitmuster ausschreiben.

unsigned int bitCount(unsigned int x)
{
  x = ((x >> 1) & 0b01010101010101010101010101010101)
     + (x       & 0b01010101010101010101010101010101);
  x = ((x >> 2) & 0b00110011001100110011001100110011)
     + (x       & 0b00110011001100110011001100110011); 
  x = ((x >> 4) & 0b00001111000011110000111100001111)
     + (x       & 0b00001111000011110000111100001111); 
  x = ((x >> 8) & 0b00000000111111110000000011111111)
     + (x       & 0b00000000111111110000000011111111); 
  x = ((x >> 16)& 0b00000000000000001111111111111111)
     + (x       & 0b00000000000000001111111111111111); 
  return x;
}

Der erste Schritt addiert die geraden Bits zu den ungeraden Bits und erzeugt eine Summe von Bits in jeweils zwei. Die anderen Schritte fügen Blöcke höherer Ordnung zu Blöcken niedriger Ordnung hinzu und verdoppeln die Blockgröße bis zum Ende, bis die endgültige Zählung den gesamten Int aufnimmt.

John Dimm
quelle
3
Diese Lösung scheint ein kleines Problem zu haben, das mit der Priorität des Bedieners zusammenhängt. Für jeden Term sollte es heißen: x = (((x >> 1) & 0b01010101010101010101010101010101) + (x & 0b01010101010101010101010101010101)); (dh zusätzliche Parens hinzugefügt).
Nopik
21

Für ein fröhliches Medium zwischen einer 2 32- Nachschlagetabelle und dem individuellen Durchlaufen jedes Bits:

int bitcount(unsigned int num){
    int count = 0;
    static int nibblebits[] =
        {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    for(; num != 0; num >>= 4)
        count += nibblebits[num & 0x0f];
    return count;
}

Von http://ctips.pbwiki.com/CountBits

PhirePhly
quelle
Nicht tragbar. Was ist, wenn die CPU 9-Bit-Bytes hat? Ja, es gibt solche echten CPUs da draußen ...
Robert S. Barnes
15
@ Robert S. Barnes, diese Funktion funktioniert weiterhin. Es wird keine Annahme über die native Wortgröße und überhaupt kein Verweis auf "Bytes" gemacht.
Finnw
19

Dies kann in erfolgen O(k), wobei kdie Anzahl der gesetzten Bits ist.

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}
herohuyongtao
quelle
Dies ist im Wesentlichen Brian Kernighans (erinnerst du dich an ihn?) Algorithmus, mit der geringfügigen Änderung, dass er die prägnantere n &= (n-1)Form verwendete.
Adrian Mole
17

Es ist nicht die schnellste oder beste Lösung, aber ich fand die gleiche Frage auf meinem Weg und begann zu denken und zu denken. Schließlich wurde mir klar, dass dies so möglich ist, wenn Sie das Problem von der mathematischen Seite her betrachten und ein Diagramm zeichnen. Dann stellen Sie fest, dass es sich um eine Funktion handelt, die einen periodischen Teil hat, und dann erkennen Sie den Unterschied zwischen den Perioden ... also Bitte schön:

unsigned int f(unsigned int x)
{
    switch (x) {
        case 0:
            return 0;
        case 1:
            return 1;
        case 2:
            return 1;
        case 3:
            return 2;
        default:
            return f(x/4) + f(x%4);
    }
}
Peter
quelle
4
Oh, das gefällt mir. Wie wäre es mit der Python-Version:def f(i, d={0:lambda:0, 1:lambda:1, 2:lambda:1, 3:lambda:2}): return d.get(i, lambda: f(i//4) + f(i%4))()
Unterlauf
10

Die gesuchte Funktion wird häufig als "Seitwärtssumme" oder "Bevölkerungszahl" einer Binärzahl bezeichnet. Knuth diskutiert es in Pre-Fascicle 1A, S. 11-12 (obwohl es in Band 2, 4.6.3- (7) eine kurze Referenz gab.)

Der locus classicus ist Peter Wegners Artikel "Eine Technik zum Zählen von Personen in einem binären Computer" aus den Mitteilungen der ACM , Band 3 (1960) Nummer 5, Seite 322 . Dort gibt er zwei verschiedene Algorithmen an, einen, der für Zahlen optimiert ist, von denen erwartet wird, dass sie "spärlich" sind (dh eine kleine Anzahl von Einsen haben), und einen für den umgekehrten Fall.

Michael Dorfman
quelle
10
  private int get_bits_set(int v)
    {
      int c; // c accumulates the total bits set in v
        for (c = 0; v>0; c++)
        {
            v &= v - 1; // clear the least significant bit set
        }
        return c;
    }
stacktay
quelle
9

Einige offene Fragen: -

  1. Wenn die Zahl dann negativ ist?
  2. Wenn die Zahl 1024 ist, wird die Methode "iterativ durch 2 teilen" zehnmal wiederholt.

Wir können das Algo so ändern, dass es die negative Zahl wie folgt unterstützt: -

count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
    count += 1
  n /= 2  
return count

Um das zweite Problem zu lösen, können wir das Algo wie folgt schreiben:

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

Vollständige Referenz siehe:

http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html

Baban
quelle
9

Ich denke, die Methode von Brian Kernighan wird auch nützlich sein ... Sie durchläuft so viele Iterationen, wie gesetzte Bits vorhanden sind. Wenn wir also ein 32-Bit-Wort haben, bei dem nur das High-Bit gesetzt ist, wird es nur einmal durch die Schleife gehen.

int countSetBits(unsigned int n) { 
    unsigned int n; // count the number of bits set in n
    unsigned int c; // c accumulates the total bits set in n
    for (c=0;n>0;n=n&(n-1)) c++; 
    return c; 
}

Veröffentlicht 1988, die C-Programmiersprache 2nd Ed. (von Brian W. Kernighan und Dennis M. Ritchie) erwähnt dies in Übung 2-9. Am 19. April 2006 wies mich Don Knuth darauf hin, dass diese Methode "erstmals von Peter Wegner in CACM 3 (1960), 322 veröffentlicht wurde. (Ebenfalls unabhängig von Derrick Lehmer entdeckt und 1964 in einem von Beckenbach herausgegebenen Buch veröffentlicht.)"

Erorr
quelle
8

Ich benutze den folgenden Code, der intuitiver ist.

int countSetBits(int n) {
    return !n ? 0 : 1 + countSetBits(n & (n-1));
}

Logik: n & (n-1) setzt das zuletzt gesetzte Bit von n zurück.

PS: Ich weiß, dass dies keine O (1) -Lösung ist, wenn auch eine interessante Lösung.

Manish Mulani
quelle
Dies ist gut für "spärliche" Zahlen mit einer geringen Anzahl von Bits O(ONE-BITS). Es ist tatsächlich O (1), da es höchstens 32 Ein-Bits gibt.
ealfonso
7

Was meinst du mit "Bester Algorithmus"? Der Kurzschlusscode oder der Fastencode? Ihr Code sieht sehr elegant aus und hat eine konstante Ausführungszeit. Der Code ist auch sehr kurz.

Aber wenn die Geschwindigkeit der Hauptfaktor und nicht die Codegröße ist, kann das Folgende meiner Meinung nach schneller sein:

       static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
        static int bitCountOfByte( int value ){
            return BIT_COUNT[ value & 0xFF ];
        }

        static int bitCountOfInt( int value ){
            return bitCountOfByte( value ) 
                 + bitCountOfByte( value >> 8 ) 
                 + bitCountOfByte( value >> 16 ) 
                 + bitCountOfByte( value >> 24 );
        }

Ich denke, dass dies für einen 64-Bit-Wert nicht schneller sein wird, aber ein 32-Bit-Wert kann schneller sein.

Horcrux7
quelle
Mein Code hat 10 Operationen. Ihr Code hat 12 Operationen. Ihr Link funktioniert mit kleineren Arrays (5). Ich benutze 256 Elemente. Beim Caching kann das ein Problem sein. Wenn Sie es jedoch sehr häufig verwenden, ist dies kein Problem.
Horcrux7
Wie sich herausstellt, ist dieser Ansatz messbar viel schneller als der Bit-Twiddling-Ansatz. Wenn Sie mehr Speicher verwenden, wird weniger Code kompiliert, und diese Verstärkung wird jedes Mal wiederholt, wenn Sie die Funktion einbinden. Es könnte sich also leicht als Nettogewinn herausstellen.
7

Ich habe ungefähr 1990 ein schnelles Bitcount-Makro für RISC-Maschinen geschrieben. Es verwendet keine fortgeschrittene Arithmetik (Multiplikation, Division,%), Speicherabrufe (viel zu langsam), Verzweigungen (viel zu langsam), aber es wird davon ausgegangen, dass die CPU eine hat 32-Bit-Barrel-Shifter (mit anderen Worten, >> 1 und >> 32 benötigen dieselbe Anzahl von Zyklen). Es wird davon ausgegangen, dass kleine Konstanten (wie 6, 12, 24) nichts zum Laden in die Register kosten oder gespeichert werden in Provisorien und immer wieder verwendet.

Mit diesen Annahmen werden auf den meisten RISC-Maschinen 32 Bit in etwa 16 Zyklen / Anweisungen gezählt. Beachten Sie, dass 15 Anweisungen / Zyklen nahe an einer Untergrenze für die Anzahl der Zyklen oder Anweisungen liegen, da anscheinend mindestens 3 Anweisungen (Maske, Verschiebung, Operator) erforderlich sind, um die Anzahl der Addenden zu halbieren, also log_2 (32). = 5, 5 x 3 = 15 Anweisungen sind quasi eine Untergrenze.

#define BitCount(X,Y)           \
                Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
                Y = ((Y + (Y >> 3)) & 030707070707); \
                Y =  (Y + (Y >> 6)); \
                Y = (Y + (Y >> 12) + (Y >> 24)) & 077;

Hier ist ein Geheimnis für den ersten und komplexesten Schritt:

input output
AB    CD             Note
00    00             = AB
01    01             = AB
10    01             = AB - (A >> 1) & 0x1
11    10             = AB - (A >> 1) & 0x1

Wenn ich also die erste Spalte (A) oben nehme, sie 1 Bit nach rechts verschiebe und von AB subtrahiere, erhalte ich die Ausgabe (CD). Die Erweiterung auf 3 Bit ist ähnlich; Sie können es mit einer 8-zeiligen booleschen Tabelle wie meiner oben überprüfen, wenn Sie möchten.

  • Don Gillies
systemBuilder
quelle
7

Wenn Sie C ++ verwenden, können Sie auch die Metaprogrammierung von Vorlagen verwenden:

// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
        // return the least significant bit plus the result of calling ourselves with
        // .. the shifted value
        return (val & 0x1) + countBits<BITS-1>(val >> 1);
}

// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
        return val & 0x1;
}

Verwendung wäre:

// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )

// another byte (this returns 7)
countBits<8>( 254 )

// counting bits in a word/short (this returns 1)
countBits<16>( 256 )

Sie können diese Vorlage natürlich weiter erweitern, um verschiedene Typen zu verwenden (sogar die automatische Erkennung der Bitgröße), aber ich habe sie aus Gründen der Übersichtlichkeit einfach gehalten.

edit: Ich habe vergessen zu erwähnen, dass dies gut ist, da es in jedem C ++ - Compiler funktionieren sollte und Ihre Schleife im Grunde nur für Sie abrollt, wenn ein konstanter Wert für die Bitanzahl verwendet wird (mit anderen Worten, ich bin mir ziemlich sicher, dass dies die schnellste allgemeine Methode ist du wirst es finden)

Pentaphobe
quelle
Leider wird die Bitzählung nicht parallel durchgeführt, daher ist sie wahrscheinlich langsamer. Könnte aber schön machen constexpr.
Imallett
Einverstanden - es war eine lustige Übung in der Rekursion von C ++ - Vorlagen, aber definitiv eine ziemlich naive Lösung.
Pentaphobe
6

Dieses Beispiel aus der Glücksakte gefällt mir besonders gut:

# BITCOUNT (x) definieren (((BX_ (x) + (BX_ (x) >> 4)) & 0x0F0F0F0F)% 255)
# BX_ (x) ((x) - (((x) >> 1) & 0x77777777) definieren
                             - (((x) >> 2) & 0x33333333)
                             - (((x) >> 3) & 0x11111111))

Ich mag es am liebsten, weil es so hübsch ist!

Ross
quelle
1
Wie funktioniert es im Vergleich zu den anderen Vorschlägen?
asdf
6

Java JDK1.5

Integer.bitCount (n);

Dabei ist n die Zahl, deren Einsen gezählt werden sollen.

Überprüfen Sie auch,

Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);

//Beginning with the value 1, rotate left 16 times
     n = 1;
         for (int i = 0; i < 16; i++) {
            n = Integer.rotateLeft(n, 1);
            System.out.println(n);
         }
Rahul
quelle
Nicht wirklich ein Algorithmus, dies ist nur ein Bibliotheksaufruf. Nützlich für Java, nicht so sehr für alle anderen.
Benzado
2
@benzado ist richtig, aber +1 trotzdem, weil einige Java-Entwickler die Methode möglicherweise nicht kennen
finnw
@ Finnw, ich bin einer dieser Entwickler. :)
neevek
6

Ich fand eine Implementierung der Bitzählung in einem Array unter Verwendung von SIMD-Anweisungen (SSSE3 und AVX2). Es hat eine 2-2,5-mal bessere Leistung als wenn es die intrinsische Funktion __popcnt64 verwendet.

SSSE3-Version:

#include <smmintrin.h>
#include <stdint.h>

const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m128i _sum =  _mm128_setzero_si128();
    for (size_t i = 0; i < size; i += 16)
    {
        //load 16-byte vector
        __m128i _src = _mm_loadu_si128((__m128i*)(src + i));
        //get low 4 bit for every byte in vector
        __m128i lo = _mm_and_si128(_src, F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
    }
    uint64_t sum[2];
    _mm_storeu_si128((__m128i*)sum, _sum);
    return sum[0] + sum[1];
}

AVX2-Version:

#include <immintrin.h>
#include <stdint.h>

const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
                                   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);

uint64_t BitCount(const uint8_t * src, size_t size)
{
    __m256i _sum =  _mm256_setzero_si256();
    for (size_t i = 0; i < size; i += 32)
    {
        //load 32-byte vector
        __m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
        //get low 4 bit for every byte in vector
        __m256i lo = _mm256_and_si256(_src, F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
        //get high 4 bit for every byte in vector
        __m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
        //sum precalculated value from T
        _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
    }
    uint64_t sum[4];
    _mm256_storeu_si256((__m256i*)sum, _sum);
    return sum[0] + sum[1] + sum[2] + sum[3];
}
ErmIg
quelle
6

Ich benutze dies immer in Competitive Programming und es ist einfach zu schreiben und effizient:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}
Diugalde
quelle
5

Es gibt viele Algorithmen, um die gesetzten Bits zu zählen. aber ich denke das beste ist das schnellere! Sie können die Details auf dieser Seite sehen:

Bit Twiddling Hacks

Ich schlage vor:

Zählen von Bits in 14-, 24- oder 32-Bit-Wörtern mithilfe von 64-Bit-Anweisungen

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

Diese Methode erfordert eine 64-Bit-CPU mit schneller Modulteilung, um effizient zu sein. Die erste Option benötigt nur 3 Operationen. Die zweite Option dauert 10; und die dritte Option dauert 15.

Mostafa
quelle
5

Schnelle C # -Lösung unter Verwendung einer vorberechneten Tabelle der Bytebitanzahl mit Verzweigung nach Eingabegröße.

public static class BitCount
{
    public static uint GetSetBitsCount(uint n)
    {
        var counts = BYTE_BIT_COUNTS;
        return n <= 0xff ? counts[n]
             : n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
             : n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
             : counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
    }

    public static readonly uint[] BYTE_BIT_COUNTS = 
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };
}
Dadhi
quelle
Ironischerweise könnte diese Tabelle von jedem der in diesem Thread veröffentlichten Algorithmen erstellt worden sein! Die Verwendung solcher Tabellen bedeutet jedoch eine zeitlich konstante Leistung. Wenn Sie noch einen Schritt weiter gehen und eine 64K-Übersetzungstabelle erstellen, halbieren Sie daher die erforderlichen Operationen AND, SHIFT und ADD. Ein interessantes Thema für Bitmanipulatoren!
user924272
Größere Tabellen können aufgrund von Cache-Problemen langsamer (und nicht zeitkonstant) sein. Sie können 3 Bits gleichzeitig (0xe994 >>(k*2))&3
nachschlagen
5

Hier ist ein tragbares Modul (ANSI-C), das jeden Ihrer Algorithmen auf jeder Architektur vergleichen kann.

Ihre CPU hat 9 Bit Bytes? Kein Problem :-) Im Moment werden 2 Algorithmen implementiert, der K & R-Algorithmus und eine byteweise Nachschlagetabelle. Die Nachschlagetabelle ist im Durchschnitt dreimal schneller als der K & R-Algorithmus. Wenn jemand einen Weg finden kann, den "Hacker's Delight" -Algorithmus portabel zu machen, können Sie ihn gerne hinzufügen.

#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_

/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );

/* List of available bitcount algorithms.  
 * onTheFly:    Calculate the bitcount on demand.
 *
 * lookupTalbe: Uses a small lookup table to determine the bitcount.  This
 * method is on average 3 times as fast as onTheFly, but incurs a small
 * upfront cost to initialize the lookup table on the first call.
 *
 * strategyCount is just a placeholder. 
 */
enum strategy { onTheFly, lookupTable, strategyCount };

/* String represenations of the algorithm names */
extern const char *strategyNames[];

/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );

#endif

.

#include <limits.h>

#include "bitcount.h"

/* The number of entries needed in the table is equal to the number of unique
 * values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;

static int _defaultBitCount( unsigned int val ) {
    int count;

    /* Starting with:
     * 1100 - 1 == 1011,  1100 & 1011 == 1000
     * 1000 - 1 == 0111,  1000 & 0111 == 0000
     */
    for ( count = 0; val; ++count )
        val &= val - 1;

    return count;
}

/* Looks up each byte of the integer in a lookup table.
 *
 * The first time the function is called it initializes the lookup table.
 */
static int _tableBitCount( unsigned int val ) {
    int bCount = 0;

    if ( !_lookupTableInitialized ) {
        unsigned int i;
        for ( i = 0; i != UCHAR_MAX + 1; ++i )
            _bitCountTable[i] =
                ( unsigned char )_defaultBitCount( i );

        _lookupTableInitialized = 1;
    }

    for ( ; val; val >>= CHAR_BIT )
        bCount += _bitCountTable[val & UCHAR_MAX];

    return bCount;
}

static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;

const char *strategyNames[] = { "onTheFly", "lookupTable" };

void setStrategy( enum strategy s ) {
    switch ( s ) {
    case onTheFly:
        _bitcount = _defaultBitCount;
        break;
    case lookupTable:
        _bitcount = _tableBitCount;
        break;
    case strategyCount:
        break;
    }
}

/* Just a forwarding function which will call whichever version of the
 * algorithm has been selected by the client 
 */
int bitcount( unsigned int val ) {
    return _bitcount( val );
}

#ifdef _BITCOUNT_EXE_

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Use the same sequence of pseudo random numbers to benmark each Hamming
 * Weight algorithm.
 */
void benchmark( int reps ) {
    clock_t start, stop;
    int i, j;
    static const int iterations = 1000000;

    for ( j = 0; j != strategyCount; ++j ) {
        setStrategy( j );

        srand( 257 );

        start = clock(  );

        for ( i = 0; i != reps * iterations; ++i )
            bitcount( rand(  ) );

        stop = clock(  );

        printf
            ( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
              reps * iterations, strategyNames[j],
              ( double )( stop - start ) / CLOCKS_PER_SEC );
    }
}

int main( void ) {
    int option;

    while ( 1 ) {
        printf( "Menu Options\n"
            "\t1.\tPrint the Hamming Weight of an Integer\n"
            "\t2.\tBenchmark Hamming Weight implementations\n"
            "\t3.\tExit ( or cntl-d )\n\n\t" );

        if ( scanf( "%d", &option ) == EOF )
            break;

        switch ( option ) {
        case 1:
            printf( "Please enter the integer: " );
            if ( scanf( "%d", &option ) != EOF )
                printf
                    ( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
                      option, option, bitcount( option ) );
            break;
        case 2:
            printf
                ( "Please select number of reps ( in millions ): " );
            if ( scanf( "%d", &option ) != EOF )
                benchmark( option );
            break;
        case 3:
            goto EXIT;
            break;
        default:
            printf( "Invalid option\n" );
        }

    }

 EXIT:
    printf( "\n" );

    return 0;
}

#endif
Robert S. Barnes
quelle
1
Ich mag Ihren Plug-in-Ansatz, den polymorphen Ansatz, sowie den Schalter, der als wiederverwendbare Bibliothek oder eigenständige ausführbare Testdatei erstellt werden soll, sehr. Sehr gut durchdacht =)
5

Was Sie tun können, ist

while(n){
    n=n&(n-1);
    count++;
}

Die Logik dahinter ist, dass die Bits von n-1 vom am weitesten rechts gesetzten Bit von n invertiert werden. Wenn n = 6, dh 110, dann ist 5 101, werden die Bits vom am weitesten rechts gesetzten Bit von n invertiert. Wenn wir und diese beiden also das Bit ganz rechts in jeder Iteration machen und immer zum nächsten ganz rechts gesetzten Bit gehen. Zählen Sie daher das gesetzte Bit. Die schlechteste Zeitkomplexität ist O (logn), wenn jedes Bit gesetzt ist.

Varun Gusain
quelle