Wie die Anzahl der gesetzten Bits in einem 32-Bit-Integer zählen?
https://stackoverflow.com/questions/109023
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
8 Bits der Nummer 7 sieht wie folgt darstellen:
00000111
Drei Bits werden.
Was sind Algorithmen, um die Anzahl der gesetzten Bits in einem 32-Bit-Integer zu bestimmen?
Lösung
Dies ist bekannt als die ' Hamming Gewicht ', 'PopCount' oder 'seitwärts Zusatz' .
Der ‚beste‘ Algorithmus hängt wirklich davon ab, welche CPU Sie sind und was Ihre Nutzungsmuster ist.
Einige CPUs haben einen einzigen integrierten in Anweisung, es zu tun und andere haben parallel Befehle, die auf Bitvektoren wirken. Die parallelen Anweisungen (wie x86 des popcnt, auf CPUs, wo es unterstützt wird) wird mit ziemlicher Sicherheit am schnellsten. Einige andere Architekturen haben eine langsame Anweisung mit einer Mikrocode-Schleife implementiert, die einen Bit pro Zyklus Tests ( Bearbeiten ).
Eine vorge besiedelten Tabellen-Lookup-Methode kann sehr schnell sein, wenn Ihre CPU einen großen Cache und / oder Sie viele dieser Anleitung in einer engen Schleife tun. Allerdings kann es aufgrund der Kosten eines ‚Cache-Miss‘ leiden, wo die CPU einen Teil der Tabelle aus dem Hauptspeicher zu holen hat.
Wenn Sie wissen, dass Ihr Bytes meist 0'en oder meist 1en sein, dann gibt es sehr effiziente Algorithmen für diese Szenarien.
ich glaube, ein sehr guter Allzweck-Algorithmus die folgenden Ergebnisse, als ‚parallel‘ oder ‚mit variabler Genauigkeit SWAR Algorithmus‘ bekannt. Ich habe diese Sprache in einer C-ähnlichen Pseudo ausgedrückt, müssen Sie es anpassen für eine bestimmte Sprache arbeiten (zum Beispiel unter Verwendung von uint32_t für C ++ und >>> in Java):
int numberOfSetBits(int i)
{
// Java: use >>> instead of >>
// C or C++: use uint32_t
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
Dies hat das beste Worst-Case-Verhalten von einem des Algorithmen diskutiert, so effizient mit jedem Nutzungsmuster umgehen oder Werten, die Sie an ihn werfen.
Dieser bitweise SWAR Algorithmus könnte parallelisieren auf einmal in mehreren Vektorelementen durchgeführt wird, statt in einem einzigen Integer-Register, für eine Beschleunigung auf CPUs mit SIMD aber keine nutzbare PopCount Anweisung. (Z x86-64-Code, der auf einer CPU laufen muß, nicht nur Nehalem oder später).
Allerdings ist der beste Weg Vektorbefehle für PopCount zu verwenden, ist in der Regel durch eine Variable-Shuffle mit einer Tabellensuche für 4 Bits zu einer Zeit eines jeden Bytes parallel zu tun. (Der 4-Bit-Index 16 a Eintragstabelle in einem Vektorregister gehalten werden).
Auf Intel-CPUs, der Hardware 64-Bit-popcnt Befehl kann übertrifft eine SSSE3 PSHUFB Bit-Parallel-Umsetzung um etwa einen Faktor von 2, aber nur , wenn Ihr Compiler es genau richtig bekommt. Ansonsten kann SSE kommt deutlich vor aus. Neuere Compiler-Versionen sind sich der falsche Abhängigkeit popcnt Problem auf Intel .
Referenzen:
https://graphics.stanford.edu/~seander/bithacks.html
https://en.wikipedia.org/wiki/Hamming_weight
http://gurmeet.net/puzzles/fast-bit-counting-routines /
http://aggregate.ee. engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)
Andere Tipps
Beachten Sie auch die integrierten Funktionen Ihres Compiler.
Auf dem GNU-Compiler zum Beispiel einfach verwenden können:
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
Im schlimmsten Fall wird der Compiler einen Aufruf einer Funktion generieren. Im besten Fall wird der Compiler einen CPU-Befehl auszusenden schneller die gleiche Arbeit zu tun.
Das GCC-Spezifika sogar über mehrere Plattformen hinweg arbeiten. PopCount wird Mainstream in der x86-Architektur worden, so macht es Sinn, jetzt die intrinsischen zu beginnen. Andere Architekturen haben die PopCount seit Jahren.
Auf x86, können Sie die Compiler sagen, dass es Unterstützung für popcnt Anweisung mit -mpopcnt annehmen kann oder -msse4.2 auch die Vektorbefehle zu ermöglichen, die in der gleichen Generation hinzugefügt wurden. Siehe GCC x86 Optionen . -march=nehalem (oder was auch immer -march= CPU Sie Ihren Code wollen und stimmen dafür übernehmen) könnte eine gute Wahl sein. Das Ausführen des resultierenden binären auf einer älteren CPU in einer illegalen Instruktion Fehler führen wird.
Um Binärdateien für die Maschine optimiert machen Sie sie bauen auf, verwenden -march=native (mit gcc, Klappern oder ICC).
MSVC bietet eine intrinsische für die x86-Instruktion popcnt , aber im Gegensatz zu gcc ist es wirklich eine intrinsische für die Hardware-Anweisung und erfordert Hardware-Unterstützung.
Mit std::bitset<>::count() anstelle eines eingebauten in
In der Theorie jeder Compiler, der weiß, wie effizient für den Ziel-CPU auf PopCount sollte diese Funktionalität durch ISO C ++ aussetzen std::bitset<> . In der Praxis könnte man mit dem Bit-Hack und / Shift / ADD in einigen Fällen für einige Ziele CPUs besser dran.
Für Ziel Architekturen, bei denen Hardware PopCount ist eine optionale Erweiterung (wie x86), nicht alle Compiler haben eine std::bitset die die Vorteile der es dauert, wenn verfügbar. Zum Beispiel hat MSVC keine Möglichkeit popcnt Unterstützung bei der Kompilierung zu ermöglichen, und verwendet immer ein Tabellennachschlag , auch mit /Ox /arch:AVX (der SSE4.2 impliziert, obwohl technisch ein separates Feature Bit für popcnt ist.)
Aber wenigstens Sie etwas portable erhalten, die überall funktioniert, und mit gcc / Klappern mit den richtigen Zieloptionen, Sie Hardware PopCount für Architekturen erhalten, die sie unterstützen.
#include <bitset>
#include <limits>
#include <type_traits>
template<typename T>
//static inline // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value, unsigned >::type
popcount(T x)
{
static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");
// sizeof(x)*CHAR_BIT
constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
// std::bitset constructor was only unsigned long before C++11. Beware if porting to C++03
static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");
typedef typename std::make_unsigned<T>::type UT; // probably not needed, bitset width chops after sign-extension
std::bitset<bitwidth> bs( static_cast<UT>(x) );
return bs.count();
}
Siehe asm von gcc, Klirren, icc und MSVC auf die Godbolt Compiler Explorer.
x86-64 gcc -O3 -std=gnu++11 -mpopcnt gibt diese:
unsigned test_short(short a) { return popcount(a); }
movzx eax, di # note zero-extension, not sign-extension
popcnt rax, rax
ret
unsigned test_int(int a) { return popcount(a); }
mov eax, edi
popcnt rax, rax
ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
xor eax, eax # gcc avoids false dependencies for Intel CPUs
popcnt rax, rdi
ret
PowerPC64 gcc -O3 -std=gnu++11 aussendet (für die int arg Version):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
Diese Quelle ist nicht x86-spezifische oder GNU-spezifische überhaupt, aber nur kompiliert gut für x86 mit gcc / Klappern / icc.
Beachten Sie auch, dass Rückfall des gcc für Architekturen ohne Single-Instruction PopCount ist eine Byte-at-a-time-Lookup-Tabelle. Dies ist nicht wunderbar für ARM, zum Beispiel .
Meiner Meinung nach ist die „beste“ Lösung ist derjenige, der von einem anderen Programmierer gelesen werden kann (oder der ursprünglichen Programmierer zwei Jahre später) ohne reichlich Kommentare. Sie können auch die schnellste oder klügste Lösung wollen, die einige bereits zur Verfügung gestellt haben, aber ich ziehe die Lesbarkeit über Klugheit jederzeit.
unsigned int bitCount (unsigned int value) {
unsigned int count = 0;
while (value > 0) { // until all bits are zero
if ((value & 1) == 1) // check lower bit
count++;
value >>= 1; // shift bits, removing lower bit
}
return count;
}
Wenn Sie mehr Geschwindigkeit wollen (und vorausgesetzt, Sie es gut dokumentieren Sie Ihre Nachfolger helfen), könnten Sie eine Lookup-Tabelle verwendet werden:
// Lookup table for fast calculation of bits set in 8-bit unsigned char.
static unsigned char oneBitsInUChar[] = {
// 0 1 2 3 4 5 6 7 8 9 A B C D E F (<- n)
// =====================================================
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
: : :
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};
// Function for fast calculation of bits set in 16-bit unsigned short.
unsigned char oneBitsInUShort (unsigned short x) {
return oneBitsInUChar [x >> 8]
+ oneBitsInUChar [x & 0xff];
}
// Function for fast calculation of bits set in 32-bit unsigned int.
unsigned char oneBitsInUInt (unsigned int x) {
return oneBitsInUShort (x >> 16)
+ oneBitsInUShort (x & 0xffff);
}
Obwohl diese auf bestimmte Datentyp Größen verlassen, so dass sie nicht tragbar sind. Da aber viele Performance-Optimierungen ohnehin nicht tragbar sind, dass möglicherweise kein Problem sein. Wenn Sie Portabilität wollen, ich auf die lesbare Lösung halten würde.
Von Hacker Delight, p. 66, Bild 5-2
int pop(unsigned x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
Führt in ~ 20-ish Anweisungen (Bogen abhängig), ohne Verzweigung.
Hacker Delight ist delightful! Sehr zu empfehlen.
Ich denke, den schnellsten Weg, ohne Lookup-Tabellen und PopCount -ist die folgenden. Er zählt die gesetzten Bits mit nur 12 Operationen.
int popcount(int v) {
v = v - ((v >> 1) & 0x55555555); // put count of each 2 bits into those 2 bits
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits
return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
Es funktioniert, weil Sie die Gesamtzahl der gesetzten Bits durch Teilung in zwei Hälften zählen kann, die Anzahl der gesetzten Bits in beiden Hälften zu zählen und dann das Hinzufügen sie. Auch bekannt als Divide and Conquer Paradigma. Lassen Sie uns ins Detail erhalten ..
v = v - ((v >> 1) & 0x55555555);
Die Anzahl der Bits in zwei Bits können 0b00, 0b01 oder 0b10 werden. Versuchen wir dies auf 2 Bits zu arbeiten ..
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
Dies ist, was erforderlich war: die letzte Spalte zeigt die Anzahl der gesetzten Bits in jedem Bit-Paar. Wenn die zwei Bit-Zahl ist >= 2 (0b10) dann erzeugt and 0b01, sonst bringt es 0b00.
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
Diese Aussage sollte leicht verständlich sein. Nach der ersten Operation haben wir die Anzahl der gesetzten Bits in jeweils zwei Bits, wir diese Zählung summieren nun in jeweils 4 Bits.
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
Wir summieren dann das obige Ergebnis, uns die Gesamtzahl der gesetzten Bits geben in 4 Bits. Die letzte Aussage ist das schwierig.
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
Lassen Sie uns brechen sie weiter ...
v + (v >> 4)
Es ist ähnlich wie die zweite Aussage; wir zählen die gesetzten Bits in Gruppen von 4 statt. Wir wissen-wegen unserer früheren Operationen-dass jeder knabbern die Anzahl der gesetzten Bits in ihm hat. Nehmen wir ein Beispiel. Angenommen, wir das Byte 0b01000010 haben. Das bedeutet, das erste Nibble hat sein 4bits gesetzt und die zweiten seine 2 Bits gesetzt haben. Nun fügen wir diese zusammen knabbert.
0b01000010 + 0b01000000
Es gibt uns die Anzahl der gesetzten Bits in einem Byte, in dem ersten knabbern 0b01100010 und deshalb maskieren wir die letzten vier Bytes aller Bytes in der Anzahl (verwerfen sie).
0b01100010 & 0xF0 = 0b01100000
Jetzt hat jedes Byte die Anzahl der gesetzten Bits in ihm. Wir brauchen sie alle zusammen addieren. Der Trick ist, das Ergebnis durch 0b10101010 zu vervielfachen, die eine interessante Eigenschaft hat. Wenn unsere Nummer vier Bytes hat, A B C D, wird es in einer neuen Nummer mit diesem Bytes A+B+C+D B+C+D C+D D führen. Eine 4-Byte-Zahl kann bis zu 32 Bits festgelegt, die als 0b00100000 dargestellt werden kann.
Alles, was wir jetzt brauchen, ist das erste Byte, das die Summe aller gesetzten Bits in allen Bytes hat, und wir bekommen es von >> 24. Dieser Algorithmus wurde entwickelt für 32 bit Worte, kann aber leicht für 64 bit Wörter geändert werden.
Wenn Sie geschehen, werden mit Hilfe von Java, die integrierte Methode Integer.bitCount wird das tun.
Ich habe gelangweilt, und zeitlich eine Milliarde Iterationen von drei Ansätzen. Compiler ist gcc O3. CPU ist, was sie in der 1. Generation Macbook Pro setzen.
Schnellste ist die folgende, in 3,7 Sekunden:
static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}
Der zweite Platz geht an den gleichen Code aber bis 4 Byte statt 2 Halbwörtern suchen. Das dauerte etwa 5,5 Sekunden.
Der dritte Platz geht an die Bit-Fummeln ‚seitwärts Zusatz‘ Ansatz, der 8,6 Sekunden dauerte.
Die vierte Platz geht an GCC __builtin_popcount () bei einer beschämenden 11 Sekunden.
Das Zählen Einer-Bit-at-a-time war Ansatz waaaay langsamer, und ich habe gelangweilt darauf zu warten, es zu beenden.
Wenn Sie also über die Leistung vor allem Pflege anders dann den ersten Ansatz. Wenn Sie sich interessieren, aber nicht genug, 64 KB RAM dafür ausgeben, den zweiten Ansatz. Ansonsten verwenden Sie den lesbaren (aber langsam) Ein-Bit-at-a-time-Ansatz.
Es ist schwer, eine Situation zu denken, wo Sie den Bit-Fummel Ansatz verwenden wollen würden.
Edit: ähnliche Ergebnisse hier .
unsigned int count_bit(unsigned int x)
{
x = (x & 0x55555555) + ((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;
}
Lassen Sie mich diesen Algorithmus erklären.
Dieser Algorithmus basiert auf Divide and Conquer-Algorithmus. Angenommen, es ist ein 8-Bit-Integer-213 (11010101 binär), der Algorithmus funktioniert wie folgt (jedes Mal verschmilzt zwei Nachbarblocks):
+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | <- x
| 1 0 | 0 1 | 0 1 | 0 1 | <- first time merge
| 0 0 1 1 | 0 0 1 0 | <- second time merge
| 0 0 0 0 0 1 0 1 | <- third time ( answer = 00000101 = 5)
+-------------------------------+
Dies ist eine jener Fragen, wo es Ihre Mikro-Architektur hilft wissen. Ich timed nur zwei Varianten unter gcc 4.3.3 kompiliert mit O3 C ++ inlines Funktionsaufruf Aufwand zu beseitigen, eine Milliarde Iterationen, die laufende Summe aller Zählungen halten den Compiler, um sicherzustellen, entfernt nicht alles wichtig, mit RDTSC für Timing ( Taktzyklus genau).
inline int pop2(unsigned x, unsigned y)
{
x = x - ((x >> 1) & 0x55555555);
y = y - ((y >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
y = y + (y >> 8);
x = x + (x >> 16);
y = y + (y >> 16);
return (x+y) & 0x000000FF;
}
Die unmodifizierten Hacker Delight nahm 12,2 gigacycles. Meine parallele Version (doppelt so viele Bits gezählt) läuft in 13,0 gigacycles. 10.5s insgesamt verstrichene sowohl für die zusammen auf einem 2,4 GHz Core Duo. 25 gigacycles = etwas mehr als 10 Sekunden bei dieser Taktfrequenz, ich bin so zuversichtlich, meine Timings richtig sind.
Das hat mit der Anweisung Abhängigkeitsketten zu tun, die für diesen Algorithmus sehr schlecht sind. Ich konnte die Geschwindigkeit wieder fast verdoppeln, indem ein Paar von 64-Bit-Registern verwendet wird. In der Tat, wenn ich bin klug und hinzugefügt x + y ein wenig früher ich einige Verschiebungen abrasieren konnte. Die 64-Bit-Version mit einigen kleinen Verbesserungen kommen würde etwa noch, aber auch hier doppelt so viele Bits zählen.
Mit 128-Bit-SIMD-Register, ein weiterer Faktor zwei, und die SSE-Befehlssätze oft clevere Abkürzungen haben, auch.
Es gibt keinen Grund für den Code besonders transparent zu sein. Die Schnittstelle ist einfach, kann der Algorithmus on-line an vielen Stellen verwiesen werden, und es ist offen für umfassenden Unit-Test. Der Programmierer, der darauf stolpert vielleicht sogar etwas lernen. Diese Bit-Operationen sind sehr natürlich auf der Maschinenebene.
OK, ich Bank beschlossen, die gezwickt 64-Bit-Version. Für diesen einen sizeof (unsigned long) == 8
inline int pop2(unsigned long x, unsigned long y)
{
x = x - ((x >> 1) & 0x5555555555555555);
y = y - ((y >> 1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
x = x + y;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
return x & 0xFF;
}
Das sieht ungefähr richtig (Ich bin nicht sorgfältig testen, obwohl). Nun kommen die Timings aus bei 10.70 gigacycles / 14.1 gigacycles. Die späte Zahl summierte 128 Milliarden Bits und entspricht 5.9s auf dieser Maschine verstrichen ist. Die nicht-parallele Version beschleunigt ein kleines bisschen, weil ich in 64-Bit-Modus ausgeführt wird und es mag 64-Bit-Register etwas besser als 32-Bit-Register.
Lassen Sie uns sehen, ob es ein bisschen mehr OOO Pipelining ist hier werden musste. Das war ein bisschen mehr beteiligt, so dass ich getestet tatsächlich ein wenig. Jeder Begriff allein Summen bis 64, alle kombinierte Summe auf 256
inline int pop4(unsigned long x, unsigned long y,
unsigned long u, unsigned long v)
{
enum { m1 = 0x5555555555555555,
m2 = 0x3333333333333333,
m3 = 0x0F0F0F0F0F0F0F0F,
m4 = 0x000000FF000000FF };
x = x - ((x >> 1) & m1);
y = y - ((y >> 1) & m1);
u = u - ((u >> 1) & m1);
v = v - ((v >> 1) & m1);
x = (x & m2) + ((x >> 2) & m2);
y = (y & m2) + ((y >> 2) & m2);
u = (u & m2) + ((u >> 2) & m2);
v = (v & m2) + ((v >> 2) & m2);
x = x + y;
u = u + v;
x = (x & m3) + ((x >> 4) & m3);
u = (u & m3) + ((u >> 4) & m3);
x = x + u;
x = x + (x >> 8);
x = x + (x >> 16);
x = x & m4;
x = x + (x >> 32);
return x & 0x000001FF;
}
Ich war für einen Moment aufgeregt, aber es stellt sich heraus, gcc mit O3 Inline-Tricks spielt, obwohl ich nicht das Schlüsselwort inline in einigen Tests mit bin. Wenn ich gcc spielen Tricks lassen, eine Milliarde Anrufe POP4 () nimmt 12.56 gigacycles, aber ich bestimmt es Argumente als konstante Ausdrücke faltete. Eine realistischere Zahl erscheint für weitere 30% Beschleunigungs-19.6gc zu sein. Meine Testschleife sieht nun wie folgt aus, um sicherzustellen, jedes Argument unterschiedlich genug ist gcc zu stoppen Tricks zu spielen.
hitime b4 = rdtsc();
for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i)
sum += pop4 (i, i^1, ~i, i|1);
hitime e4 = rdtsc();
256 Milliarden summierten Bits in 8.17s verstrichen ist. Ausarbeitet, um 1.02s für 32 Millionen Bits, wie in der 16-Bit-Lookup-Tabelle gebenchmarkt. Kann nicht direkt vergleichen, weil die andere Bank, keine Taktgeschwindigkeit geben, sondern sieht aus wie ich den Rotz aus der 64KB Tisch Ausgabe schlug habe, die eine tragische Verwendung von L1-Cache in erster Linie ist.
Update: beschlossen, das Offensichtliche zu tun und schaffen POP6 () durch vier Hinzufügen von mehr dupliziert Linien. Kam zu 22.8gc 384 Milliarden Bits in 9.5s verstrichene summiert. So gibt es eine weitere 20% Jetzt bei 800ms für 32 Milliarden Bits.
Warum nicht iterativ dividieren durch 2?
count = 0
while n > 0
if (n % 2) == 1
count += 1
n /= 2
Ich bin damit einverstanden, dass dies nicht die schnellste, aber „beste“ ist nicht ganz eindeutig. Ich würde behaupten, obwohl die „beste“ sollte ein Element der Klarheit
Die Freude des Hacker-Bit-Fummeln wird so viel klarer, wenn man die Bitmuster schreiben.
unsigned int bitCount(unsigned int x)
{
x = ((x >> 1) & 0b01010101010101010101010101010101)
+ (x & 0b01010101010101010101010101010101);
x = ((x >> 2) & 0b00110011001100110011001100110011)
+ (x & 0b00110011001100110011001100110011);
x = ((x >> 4) & 0b00001111000011110000111100001111)
+ (x & 0b00001111000011110000111100001111);
x = ((x >> 8) & 0b00000000111111110000000011111111)
+ (x & 0b00000000111111110000000011111111);
x = ((x >> 16)& 0b00000000000000001111111111111111)
+ (x & 0b00000000000000001111111111111111);
return x;
}
Der erste Schritt fügt die geraden Bits zu dem ungeradzahligen Bits, um eine Summe von zwei Bits in jeder Herstellung. Die anderen Schritte hinzufügen höherwertigen Brocken zu niedriger Ordnung Stücke, bis die Blockgröße den ganzen Weg zu verdoppeln, bis wir die endgültige Anzahl der gesamten int Aufnahme haben.
Für einen Mittelweg zwischen einer 2 32 Lookup-Tabelle und iteriert durch jedes Bit einzeln:
int bitcount(unsigned int num){
int count = 0;
static int nibblebits[] =
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
for(; num != 0; num >>= 4)
count += nibblebits[num & 0x0f];
return count;
}
Es ist nicht die schnellste oder beste Lösung, aber ich fand die gleiche Frage in dem Weg, und ich begann zu denken und zu denken. schließlich wurde mir klar, dass es wie dies getan werden kann, wenn man das Problem von der mathematischen Seite bekommen, und eine Grafik zeichnen, dann finden Sie, dass es sich um eine Funktion ist, die eine gewisse periodische Teil hat, und dann merkt man den Unterschied zwischen den Perioden ... so hier gehen Sie:
unsigned int f(unsigned int x)
{
switch (x) {
case 0:
return 0;
case 1:
return 1;
case 2:
return 1;
case 3:
return 2;
default:
return f(x/4) + f(x%4);
}
}
Dies kann in O(k) erfolgen, wo k ist die Anzahl der Bits gesetzt.
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
Die Funktion Sie suchen, wird oft als die „seitlich Summe“ oder „Bevölkerungszahl“ einer binären Zahl genannt. Knuth erörtert ihn in pre-Faszikel 1A, pp11-12 (obwohl es ein kurzer Hinweis in Band 2 war, 4.6.3- (7)).
Die locus classicus ist Artikel Peter Wegner "Eine Technik für Ones in einem binären Computer-Counting", aus dem Communications of the ACM , Volume 3 (1960) Nummer 5 , Seite 322 . Er gibt zwei verschiedene Algorithmen gibt, eine für Zahlen optimiert zu erwarten sein „spärlich“ (das heißt, eine kleine Anzahl von Einsen haben) und eine für den umgekehrten Fall.
Ein paar offene Fragen: -
- Wenn die Zahl negativ ist dann?
- Wenn die Zahl 1024 ist, dann ist die „iterativ dividieren durch 2“ Methode 10-mal wiederholen.
Wir können die algo modifizieren, um die negative Zahl zu unterstützen, wie folgt: -
count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
count += 1
n /= 2
return count
nun das zweite Problem überwinden wir die algo wie schreiben: -
int bit_count(int num)
{
int count=0;
while(num)
{
num=(num)&(num-1);
count++;
}
return count;
}
für eine vollständige Referenz finden Sie unter:
http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html
private int get_bits_set(int v)
{
int c; // c accumulates the total bits set in v
for (c = 0; v>0; c++)
{
v &= v - 1; // clear the least significant bit set
}
return c;
}
Ich denke, die Brian Kernighan die Methode zu Nutzen sein wird ... Es geht durch so viele Iterationen wie dort gesetzten Bits sind. Wenn wir also über ein 32-Bit-Wort haben nur mit dem hohen Bit gesetzt, dann wird es geht nur einmal durch die Schlaufe.
int countSetBits(unsigned int n) {
unsigned int n; // count the number of bits set in n
unsigned int c; // c accumulates the total bits set in n
for (c=0;n>0;n=n&(n-1)) c++;
return c;
}
Veröffentlicht im Jahr 1988, der Programmiersprache C 2nd Ed. (Von Brian W. Kernighan und Dennis M. Ritchie) erwähnt dies in Übung 2-9. Am 19. April 2006 wies Don Knuth mich darauf hin, dass diese Methode „wurde in CACM 3 (1960), veröffentlicht von Peter Wegner ersten, 322. (auch unabhängig von Derrick Lehmer entdeckt und im Jahr 1964 in einem Buch herausgegeben von Beckenbach veröffentlicht.)“
Ich verwende den folgenden Code, intuitiver ist.
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
Logik: n. & (N-1) setzt die zuletzt eingestellte Bit von n
P. S:. Ich weiß, das ist nicht O (1) Lösung, wenn auch eine interessante Lösung
Was tun Sie bedeuten, mit „Bestem Algorithmus“? Der kurzgeschlossene Code oder der gefastet Code? Ihr Code sehr elegant aussehen und es hat eine konstante Ausführungszeit. Der Code ist auch sehr kurz.
Wenn aber die Geschwindigkeit der Hauptfaktor ist und nicht die Codegröße dann denke ich, die folgen kann schneller sein:
static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
static int bitCountOfByte( int value ){
return BIT_COUNT[ value & 0xFF ];
}
static int bitCountOfInt( int value ){
return bitCountOfByte( value )
+ bitCountOfByte( value >> 8 )
+ bitCountOfByte( value >> 16 )
+ bitCountOfByte( value >> 24 );
}
Ich denke, dass dies nicht mehr schneller für einen 64-Bit-Wert, sondern ein 32-Bit-Wert kann schneller sein.
schrieb ich einen schnellen Bitcount Makro für RISC-Rechner in etwa 1990. Dabei spielt es keine erweiterte Arithmetik (Multiplikation, Division,%), Speicher (viel zu langsam), Zweige (viel zu langsam) holen, aber es tut übernimmt die CPU verfügt über einen 32-Bit-Barrel-Shifter (in anderen Worten, >> 1 und >> 32 nimmt die gleiche Menge an Zyklen). Es wird davon ausgegangen, dass kleine Konstanten (wie beispielsweise 6, 12, 24) nichts kostet in die Register zu laden, oder sind in Provisorien gespeichert und wiederverwendet werden immer und immer wieder.
Mit diesen Annahmen zählt er 32 Bits in etwa 16 Zyklen / Anweisungen auf den meisten RISC-Maschinen. Man beachte, dass 15 Anweisungen / Zyklen sind in der Nähe einer unteren Schranke für die Anzahl von Zyklen oder Anweisungen, weil es mindestens 3 Anweisungen (Maske, Verschiebung, operator) zu nehmen scheint die Anzahl der Summanden in zwei Hälften geschnitten, so log_2 (32) = 5, 5 x 3 = 15 Anweisungen sind ein quasi-UntereGrenze.
#define BitCount(X,Y) \
Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
Y = ((Y + (Y >> 3)) & 030707070707); \
Y = (Y + (Y >> 6)); \
Y = (Y + (Y >> 12) + (Y >> 24)) & 077;
Hier ist ein Geheimnis für den ersten und komplexeste Schritt:
input output
AB CD Note
00 00 = AB
01 01 = AB
10 01 = AB - (A >> 1) & 0x1
11 10 = AB - (A >> 1) & 0x1
Wenn ich also die 1. Säule (A) oben verschieben es rechts 1 Bit, und subtrahieren sie von AB, bekomme ich die Ausgabe (CD). Die Erweiterung auf 3 Bits ist ähnlich; Sie können es mit einer 8-Reihe boolean Tabelle wie meine oben, wenn Sie es wünschen.
- Don Gillies
Wenn Sie C ++ verwenden eine andere Option ist Metaprogrammierung zu verwenden:
// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
// return the least significant bit plus the result of calling ourselves with
// .. the shifted value
return (val & 0x1) + countBits<BITS-1>(val >> 1);
}
// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
return val & 0x1;
}
Nutzung wäre:
// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )
// another byte (this returns 7)
countBits<8>( 254 )
// counting bits in a word/short (this returns 1)
countBits<16>( 256 )
Sie natürlich könnte diese Vorlage erweitern verschiedene Arten zu verwenden (auch automatische Erkennung Bitgröße), aber ich habe es einfach für Klarheit gehalten.
Bearbeiten: vergessen zu erwähnen, das ist gut, weil es sollte Arbeiten in jedem C ++ Compiler und es im Grunde entrollt nur für Sie Ihre Schleife, wenn ein konstanter Wert für das Bit verwendet wird Zahl (mit anderen Worten, ich bin ziemlich sicher, dass es die schnellste allgemeine Methode ist Sie finden)
Ich bin besonders gern dieses Beispiel aus dem Vermögen Datei:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333)
- (((x)>>3)&0x11111111))
Ich mag es am besten, weil es so schön ist!
Java jdk1.5
Integer.bitCount (n);
wobei n die Zahl, deren 1'en ist gezählt werden.
auch zu prüfen,
Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);
//Beginning with the value 1, rotate left 16 times
n = 1;
for (int i = 0; i < 16; i++) {
n = Integer.rotateLeft(n, 1);
System.out.println(n);
}
fand ich eine Implementierung von Bits in einem Array Zählen unter Verwendung von SIMD-Befehl (SSSE3 und AVX2). Es hat in 2-2,5 mal bessere Leistung als wenn es intrinsische Funktion __popcnt64 wird.
SSSE3 Version:
#include <smmintrin.h>
#include <stdint.h>
const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m128i _sum = _mm128_setzero_si128();
for (size_t i = 0; i < size; i += 16)
{
//load 16-byte vector
__m128i _src = _mm_loadu_si128((__m128i*)(src + i));
//get low 4 bit for every byte in vector
__m128i lo = _mm_and_si128(_src, F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
}
uint64_t sum[2];
_mm_storeu_si128((__m128i*)sum, _sum);
return sum[0] + sum[1];
}
AVX2 Version:
#include <immintrin.h>
#include <stdint.h>
const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m256i _sum = _mm256_setzero_si256();
for (size_t i = 0; i < size; i += 32)
{
//load 32-byte vector
__m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
//get low 4 bit for every byte in vector
__m256i lo = _mm256_and_si256(_src, F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
}
uint64_t sum[4];
_mm256_storeu_si256((__m256i*)sum, _sum);
return sum[0] + sum[1] + sum[2] + sum[3];
}
Ich benutze diese immer in Competitive Programmierung und es ist leicht zu schreiben und effizient:
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
Es gibt viele Algorithmus, um die gesetzten Bits zu zählen; aber ich denke, das Beste ist, desto schneller ein! Sie können die detaillierten auf dieser Seite sehen:
Ich schlage vor, diese:
Counting gesetzten Bits in 14, 24, oder 32-Bit-Wörter 64-Bit-Befehle
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
// option 2, for at most 24-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)
% 0x1f;
// option 3, for at most 32-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %
0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
Dieses Verfahren erfordert ein 64-Bit-CPU mit schnellen Modul Division effizient. Die erste Option dauert nur 3 Operationen; Die zweite Option dauert 10; und die dritte Option nimmt 15
Fast C # Lösung mit vorberechnete Tabelle von Byte Bit zählt mit Verzweigung auf Eingabegröße.
public static class BitCount
{
public static uint GetSetBitsCount(uint n)
{
var counts = BYTE_BIT_COUNTS;
return n <= 0xff ? counts[n]
: n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
: n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
: counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
}
public static readonly uint[] BYTE_BIT_COUNTS =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
}
Hier ist ein tragbares Modul (ANSI-C), wo Benchmark jedes Ihrer Algorithmen auf jeder Architektur.
Ihre CPU verfügt über 9-Bit-Bytes? Kein Problem :-) Im Moment setzt sie zwei Algorithmen, die K & R-Algorithmus und eine Byte-weise Lookup-Tabelle. Die Nachschlagtabelle ist im Durchschnitt 3 mal schneller als der K & R-Algorithmus. Wenn jemand einen Weg des „Hacker Delight“ Algorithmus portable gerne hinzufügen, um es in.
machen#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_
/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );
/* List of available bitcount algorithms.
* onTheFly: Calculate the bitcount on demand.
*
* lookupTalbe: Uses a small lookup table to determine the bitcount. This
* method is on average 3 times as fast as onTheFly, but incurs a small
* upfront cost to initialize the lookup table on the first call.
*
* strategyCount is just a placeholder.
*/
enum strategy { onTheFly, lookupTable, strategyCount };
/* String represenations of the algorithm names */
extern const char *strategyNames[];
/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );
#endif
.
#include <limits.h>
#include "bitcount.h"
/* The number of entries needed in the table is equal to the number of unique
* values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;
static int _defaultBitCount( unsigned int val ) {
int count;
/* Starting with:
* 1100 - 1 == 1011, 1100 & 1011 == 1000
* 1000 - 1 == 0111, 1000 & 0111 == 0000
*/
for ( count = 0; val; ++count )
val &= val - 1;
return count;
}
/* Looks up each byte of the integer in a lookup table.
*
* The first time the function is called it initializes the lookup table.
*/
static int _tableBitCount( unsigned int val ) {
int bCount = 0;
if ( !_lookupTableInitialized ) {
unsigned int i;
for ( i = 0; i != UCHAR_MAX + 1; ++i )
_bitCountTable[i] =
( unsigned char )_defaultBitCount( i );
_lookupTableInitialized = 1;
}
for ( ; val; val >>= CHAR_BIT )
bCount += _bitCountTable[val & UCHAR_MAX];
return bCount;
}
static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;
const char *strategyNames[] = { "onTheFly", "lookupTable" };
void setStrategy( enum strategy s ) {
switch ( s ) {
case onTheFly:
_bitcount = _defaultBitCount;
break;
case lookupTable:
_bitcount = _tableBitCount;
break;
case strategyCount:
break;
}
}
/* Just a forwarding function which will call whichever version of the
* algorithm has been selected by the client
*/
int bitcount( unsigned int val ) {
return _bitcount( val );
}
#ifdef _BITCOUNT_EXE_
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Use the same sequence of pseudo random numbers to benmark each Hamming
* Weight algorithm.
*/
void benchmark( int reps ) {
clock_t start, stop;
int i, j;
static const int iterations = 1000000;
for ( j = 0; j != strategyCount; ++j ) {
setStrategy( j );
srand( 257 );
start = clock( );
for ( i = 0; i != reps * iterations; ++i )
bitcount( rand( ) );
stop = clock( );
printf
( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
reps * iterations, strategyNames[j],
( double )( stop - start ) / CLOCKS_PER_SEC );
}
}
int main( void ) {
int option;
while ( 1 ) {
printf( "Menu Options\n"
"\t1.\tPrint the Hamming Weight of an Integer\n"
"\t2.\tBenchmark Hamming Weight implementations\n"
"\t3.\tExit ( or cntl-d )\n\n\t" );
if ( scanf( "%d", &option ) == EOF )
break;
switch ( option ) {
case 1:
printf( "Please enter the integer: " );
if ( scanf( "%d", &option ) != EOF )
printf
( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
option, option, bitcount( option ) );
break;
case 2:
printf
( "Please select number of reps ( in millions ): " );
if ( scanf( "%d", &option ) != EOF )
benchmark( option );
break;
case 3:
goto EXIT;
break;
default:
printf( "Invalid option\n" );
}
}
EXIT:
printf( "\n" );
return 0;
}
#endif
32-Bit oder nicht? Ich kam gerade mit dieser Methode in Java nach dem Lesen „ die Codierung Interview Cracken“ 4. Auflage exercice 5.5 (Kap 5: Bit Manipulation). Wenn das niedrigstwertige Bit 1 Inkrement count ist, dann mit der rechten verschieben die ganze Zahl ist.
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
ich denke, das ein intuitiver als die Lösungen mit konstantem 0x33333333 ist, egal wie schnell sie sind. Es hängt von Ihrer Definition von "best-Algorithmus".
