Contare il numero di bit in un intero a 64 bit (lungo, grande)?

Question

Ho letto il numero this SO question di 32 bit, ma che dire dei numeri a 64 bit? Dovrei semplicemente mascherare i 4 byte superiori e inferiori, eseguire il conteggio sui 32 bit e quindi aggiungerli insieme?

Answer 1

È possibile trovare la versione a 64 bit qui http://en.wikipedia.org/wiki/Hamming_weight

E 'qualcosa di simile

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

Si tratta di una versione a 64 bit del modulo di codice qui How to count the number of set bits in a 32-bit integer?

Utilizzando il suggerimento di Joshua mi avrebbe trasformato in questo:

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: Ho trovato un errore durante il test della versione a 32 bit. Ho aggiunto le parentesi mancanti. La somma dovrebbe essere fatto prima bit a bit &, nell'ultima riga

EDIT2 Aggiunto versione più sicura per Ulong

Answer 2

Un veloce (e più portabile di utilizzare le estensioni del compilatore non standard) modo:

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

Ogni volta che fate un n&=(n-1) si elimina il bit ultima serie in n. Quindi questo richiede il tempo O (numero di bit impostati).

Questo è più veloce di O (log n) che sarebbe necessario se si testasse ogni bit - non ogni bit è impostato a meno che il numero sia 0xFFFFFFFFFFFFFFFF), quindi in genere sono necessarie molte meno iterazioni.

Answer 3

risposta standard in C#:

ulong val = //whatever 
byte count = 0; 

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

Questo sposta val destra di un bit, e incrementi count se è impostato il bit più a destra. Questo è un algoritmo generale che può essere utilizzato per qualsiasi numero intero di lunghezza.