Count-Bits in der Anzahl [Duplicate]

Question

Duplizieren:

  

Beste Algorithmus, um die Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl zu zählen?

---

Angenommen, Sie eine Nummer haben. Gibt es eine Möglichkeit, die Bits zu zählen, die in binärer Darstellung dieser Zahl gleich 1, unter Verwendung von nicht-Iteration? Ich meine, ist es eine Möglichkeit, es in konstanter Zeit mit einigen Bit-Operatoren und Masken zu tun. Ich brauche Lösung, die sowohl gut für 32-Bit-Architekturen und 64-Bit arbeiten. Ah fast vergessen, ich brauche es für Sprache C oder Assembler ist auch gut.

Answer 1

Es ist ein bisschen zu zählen Algorithmus ohne eine Schleife unter http: //graphics.stanford. edu / ~ seander / bithacks.html . Viele Bitzählweise Algorithmen unter http: //gurmeetsingh.wordpress .com / 2008/08/05 / Fast-Bit-Zählung-Routinen /

Answer 2

Nun, natürlich gibt es, aber du bist es nicht gehen zu wollen.

Sie könnten natürlich, bauen mit all den richtigen Werten in einer Lookup-Tabelle:

Tabelle [1] = 1, Tabelle [2] = 1, Tabelle [3] = 2, etc.

Also, das würde Sie eine wirklich schnell Antwort, aber es ist eine völlig nutzlos Lösung von selbst, da die Tabelle sehr sein müßte, sehr groß ist.

Sie könnte dies ein wenig optimieren, aber es erfordert nur ein wenig Iteration. eine 8-Bit-Version der Tabelle Lösung, eine bloße 256-Eintragstabelle, dann iterieren jedes Byte im Wert geprüft werden, summiert die Ergebnisse der Tabellensuche einfach erstellen. So etwas wie:

short int tableLookup[256] = { 0, 1, 1, 2, 1, ... };
unsigned int valueToCheck = 89392491;
int result = 0;
while ( valueToCheck != 0 ) {
   result += tableLookup[ (valueToCheck & 0xFF) ];
   valueToCheck >>= 8;
}
// result should now have the correct bit count, if the table is correct.

Hmm, scheint dies gut bekannt ist (und hier wurde ich dies die Spitze von meinem Kopf zu tun off): http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Answer 3

Ja, können Sie tun, dass eine nachschlagen .