Anzahl der Nullen in der Binärdarstellung eines Integer

Question

Mögliche Duplizieren:
Best algorithm to count the number of set bits in a 32-bit integer?

Bei einer 32-Bit-Ganzzahl N, einen Algorithmus entwickeln, um die Anzahl der Nullen in dem binären Bit zu finden, Darstellung von N.

der einfachste Algorithmus, den ich denken kann, ist die binäre Darstellung für Zeros, in C, so etwas zu überprüfen:

int num_of_zero(int num) 
{ 
    if(0 == num) return 1; /*For the input 0 it should output 1 */ 
    int Count = 0; 
    while(num>0){ 
    if(0 == (num&1)) Count++; 
    num >>= 1; 
} 
return Count; 
} 

Ich war wandern, wenn es einen Algorithmus gibt, um zu konstanter Zeit zu berechnen.

Für den Eingang sollte es 1 nicht 32 zurückgeben.

Für sollte der Ausgang 1 sein. Als binäre Darstellung ist .

Für der Ausgang 0.

genau sein soll, Suche nach einem besseren Algorithmus Anzahl (nichtvoreilender) Nullen in der binären Interpretation eines 32-Bit-integer.Hope das Problem zu berechnen, ist jetzt klar.

Bearbeiten: Wie Alex Martelli, Delroth wies ich meinen Code, um es lesbarer & mit Iteration dieses Mal ändern.

Answer 1

Der einfache Weg, dies zu tun ist, über jedes Bit der Binärdarstellung der Zahl zu iterieren, den Wert jedes Bits zu testen und zu zählen, wie viele von ihnen Null sind. Eine Schleife wäre dafür viel klarer als eine Rekursion.

Es gibt jedoch viele weitere optimierte Methoden dafür. Sie können einige der besseren in Antworten auf diese Frage finden, "Best algorithm to count the number of set bits in a 32-bit integer" (natürlich ist die Anzahl der Null-Bits die Anzahl der gesetzten Bits von der Gesamtzahl der Bits subtrahiert).

Answer 2

Es ist nicht wirklich eine Antwort auf Ihre wichtigste Frage, aber Sie sollten Ihre rekursive Funktion wie folgt umschreiben:

int num_of_zero(int num) 
{ 
    int left_part_zeros; 

    if (num == 0) 
     return 0; 

    left_part_zeros = num_of_zero(num >> 1); 
    if ((num & 1) == 0) 
     return left_part_zeros + 1; 
    else 
     return left_part_zeros; 
} 

Ihre Implementierung eine Menge Probleme haben, neben vollständig unlesbar zu sein.

Answer 3

Schnelle und dumme Art - es gibt exotischere Implementierungen in der Duplikatsfrage, aber ich habe etwas Ähnliches verwendet, ohne in der Vergangenheit viele negative Auswirkungen zu haben.

Wir verwenden hier eine Tabelle mit Nibbles, um die Anzahl der Wiederholungen der Schleife zu reduzieren - wenn Sie eine Bootsladung dieser Berechnungen durchführen, könnte es effizienter sein, ein viel größeres Array zu erstellen, sagen wir Byte-Ebene, schneidet die Schleife in zwei Hälften.

/* How many bits are set in every possible nibble. */ 
static size_t BIT_TABLE[] = { 
    0, 1, 1, 2,  /* 0, 1, 2, 3 */ 
    1, 2, 2, 3,  /* 4, 5, 6, 7 */ 
    1, 2, 2, 3,  /* 8, 9, A, B */ 
    2, 3, 3, 4  /* C, D, E, F */ 
}; 

size_t num_of_bits(int num) { 
    /* Little reworking could probably shrink the stack space in use here. */ 
    size_t ret = 0, i; 
    register int work = num; 

    /* Iterate every nibble, rotating the integer in place. */ 
    for(i = 0; i < (sizeof(num) * 2); i++) { 
     /* Pointer math to get a member of the static array. */ 
     ret += *(BIT_TABLE + (work & 0xF)); 
     work >>= 4; 
    } 
    return ret; 
} 

Answer 4

Rekursion ist auf jeden Fall viel des Guten - und außerdem ziemlich Buggy Ihres Code (es wird keine der führenden Nullen von num zählen !!!).Eine einfache Iteration, wie zum Beispiel:

int num_of_zero(int num) { 
    unsigned int unum = (unsigned int)num; 
    int count; 
    int i; 

    for(i = 0; i < 32; ++i) { 
    if(!(unum & 1)) ++count; 
    unum >>= 1; 
    } 
    return count; 
} 

ist richtig und schneller (kann prägnant codiert werden wird, aber ich denke, das ist der deutlichste Ausdruck ist).

Wenn Sie diese Berechnung viele Male durchführen müssen, überlegen Sie, ein Array von (sagen wir) 256 "Zählern von Nullen" vorberechnen (jeder Wert gibt die Anzahl für seinen Index, einschließlich 0 bis 255, als 8-Bit-Nummer) . Dann können Sie nur 4-mal Schleifen (maskieren und Verschieben von 8 Bits auf einmal), und leicht die Schleife ausrollen - wenn Ihr Compiler ist nicht schlau genug, es in Ihrem Namen zu tun ;-).

Answer 5

Es gibt eine große Ressource online genannt Bit Twiddling Hacks, die alle Arten von großen kleinen C-Tricks enthält. Sie sind möglicherweise besonders interessiert an der Counting bits set Abschnitt.

Answer 6

Ich vermute, dass dies eine Hausaufgabe ist. Kein Problem! Hier ist die schnellstmögliche Lösung (nach langen Anlaufkosten):

Machen Sie ein Array von byte das ist 2 lang. Berechnen Sie den Wert der Anzahl der Nullen in der Binärdarstellung für jeden möglichen int Wert, um dieses Array auszufüllen. Von nun an haben Sie ein Array, das Ihnen die Anzahl der Nullen pro Wert gibt.

Ja, diese Lösung ist dumm - es ist viel Arbeit für wenig Gewinn - aber mit einer anderen Idee kombinieren:

Was passiert, wenn Sie nur die Werte vorauszuberechnen, die lange 8 Bits sind? Wären Sie in der Lage, Code zu schreiben, der, obwohl nicht ganz so schnell, immer noch die Anzahl von 0-Bits in einem int zurückgeben würde?

Was passiert, wenn Sie nur die Werte vorberechnen, die 4 Bits lang sind? 2 Bits lang? 1 Bit lang?

Ich hoffe, das gibt Ihnen Ideen für eine bessere algorthm ...

Answer 7

Der einfachste Weg, ich war fand es auf etwas zu stützen, dass die, die zählt dann einfach abziehen, dass von 32 (unter der Annahme, dass Sie sicher sind, die int Größe ist 32 Bits).

int numberOfOnes (int num) { 
    int count = 0; 
    unsigned int u = (unsigned int)num; 
    while (u != 0) { 
     if ((u&1) == 1) 
      count++; 
     u >>= 1; 
    } 
    return count; 
} 
int numberOfZeros (int num) { 
    return 32 - numberOfOnes (num); 
} 

Dies gibt Ihnen eigentlich beide Varianten (Einsen und Nullen) - es gibt schnellere Wege, es zu tun, aber ich würde sie nicht der Ansicht, es sei denn und bis Sie wissen, es ist ein Performance-Problem. Ich tendiere dazu, zuerst die Lesbarkeit zu kodieren.

Sie auch zumindest möchten die Möglichkeit prüfen, dass eine Lookup-Tabelle schneller sein könnte (die oberste Direktive der Optimierung Maßnahme ist, nicht erraten!

Eine Möglichkeit gibt die numberOfOnes Funktion ersetzt werden könnte, mit etwas, das eine nybble zu einem Zeitpunkt arbeitet.

int numberOfOnes (int num) { 
    static const count[] = { 
     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 
    }; 
    int retval = 0; 
    unsigned int u = (unsigned int)num; 
    while (u != 0) { 
     retval += count[u & 0x0f] 
     u >>= 4; 
    } 
    return retval; 
}