Dies ist Teil einer Divide-and-Conquer-Strategie zum Zählen von Bits, die als "Populations" -Funktion bezeichnet wird. Die wissenschaftliche Behandlung dieser Strategie kann in Reingold und Nievergelt, 1977 gefunden werden. Die Idee ist, zuerst die Bits paarweise, dann 4-weise, dann 8-weise und so weiter zu summieren. Wenn Sie beispielsweise die Bits 1011 haben, wird das erste Paar 1001, weil es ein Bit gibt, und das zweite wird 10, da 10 = 2 binär ist und es zwei Bits in 11 gibt. Die wesentliche Tatsache hierbei ist, dass:
population(x) = x - (x/2) - (x/4) - (x/8) - (x/16) - ... etc.
Der genaue Algorithmus Sie haben, ist eine Variante dessen, was als „HAKMEM“ Algorithmus bekannt ist (siehe Beeler, Gosper und Schröppel, 1972). Dieser Algorithmus zählt 1 in 4-Bit-Feldern parallel, dann werden diese Summen in 8-Bit-Summen umgewandelt. Der letzte Schritt ist eine Operation zum Hinzufügen dieser 4 Bytes durch Multiplizieren mit 0x01010101. Die 0x0F0F0F0F Maske erhält die 4-fachen Bytesummen durch Ausblenden von Nicht-Summeninformationen. Nehmen wir beispielsweise an, dass das 8-seitige Feld 10110110 ist, dann gibt es 5 Bits, die gleich 0101 sind, also werden wir 10110101 haben. Nur die letzten vier Bits sind signifikant, so maskieren wir die ersten vier, das heißt:
10110101 & 0x0F = 00000101
Sie können ein ganzes Kapitel über die Minutien finden Bits in dem Buch „Hackers Delight“ von Henry Warren zu zählen.
Randbemerkung: Es ist nicht wirklich "O (1)". Es ist "O (log (n))" zu der Anzahl von Bits, während eine einfache Schleife "O (n)" ist. Für eine feste Integer-Größe sind sowohl diese als auch eine geradlinige Schleife "O (1)". – Mysticial
@Mysticial Ja, wenn wir einen 32-Bit-Int betrachten, sind sie beide O (1). Aber dieser sollte schneller sein als die Iteration, oder? – NSF