Anzahl der Bits in einer 64-Bit-Ganzzahl (lang, groß) zählen?

Question

Ich habe this SO question über 32-Bit gelesen, aber was ist mit 64-Bit-Zahlen? Sollte ich nur die oberen und unteren 4 Bytes maskieren, die Zählung auf den 32 Bits durchführen und sie dann zusammenfügen?

Answer 1

Sie 64-Bit-Version http://en.wikipedia.org/wiki/Hamming_weight

finden Sie hier Es ist so etwas wie dieses

static long NumberOfSetBits(long i) 
{ 
    i = i - ((i >> 1) & 0x5555555555555555); 
    i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333); 
    return (((i + (i >> 4)) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56; 
} 

Dies ist eine 64-Bit-Version des Codes bilden hier How to count the number of set bits in a 32-bit integer?

Joshua Vorschlag Verwendung Ich würde verwandeln es in das:

static int NumberOfSetBits(ulong i) 
{ 
    i = i - ((i >> 1) & 0x5555555555555555UL); 
    i = (i & 0x3333333333333333UL) + ((i >> 2) & 0x3333333333333333UL); 
    return (int)(unchecked(((i + (i >> 4)) & 0xF0F0F0F0F0F0F0FUL) * 0x101010101010101UL) >> 56); 
} 

EDIT: Ich habe einen Fehler beim Testen der 32-Bit-Version gefunden. Ich habe fehlende Klammern hinzugefügt. Die Summe sollte

EDIT2 hinzugefügt sicherere Version für Ulong

Answer 2

Eine schnelle (und mehr tragbar als die Verwendung von Nicht-Standard-Compiler-Erweiterungen) Art und Weise:

int bitcout(long long n) 
{ 
    int ret=0; 
    while (n!=0) 
    { 
     n&=(n-1); 
     ret++; 
    } 
    return ret; 
} 

Jedes Mal, wenn Sie ein n&=(n-1) Sie den letzten Satz Bit in n beseitigen. Dies benötigt also O (Anzahl der gesetzten Bits) Zeit.

Dies ist schneller als der O (log n), den Sie benötigen würden, wenn Sie jedes Bit getestet haben - nicht jedes Bit ist gesetzt, es sei denn, die Nummer ist 0xFFFFFFFFFFFFFFFF), daher benötigen Sie normalerweise wesentlich weniger Iterationen.

Answer 3

Standard-Antwort in C#:

ulong val = //whatever 
byte count = 0; 

while (val != 0) { 
    if ((val & 0x1) == 0x1) count++; 
    val >>= 1; 
} 

Dieses val ein Bit nach rechts verschiebt, und Schritte count wenn das Bit ganz rechts eingestellt ist. Dies ist ein allgemeiner Algorithmus, der für Ganzzahlen beliebiger Länge verwendet werden kann.