C-Code zum Zählen der Anzahl von '1' Bits in einem unsignierten Zeichen

Derselbe Code wird für ein unsigniertes Zeichen funktionieren. Schleife über alle Bits, die sie testen. Siehe dies .

Ein Array, das die Anzahl der Bits für 0 bis 15 kennt. Fügen Sie die Ergebnisse für jedes Nibble hinzu.

HACKMEM hat diesen Algorithmus in drei Operationen (grob in C übersetzt):

( ULL soll 64-Bit-Arithmetik erzwingen. Es wird benötigt, nur knapp ... diese Berechnung erfordert 33-Bit-Ganzzahlen.)

Tatsächlich können Sie die zweite Konstante durch 042104210021ULL ersetzen, da Sie nur 8 Bits zählen, aber es sieht nicht so gut symmetrisch aus.

Wie funktioniert das? Denken Sie an c bitweise und denken Sie daran, dass (a + b) % c = (a % c + b % c) % c und (a | b) == a + b iff (a & b) == 0 .

Wenn Sie keine 64-Bit-Arithmetik zur Verfügung haben, können Sie c in Nibbles aufteilen und jede Hälfte durchführen, wobei Sie 9 Operationen ausführen. Dies erfordert nur 13 Bits, so dass 16- oder 32-Bit-Arithmetik funktioniert.

Zum Beispiel, wenn c == 105 == 0b11001001 ,

Siehe die Bit Twiddling Hacks Seite: Ссылка

es gibt viele gute Lösungen dafür.

Auch diese Funktion in ihrer einfachsten Implementierung ist ziemlich trivial. Sie sollten sich die Zeit nehmen, um zu lernen, wie das geht.

Für eine ganze Zahl, die so klein ist wie ein Zeichen ohne Vorzeichen, erhalten Sie die beste Leistung mit einer kleinen Nachschlagetabelle.

Ich weiß, welche Populationszählungsalgorithmen Sie erwähnen. Sie arbeiten mit Arithmetik mehrerer Wörter, die kleiner als eine in einem Register gespeicherte ganze Zahl sind.

Diese Technik wird SWAR ( Ссылка ) genannt.

Weitere Informationen finden Sie auf der Website von Hackers Delight: www.hackersdelight.org. Er hat Beispielcode und hat ein Buch geschrieben, das diese Tricks im Detail erklärt.

Wie bereits beantwortet, funktionieren die Standardmethoden zum Zählen von Bits auch mit unsignierten Zeichen.

Beispiel:

ein Zeichen ohne Vorzeichen ist eine "Nummer" auf die gleiche Weise, wie ein 32-Bit-Float oder Integer eine "Zahl" ist, was der Compiler sie zu repräsentieren meint, was sich ändert.

Wenn Sie sich ein Char als seine Bits vorstellen:

01010011 (8 Bits);

Sie können die gesetzten Bits wie folgt zählen:

nimm den Wert, sagen wir x, und nimm x% 2, der Rest ist entweder 1 oder 0. Das ist, abhängig von der Endianz des Chars, das linke oder rechte Bit. akkumulieren Sie den Rest in einer separaten Variablen (dies ist die resultierende Anzahl der gesetzten Bits).

dann & gt; & gt; (Rechtsverschiebung) 1 Bit.

wiederholen, bis 8 Bits verschoben wurden.

Der c-Code sollte ziemlich einfach aus meinem Pseudocode zu implementieren sein, aber grundsätzlich

Basierend auf Ephemient's Post, haben wir die keine verzweigte 8-Bit-Version. Es ist im hexadezimalen Ausdruck.

Übernehmen Sie es zweimal, wir haben eine 16-Bit-Version, die 9 Operationen benötigt.

Hier schreibe ich eine Variante mit 16 Bit, die 64 Bit Register und 11 Operationen benötigt. Es scheint nicht besser als das vorherige, aber es verwendet nur 1 Modulo-Operation.