Frage Wie zähle ich die Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl?


8 Bits, die die Zahl 7 darstellen, sehen so aus:

00000111

Drei Bits sind gesetzt.

Was sind Algorithmen zur Bestimmung der Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl?


751


Ursprung


Antworten:


Dies ist bekannt alsHamming Gewicht',' Popcount 'oder' Seitwärtsaddition '.

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

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's popcnt, auf CPUs, wo es unterstützt wird) wird mit ziemlicher Sicherheit am schnellsten sein. Einige andere Architekturen können einen langsamen Befehl haben, der mit einer mikrocodierten Schleife implementiert ist, die ein Bit pro Zyklus testet (Zitat benötigt).

Eine vorbelegte 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 aufgrund der Kosten eines "Cache-Fehltreffers" leiden, bei dem die CPU einen Teil der Tabelle aus dem Hauptspeicher holen muss.

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

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, Sie müssen es möglicherweise anpassen, um für eine bestimmte Sprache zu arbeiten (z. B. mit uint32_t für C ++ und >>> in Java):

int numberOfSetBits(int i)
{
     // Java: 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;
}

Dies hat das beste Worst-Case-Verhalten eines der besprochenen Algorithmen und wird daher effizient mit jedem Verwendungsmuster oder den Werten umgehen, die Sie darauf werfen.


Dieser bitweise SWAR-Algorithmus könnte parallelisiert werden, um in mehreren Vektorelementen gleichzeitig statt in einem einzigen Ganzzahlregister für eine Beschleunigung auf CPUs mit SIMD, aber ohne brauchbaren Popcount-Befehl, ausgeführt zu werden. (z. B. x86-64-Code, der auf jeder CPU ausgeführt werden muss, nicht nur Nehalem oder später.)

Der beste Weg, Vektorbefehle für den Popcount zu verwenden, besteht jedoch normalerweise darin, einen Variablen-Shuffle zu verwenden, um eine Tabellensuche für 4 Bits gleichzeitig mit jedem Byte durchzuführen. (Die 4 Bits indizieren eine Tabelle mit 16 Einträgen, die in einem Vektorregister gehalten wird).

Auf Intel-CPUs kann die Hardware-64-Bit-popcnt-Anweisung eine Leistung übertreffen SSSE3 PSHUFB bitparallele Implementierung um etwa einen Faktor von 2, aber nur wenn dein Compiler es richtig macht. Sonst kann SSE deutlich nach vorne kommen. Neuere Compilerversionen kennen die popcnt falsche Abhängigkeit  Problem bei Intel.

Verweise:

https://graphics.stanford.edu/~seander/bithacks.html

https://en.wikipedia.org/wiki/Hamming_weight

http://gurmeet.net/puzzles/fast-bit-counting-routinen/

http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)


764



Beachten Sie auch die integrierten Funktionen Ihrer Compiler.

Auf dem GNU-Compiler zum Beispiel können Sie einfach verwenden:

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

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

Die GCC-Intrinsics arbeiten sogar über mehrere Plattformen hinweg. Popcount wird in der x86-Architektur zum Mainstream werden, so dass es sinnvoll ist, jetzt das intrinsische zu verwenden. Andere Architekturen haben den Popcount seit Jahren.


Auf x86 können Sie dem Compiler mitteilen, dass er Unterstützung annehmen kann popcnt Anleitung mit -mpopcnt oder -msse4.2 um auch die Vektorbefehle zu aktivieren, die in derselben Generation hinzugefügt wurden. Sehen GCC x86-Optionen. -march=nehalem (oder -march= Welche CPU auch immer Ihr Code annehmen und einstellen sollte, könnte eine gute Wahl sein. Das Ausführen der resultierenden Binärdatei auf einer älteren CPU führt zu einem ungültigen Befehlsfehler.

Verwenden Sie, um Binärdateien zu optimieren, die für die Maschine optimiert sind, auf der Sie sie erstellen -march=native  (mit gcc, klingeln oder ICC).

MSVC bietet eine intrinsische für das x86 popcnt Anweisung, aber im Gegensatz zu GCC ist es wirklich ein intrinsischer für den Hardware-Befehl und erfordert Hardware-Unterstützung.


Verwenden std::bitset<>::count() anstelle von einem eingebauten

In der Theorie sollte jeder Compiler, der weiß, wie man für die Ziel-CPU effizient pokommiert, diese Funktionalität durch ISO C ++ verfügbar machen std::bitset<>. In der Praxis könnte es für einige Ziel-CPUs in einigen Fällen besser sein, den Bit-Hack AND / shift / ADD zu verwenden.

Für Zielarchitekturen, bei denen Hardware-Popcount eine optionale Erweiterung ist (wie x86), haben nicht alle Compiler ein std::bitset das nutzt es aus, wenn es verfügbar ist. Zum Beispiel hat MSVC keine Möglichkeit zu aktivieren popcnt Unterstützung zur Kompilierzeit und immer verwendet eine Tabellensuche, sogar mit /Ox /arch:AVX (was SSE4.2 impliziert, obwohl es technisch ein separates Feature Bit für popcnt.)

Aber zumindest bekommt man etwas Portables, das überall funktioniert, und mit gcc / clang mit den richtigen Zieloptionen erhält man Hardware-Popcount für Architekturen, die es 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();
}

Sehen asm von gcc, clang, icc und MSVC auf dem Godbolt Compiler Explorer.

x86-64 gcc -O3 -std=gnu++11 -mpopcnt gibt dies 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++11 emittiert (für die int arg Version):

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

Diese Quelle ist nicht x86-spezifisch oder GNU-spezifisch, sondern kompiliert nur gut für x86 mit gcc / clang / icc.

Beachten Sie auch, dass gcc's Fallback für Architekturen ohne Einzelanweisungs-Popcount eine byteweise Suche nach Tabellen ist. Das ist nicht wunderbar zum Beispiel für ARM.


185



Meiner Meinung nach ist die "beste" Lösung diejenige, die von einem anderen Programmierer (oder dem ursprünglichen Programmierer zwei Jahre später) ohne umfangreiche Kommentare gelesen werden kann. Du magst vielleicht die schnellste oder cleverste Lösung, die einige bereits zur Verfügung gestellt haben, aber ich bevorzuge Lesbarkeit gegenüber Klugheit jederzeit.

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 es gut dokumentieren, um Ihren Nachfolgern zu helfen), könnten 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 bestimmte Datentypen angewiesen sind, 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, bleibe ich bei der lesbaren Lösung.


168



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;
}

Führt in ~ 20-ish-Anweisungen aus (bogenabhängig), keine Verzweigung.

Hacker Freude  ist herrlich! Sehr empfehlenswert.


94



Ich denke der schnellste Weg - ohne Nachschlagetabellen und Popcount-ist das 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;
}

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

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

Die Anzahl der Bits in zwei Bits kann sein 0b00, 0b01 oder 0b10. Lasst uns versuchen, das auf 2 Bits auszuarbeiten.

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

Dies wurde benötigt: Die letzte Spalte zeigt die Anzahl der gesetzten Bits in jedem Zwei-Bit-Paar. Wenn die zwei Bit-Nummer ist >= 2 (0b10) dann and produziert 0b01sonst produziert 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 je zwei Bits, jetzt fassen wir diese Zählung in allen 4 Bits zusammen.

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

Wir addieren dann das obige Ergebnis und geben uns die Gesamtzahl der gesetzten Bits in 4 Bits. Die letzte Aussage ist am schwierigsten.

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

Lass es uns weiter brechen ...

v + (v >> 4)

Es ist ähnlich wie die zweite Aussage; Wir zählen stattdessen die gesetzten Bits in Gruppen von 4. Wir wissen - aufgrund unserer früheren Operationen - dass jedes Nibble die Anzahl der gesetzten Bits enthält. Schauen wir uns ein Beispiel an. Angenommen, wir haben das Byte 0b01000010. Es bedeutet, dass das erste Nibble seine 4 Bits gesetzt hat und das zweite hat seine 2 Bits gesetzt. Jetzt fügen wir diese Nibbles zusammen.

0b01000010 + 0b01000000

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

0b01100010 & 0xF0 = 0b01100000

Jetzt hat jedes Byte die Anzahl der gesetzten Bits darin. Wir müssen sie alle zusammen addieren. Der Trick besteht darin, das Ergebnis zu multiplizieren 0b10101010 Das hat eine interessante Eigenschaft. Wenn unsere Nummer vier Bytes hat, A B C DEs wird eine neue Zahl mit diesen Bytes ergeben A+B+C+D B+C+D C+D D. Eine 4-Byte-Zahl kann maximal 32 Bit gesetzt haben, die als dargestellt werden können 0b00100000.

Alles, was wir jetzt brauchen, ist das erste Byte, das die Summe aller gesetzten Bits in allen Bytes hat, und wir bekommen es durch >> 24. Dieser Algorithmus wurde entwickelt für 32 bit Wörter aber können leicht für geändert werden 64 bit Wörter.


69



Mir wurde langweilig, und ich plante eine Milliarde Wiederholungen von drei Ansätzen. Compiler ist gcc -O3. CPU ist was auch immer sie in das 1. Gen Macbook Pro stecken.

Am schnellsten ist Folgendes mit 3,7 Sekunden:

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 den gleichen Code, aber nach 4 Bytes anstatt 2 Halbworten. Das dauerte etwa 5,5 Sekunden.

Der dritte Platz geht an den Bit-Twiddling-Ansatz "Seitwärtszugabe", der 8,6 Sekunden dauerte.

Der vierte Platz geht an GCC's __builtin_popcount (), zu schändlichen 11 Sekunden.

Das Ein-Bit-auf-zu-einem-Mal-Herannahen war langsamer und mir war es langweilig, darauf zu warten, dass es fertig war.

Wenn Sie also vor allem Wert auf Leistung legen, verwenden Sie den ersten Ansatz. Wenn Sie möchten, aber nicht genug, um 64 KB RAM darauf auszugeben, verwenden Sie den zweiten Ansatz. Ansonsten verwenden Sie den lesbaren (aber langsamen) Ein-Bit-auf-Mal-Ansatz.

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

Bearbeiten: Ähnliche Ergebnisse Hier.


53



Wenn Sie Java verwenden, die integrierte Methode Integer.bitCount wird das machen.


52



Dies ist eine dieser Fragen, bei der es hilfreich ist, Ihre Mikroarchitektur zu kennen. Ich habe gerade zwei Varianten unter gcc 4.3.3 mit -O3 kompiliert mit C ++ Inlines, um Function Call Overhead, eine Milliarde Iterationen zu beseitigen, die laufende Summe aller Zählungen zu halten, um sicherzustellen, dass der Compiler nichts Wichtiges entfernt, mit rdtsc für Timing ( Taktzyklus präzise).

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 & gt; 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);
    Rückgabe (x + y) & 0x000000FF;
}

Das unmodifizierte Hacker's Delight benötigte 12,2 Gigacycles. Meine parallele Version (zählt doppelt so viele Bits) läuft in 13.0 Gigacycles. Bei einem 2,4 GHz Core Duo sind insgesamt 10,5 Sekunden vergangen. 25 Gigacycles = etwas mehr als 10 Sekunden bei dieser Taktfrequenz, also bin ich zuversichtlich, dass meine Timings richtig sind.

Dies hat mit Befehlsabhängigkeitsketten zu tun, die für diesen Algorithmus sehr schlecht sind. Ich könnte die Geschwindigkeit wieder fast verdoppeln, indem ich ein Paar 64-Bit-Register verwende. In der Tat, wenn ich schlau wäre und etwas schneller ein X + y hinzufügen würde, könnte ich einige Schichten abtragen. Die 64-Bit-Version mit einigen kleinen Tweaks würde über even hinauskommen, aber doppelt so viele Bits zählen.

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

Es gibt keinen Grund dafür, dass der Code besonders transparent ist. Die Schnittstelle ist einfach, der Algorithmus kann an vielen Stellen online referenziert werden, und es ist einem umfassenden Komponententest zugänglich. Der Programmierer, der darüber stolpert, könnte sogar etwas lernen. Diese Bitoperationen sind auf Maschinenebene sehr natürlich.

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

inline int pop2 (vorzeichenloses langes x, unsigniertes langes y)
{
    x = x - ((x> 1) & 0x5555555555555555);
    y = y - ((y >> 1) & 0x5555555555555555);
    x = (x & 0x333333333333333) + ((x> 2) & 0x3333333333333333);
    y = (y & 0x333333333333333) + ((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);
    Rückgabe x & 0xFF;
}

Das sieht gut aus (ich teste das aber nicht sorgfältig). Jetzt kommen die Timings bei 10.70 Gigacycles / 14,1 Gigacycles heraus. Diese spätere Zahl summierte 128 Milliarden Bits und entspricht 5,9 s, die auf dieser Maschine verstrichen waren. Die nichtparallele Version beschleunigt ein kleines bisschen, weil ich im 64-Bit-Modus laufe und 64-Bit-Register etwas besser mag als 32-Bit-Register.

Mal sehen, ob hier noch etwas mehr Pipelining zu haben ist. Das war ein bisschen komplizierter, also habe ich ein bisschen getestet. Jeder Ausdruck allein ergibt 64, alle zusammen 256.

inline int pop4 (vorzeichenloses langes x, vorzeichenloses langes y,
                unsigned long u, unsigned long v)
{
  enum {m1 = 0x5555555555555555,
         m2 = 0x3333333333333333,
         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 & m²) + ((y & gt; 2) & m²);
    u = (u & m²) + ((u & supmin; ²) & m²);
    v = (v und 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);
    Rückgabe x & 0x000001FF;
}

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

   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);
   hitime e4 = rdtsc ();

256 Milliarden Bits summiert in 8.17s vergangen. Funktioniert mit 1,02s für 32 Millionen Bits, wie in der 16-Bit-Tabelle nachgeschlagen wird. Kann nicht direkt vergleichen, weil die andere Bank keine Taktrate gibt, aber es sieht so aus, als hätte ich die Rotte aus der 64KB-Tabellenausgabe geknallt, was eine tragische Verwendung von L1-Cache an erster Stelle ist.

Update: Entschlossen, das Offensichtliche zu tun und pop6 () durch Hinzufügen von vier weiteren duplizierten Zeilen zu erstellen. Auf 22,8 gc kam es zu 384 Milliarden Bits, die in 9,5 Sekunden summiert wurden. Also gibt es noch 20% Jetzt bei 800ms für 32 Milliarden Bits.


28



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 im Binärformat), so funktioniert der Algorithmus folgendermaßen (jedes Mal, wenn zwei benachbarte Blö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)
+-------------------------------+

28



Warum nicht iterativ durch 2 dividieren?

Anzahl = 0
während n> 0 ist
  wenn (n% 2) == 1
    Zähle + = 1
  n / = 2

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


23



Für ein fröhliches Medium zwischen 232 Nachschlagetabelle und Iteration durch jedes Bit einzeln:

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://ctipps.pbwiki.com/CountBits


19