¿Contar el número de bits en un entero de 64 bits (largo, grande)?

Question

He leído this SO question acerca de 32 bits, pero ¿qué pasa con los números de 64 bits? ¿Debo enmascarar los 4 bytes superiores e inferiores, realizar el conteo de los 32 bits y luego sumarlos?

Answer 1

Puede encontrar la versión de 64 bits aquí http://en.wikipedia.org/wiki/Hamming_weight

Es algo como esto

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

Ésta es una versión de 64 bits de la clave aquí How to count the number of set bits in a 32-bit integer?

El uso de la sugerencia de Joshua me transformaría en esto:

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: Encontré un error al probar la versión de 32 bits. Agregué paréntesis faltantes. La suma debe hacerse antes de bit a bit &, en la última línea

Edit2 Añadida versión más seguro para ULONG

Answer 2

Un rápido (y más portátil que el uso de extensiones del compilador no estándar) forma:

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

Cada vez que haces un n&=(n-1) se elimina el último conjunto de bits en n. Por lo tanto, esto toma el tiempo O (número de bits establecidos).

Esto es más rápido que el O (log n) que necesitaría si probara cada bit - no todos los bits están configurados a menos que el número sea 0xFFFFFFFFFFFFFFFF), por lo tanto, generalmente necesita muchas iteraciones.

Answer 3

respuesta estándar en C#:

ulong val = //whatever 
byte count = 0; 

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

Esto desplaza val derecha un bit, y los incrementos count si se establece el bit más a la derecha. Este es un algoritmo general que se puede usar para cualquier entero de longitud.