Wie zähle ich die Anzahl der null-bits in einem integer?

Die einfachste, die meisten naive Weg ist das iterieren über die bits und zählen:

size_t num_zeroes = 0;

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i)
{
  if ((value & (1 << i)) == 0)
    ++num_zeroes;
}

Dort sind alle Nummer besser (für verschiedene Werte von "besser") Weise, das ist aber ganz klar, sehr knappe (code-Weise), und nicht ein Haufen von setup.

Einer Mikro-Optimierung, die betrachtet werden könnte, eine Verbesserung ist nicht zu berechnen, die Maske zu testen, jedes bit, statt shift den Wert und testen Sie immer das bit ganz rechts:

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i, value >>= 1)
{
  if ((value & 1) == 0)
    ++num_zeroes;
}

InformationsquelleAutor unwind

Können Sie tun 32 minus die Anzahl der gesetzten bits.

InformationsquelleAutor Goz

Kernighan Weg der Zählung der bits, die

unsigned int v; //count the number of bits set in v
unsigned int c; //c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; //clear the least significant bit set
}

Kann leicht angepasst werden, für die Aufgabe gegeben. Eine Anzahl von Iterationen hier ist gleich einer Anzahl von bits festgelegt.

Ich empfehle auch den link oben für verschiedene andere Möglichkeiten, dies zu lösen und andere Arten von bit-bezogenen Aufgaben. Es gibt auch eine single line Beispiel für den Erhalt bit-count implementiert Makros.

InformationsquelleAutor Basilevs

Es ist ein tolles Buch für diese Art von Sachen : Hacker ' s Delight (ja, der name ist beschissen : es hat nichts mit Sicherheit zu tun, sondern ausschließlich bit-twiddling). Es bietet mehrere algorithmen, um count '1' - bits, die besten können auch gefunden werden hier (obwohl das Buch hat Erklärungen, die dieser website nicht).

Sobald Sie wissen, die '1' - bits zählen, nur subtrahieren Sie die Anzahl der bits, die in der Art Ihrer Darstellung.

InformationsquelleAutor icecrime

Tun ein Kompliment zählt dann die 1s.

count_zero_bits( x ) = count_one_bits( ~x );

Implementieren Sie den code zum zählen der Einsen.

template< typename I > 
int count_one_bits( I i )
{
   size_t numbits = 0;
   for( ; i != 0; i >>= 1 )
   {
      numbits += i&1;
   }
}

obwohl es ein Problem mit meiner Funktion, wenn ich eine negative Zahl, weil >> lege 1-bits in der rechten Seite, so erhalten Sie eine nie-terminierende Schleife. Wenn es eine vorgefertigte durchsetzen, einen unsigned-Typ, der wäre ideal.

Sobald Sie das haben, dann:

template< typename I > int count_zero_bits( I i )
{
   return count_one_bits( ~i );
}

arbeiten.

InformationsquelleAutor CashCow

Erweiterung auf ronag Antwort, die von den anderen Nutzern erwähnt habe, führt zu falschen Ergebnissen (seinen Algorithmus funktioniert nur bis zu einem Wert von x = 15), hier ist eine aktualisierte version des Algorithmus:

uint8_t count_1bits(uint32_t x) {
    x = x - ((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 & 0x3F;
}

uint8_t count_0bits(uint32_t x)    {
    return 32 - count_1bits(x);
}

Die Erklärung der ersten Zeile von ronag ist richtig, jedoch, die restlichen Zeilen werden mit einem anderen Ansatz. In der ersten Zeile, durch die Verschiebung und Subtraktion, jede 2-bit-Paares enthält die Anzahl der bits, die gesetzt wurden, in einem paar in der ursprünglichen Anzahl. Der rest der Zeilen rekursiv Falten Sie diese zahlen zusammen, indem die lsb der einzelnen 2n-bit-Gruppe, um den msb, dass ein paar verschoben von n, so dass die 2n-bit-Gruppe enthält die Anzahl der bits, die gesetzt wurde, in dieser Gruppe in der original-Nummer:

01110110: 0111 (7 bits were set in the original number) 0110 (6 bits were set in the original number)
-> 01110110 & 00001111 + (01110110 >> 4) & 00001111
= 0110 + 0111
= 1101

Den oben beschriebenen Algorithmus arbeitet für 32-bit-Ganzzahlen, aber kann leicht angepasst werden durch ändern der Konstanten auf die richtige bit-Länge, so dass das Muster gleich bleibt (z.B. 0x5555... = 0101..., 0x0f0f... = 00001111... usw.) und das hinzufügen/entfernen der entsprechenden Schichten

InformationsquelleAutor milch