Der einfachste und naivste Weg besteht darin, einfach über die Bits zu iterieren und zu zählen:
%Vor%Es gibt jede Menge besserer (für verschiedene Werte von "besser") Möglichkeiten, aber das ist ziemlich klar, sehr knapp (Code-weise), und erfordert nicht eine Menge Setup.
Eine Mikrooptimierung, die als eine Verbesserung angesehen werden kann, besteht darin, die Maske nicht zum Testen jedes Bits zu berechnen, sondern den Wert zu verschieben und immer das Bit ganz rechts zu testen:
%Vor%Wenn Sie Effizienz wollen, dann gibt es eine gute Umsetzung in dem Buch "Hackers Delight"
22 Anweisungen verzweigen frei.
%Vor%Ich werde versuchen zu erklären, wie es funktioniert. Es ist ein Divide-and-Conquer-Algorithmus.
%Vor%Verschiebt alle Bits 1 Schritt nach rechts und nimmt das niedrigstwertige Bit jedes Bitpaars.
%Vor%Sie haben also im Grunde die folgende Tabelle mit allen 2 Bit-Permutationen.
%Vor%Dann subtrahierst du diese von den nicht verschobenen Paaren.
%Vor%Also haben wir jetzt jedes 2-Bit-Paar so geändert, dass ihr Wert jetzt die Anzahl der Bits ihrer entsprechenden ursprünglichen 2-Bit-Paare ist ... und dann fahren wir in ähnlicher Weise mit 4-Bit-Gruppen, 8-Bit-Gruppen, 16 Bit fort Gruppen und letzten 32 Bit.
Wenn Sie eine bessere Erklärung wollen, kaufen Sie das Buch, es gibt viele gute Erklärungen und Diskussionen über alternative Algorithmen usw. ...
Wenn Sie GCC verwenden, können Sie integrierte Funktionen ausprobieren:
%Vor%Siehe GCC-Dokumentation für Details.
Kernighan-Weg zum Zählen der gesetzten Bits
%Vor%Kann für die gegebene Aufgabe leicht angepasst werden. Eine Anzahl von Iterationen ist hier gleich einer Anzahl von gesetzten Bits.
Ich empfehle auch den obigen Link für verschiedene andere Möglichkeiten, um diese und andere Arten bitbezogener Aufgaben zu lösen. Es gibt auch ein Ein-Zeilen-Beispiel zum Erhalten einer Bitzahl, die in Makros implementiert ist.
Es gibt ein tolles Buch für diese Art von Sachen: Hacker's Delight (ja, der Name saugt: es hat nichts mit Sicherheit zu tun, sondern ausschließlich Bit-Twiddling). Es bietet mehrere Algorithmen zum Zählen von "1" Bits, die besten können auch hier gefunden werden (obwohl die Buch hat Erklärungen, die diese Website nicht hat).
Sobald Sie die Anzahl der Bits '1' kennen, subtrahieren Sie sie einfach von der Anzahl der Bits in Ihrer Typendarstellung.
Ich bin überrascht, dass niemand diesen erwähnt hat:
%Vor% Dies gibt die Anzahl der Null-Bits in num bei Verwendung mit GCC an.
Machen Sie ein Kompliment und zählen Sie die 1s.
count_zero_bits (x) = count_one_bits (~ x);
Implementieren Sie den Code, um die Einsen zu zählen.
%Vor%obwohl es ein Problem mit meiner Funktion gibt, wenn i eine negative Zahl ist, weil & gt; & gt; setzt 1 Bits auf die rechte Seite, so dass Sie eine Schleife mit nie enden- der Schleife erhalten. Wenn es eine Vorlagenvorlage gibt, die einen vorzeichenlosen Typ erzwingt, der ideal wäre.
Sobald Sie das dann haben:
%Vor%funktioniert.
Erweitern Sie die Antwort von Ronag, die von anderen Benutzern erwähnt wurde, führt zu falschen Ergebnissen (sein Algorithmus funktioniert nur bis zu einem Wert von x = 15), hier ist eine aktualisierte Version des Algorithmus:
%Vor%Die Erklärung der ersten Zeile von Ronag ist korrekt, die übrigen Zeilen verwenden jedoch einen anderen Ansatz. In der ersten Zeile wird durch das Verschieben und Subtrahieren jedes 2-Bit-Paar die Anzahl der Bits enthalten, die in diesem Paar in der ursprünglichen Zahl gesetzt wurden. Der Rest der Zeilen faltet rekursiv diese Zahlen zusammen, indem der LSB jeder 2-n-Bit-Gruppe zu dem MSB dieses Paars addiert wird, das um n verschoben ist, so dass die 2n-Bit-Gruppe die Anzahl der Bits enthält, die in dieser Gruppe gesetzt wurden Originalnummer:
%Vor%Der obige Algorithmus funktioniert für 32-Bit-Ganzzahlen, kann aber leicht angepasst werden, indem die Konstanten auf die korrekte Bitlänge geändert werden, so dass das Muster gleich bleibt (zB 0x5555 ... = 0101 ..., 0x0f0f ... = 00001111 ... etc.) und Hinzufügen / Entfernen der entsprechenden Schichten