Wie funktioniert dieser Algorithmus zum Zählen der Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl?

Question

Feb 27, 2014, 11:16 PM

Wie funktioniert dieser Algorithmus zum Zählen der Anzahl der gesetzten Bits in einer 32-Bit-Ganzzahl?

int SWAR(unsigned int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

Ich habe diesen Code gesehen, der die Anzahl der Bits gleich zählt1 in 32-Bit-Ganzzahl, und ich bemerkte, dass seine Leistung besser ist als__builtin_popcount aber ich kann nicht verstehen, wie es funktioniert.

Kann jemand eine detaillierte Erklärung geben, wie dieser Code funktioniert?