¿Cómo contar el número de bits establecidos en un entero de 32 bits?
https://stackoverflow.com/questions/109023
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
8 bits que representan el número 7 se ven así:
00000111
Se establecen tres bits.
¿Cuáles son los algoritmos para determinar el número de bits establecidos en un entero de 32 bits?
Solución
Esto se conoce como el 'Peso Hamming', 'popcount' o 'suma lateral'.
El "mejor" algoritmo realmente depende de en qué CPU esté y cuál sea su patrón de uso.
Algunas CPU tienen una única instrucción incorporada para hacerlo y otras tienen instrucciones paralelas que actúan sobre vectores de bits.Las instrucciones paralelas (como las de x86 popcnt, en CPU donde sea compatible) será casi con toda seguridad el más rápido.Algunas otras arquitecturas pueden tener una instrucción lenta implementada con un bucle microcodificado que prueba un bit por ciclo (cita necesaria).
Un método de búsqueda de tablas previamente completadas puede ser muy rápido si su CPU tiene una memoria caché grande y/o está realizando muchas de estas instrucciones en un bucle cerrado.Sin embargo, puede verse afectado por el gasto de una 'falta de caché', donde la CPU tiene que recuperar parte de la tabla de la memoria principal.
Si sabe que sus bytes serán en su mayoría 0 o 1, entonces existen algoritmos muy eficientes para estos escenarios.
Creo que un muy buen algoritmo de propósito general es el siguiente, conocido como "algoritmo SWAR paralelo" o "de precisión variable".He expresado esto en un pseudolenguaje tipo C, es posible que necesites ajustarlo para que funcione en un lenguaje en particular (p. ej.usando uint32_t para C++ y >>> en 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;
}
Este tiene el mejor comportamiento en el peor de los casos de cualquiera de los algoritmos discutidos, por lo que manejará de manera eficiente cualquier patrón de uso o valores que le arroje.
Este algoritmo SWAR bit a bit podría paralelizarse en múltiples elementos vectoriales a la vez, en lugar de en un solo registro entero, para acelerar las CPU con SIMD pero sin instrucción popcount utilizable.(p.ej.Código x86-64 que debe ejecutarse en cualquier CPU, no solo en Nehalem o posterior).
Sin embargo, la mejor manera de utilizar instrucciones vectoriales para popcount suele ser mediante el uso de una combinación aleatoria de variables para realizar una búsqueda en la tabla de 4 bits a la vez de cada byte en paralelo.(Los 4 bits indexan una tabla de 16 entradas mantenida en un registro vectorial).
En las CPU Intel, la instrucción popcnt de hardware de 64 bits puede superar a una SSSE3 PSHUFB implementación de bits paralelos por aproximadamente un factor de 2, pero sólo si su compilador lo hace bien.De lo contrario, la ESS puede salir ganando considerablemente.Las versiones más recientes del compilador son conscientes de la popcnt falsa dependencia problema en intel.
Referencias:
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)
Otros consejos
Considere también las funciones integradas de sus compiladores.
En el compilador GNU, por ejemplo, puedes usar:
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
En el peor de los casos, el compilador generará una llamada a una función.En el mejor de los casos, el compilador emitirá una instrucción de CPU para realizar el mismo trabajo más rápido.
Los elementos intrínsecos del CCG funcionan incluso en múltiples plataformas.Popcount se convertirá en algo común en la arquitectura x86, por lo que tiene sentido comenzar a usar lo intrínseco ahora.Otras arquitecturas tienen popularidad desde hace años.
En x86, puede decirle al compilador que puede asumir soporte para popcnt instrucción con -mpopcnt o -msse4.2 para habilitar también las instrucciones vectoriales que se agregaron en la misma generación.Ver Opciones de GCC x86. -march=nehalem (o -march= cualquier CPU que desee que su código asuma y ajuste) podría ser una buena opción.La ejecución del binario resultante en una CPU más antigua provocará un error de instrucción ilegal.
Para optimizar los archivos binarios para la máquina en la que los construye, utilice -march=native (con gcc, clang o ICC).
MSVC proporciona una solución intrínseca para x86 popcnt instrucción, pero a diferencia de gcc, es realmente una instrucción intrínseca de hardware y requiere soporte de hardware.
Usando std::bitset<>::count() en lugar de un incorporado
En teoría, cualquier compilador que sepa cómo realizar popcount de manera eficiente para la CPU de destino debería exponer esa funcionalidad a través de ISO C++. std::bitset<>.En la práctica, es posible que le resulte mejor utilizar el bit-hack AND/shift/ADD en algunos casos para algunas CPU de destino.
Para arquitecturas de destino donde el popcount de hardware es una extensión opcional (como x86), no todos los compiladores tienen un std::bitset que lo aprovecha cuando está disponible.Por ejemplo, MSVC no tiene forma de habilitar popcnt soporte en tiempo de compilación, y siempre usa una búsqueda de tabla, incluso con /Ox /arch:AVX (lo que implica SSE4.2, aunque técnicamente hay un bit de característica separado para popcnt.)
Pero al menos obtienes algo portátil que funciona en todas partes, y con gcc/clang con las opciones de destino correctas, obtienes hardware disponible para arquitecturas que lo admiten.
#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();
}
Ver ensamblaje de gcc, clang, icc y MSVC en el explorador del compilador Godbolt.
x86-64 gcc -O3 -std=gnu++11 -mpopcnt emite esto:
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 emite (para el int versión arg):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
Esta fuente no es específica de x86 ni de GNU en absoluto, pero solo se compila bien para x86 con gcc/clang/icc.
También tenga en cuenta que la alternativa de gcc para arquitecturas sin popcount de una sola instrucción es una búsqueda en la tabla de bytes a la vez.esto no es maravilloso para ARM, por ejemplo.
En mi opinión, la "mejor" solución es aquella que puede ser leída por otro programador (o el programador original dos años después) sin muchos comentarios.Es posible que desee la solución más rápida o inteligente que algunos ya han proporcionado, pero prefiero la legibilidad a la inteligencia en cualquier momento.
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;
}
Si desea más velocidad (y suponiendo que lo documente bien para ayudar a sus sucesores), puede utilizar una búsqueda en tabla:
// 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);
}
Aunque estos dependen de tamaños de tipos de datos específicos, no son tan portátiles.Pero, dado que muchas optimizaciones de rendimiento no son portátiles de todos modos, eso puede no ser un problema.Si desea portabilidad, me quedaría con la solución legible.
Del placer del hacker, pág.66, Figura 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;
}
Se ejecuta en aproximadamente 20 instrucciones (dependiente del arco), sin bifurcaciones.
El deleite del hacker es ¡encantador!Muy recomendable.
Creo que la forma más rápida, sin utilizar tablas de búsqueda y recuento pop-es el siguiente.Cuenta los bits configurados con sólo 12 operaciones.
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;
}
Funciona porque puedes contar el número total de bits configurados dividiéndolos en dos mitades, contando el número de bits configurados en ambas mitades y luego sumándolos.También conocido como Divide and Conquer paradigma.Entremos en detalle..
v = v - ((v >> 1) & 0x55555555);
El número de bits en dos bits puede ser 0b00, 0b01 o 0b10.Intentemos resolver esto en 2 bits.
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
Esto es lo que se requería:la última columna muestra el recuento de bits establecidos en cada par de dos bits.Si el número de dos bits es >= 2 (0b10) entonces and produce 0b01, de lo contrario produce 0b00.
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
Esta afirmación debería ser fácil de entender.Después de la primera operación tenemos el recuento de bits establecidos en cada dos bits, ahora sumamos ese recuento en cada 4 bits.
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
Luego resumimos el resultado anterior, dándonos el recuento total de bits establecidos en 4 bits.La última afirmación es la más complicada.
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
Analicémoslo más...
v + (v >> 4)
Es similar a la segunda declaración;En su lugar, contamos los bits configurados en grupos de 4.Sabemos, debido a nuestras operaciones anteriores, que cada mordisco tiene el recuento de bits establecidos.Veamos un ejemplo.Supongamos que tenemos el byte 0b01000010.Significa que el primer mordisco tiene sus 4 bits configurados y el segundo tiene sus 2 bits configurados.Ahora sumamos esos mordiscos.
0b01000010 + 0b01000000
Nos da el conteo de bits establecidos en un byte, en el primer nibble 0b01100010 y por lo tanto enmascaramos los últimos cuatro bytes de todos los bytes del número (descartándolos).
0b01100010 & 0xF0 = 0b01100000
Ahora cada byte tiene el recuento de bits establecidos.Necesitamos sumarlos todos juntos.El truco consiste en multiplicar el resultado por 0b10101010 que tiene una propiedad interesante.Si nuestro número tiene cuatro bytes, A B C D, resultará en un nuevo número con estos bytes A+B+C+D B+C+D C+D D.Un número de 4 bytes puede tener un máximo de 32 bits configurados, que se pueden representar como 0b00100000.
Todo lo que necesitamos ahora es el primer byte que tiene la suma de todos los bits establecidos en todos los bytes, y lo obtenemos mediante >> 24.Este algoritmo fue diseñado para 32 bit palabras pero se pueden modificar fácilmente para 64 bit palabras.
Si está utilizando Java, el método integrado Integer.bitCount lo haré.
Me aburrí y cronometré mil millones de iteraciones de tres enfoques.El compilador es gcc -O3.La CPU es lo que sea que pongan en la Macbook Pro de primera generación.
El más rápido es el siguiente, con 3,7 segundos:
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] );
}
El segundo lugar es para el mismo código pero buscando 4 bytes en lugar de 2 medias palabras.Eso tomó alrededor de 5,5 segundos.
El tercer lugar lo ocupa el método de "suma lateral", que tardó 8,6 segundos.
El cuarto lugar es para __builtin_popcount() de GCC, con unos vergonzosos 11 segundos.
El método de contar bit a bit fue muchísimo más lento y me aburrí de esperar a que se completara.
Entonces, si lo que más le importa es el rendimiento, utilice el primer enfoque.Si le importa, pero no lo suficiente como para gastar 64 Kb de RAM, utilice el segundo enfoque.De lo contrario, utilice el enfoque legible (pero lento) de un bit a la vez.
Es difícil pensar en una situación en la que querrías utilizar el enfoque de jugar con los bits.
Editar:Resultados similares aquí.
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;
}
Déjame explicarte este algoritmo.
Este algoritmo se basa en el algoritmo divide y vencerás.Supongamos que hay un entero de 8 bits 213 (11010101 en binario), el algoritmo funciona así (cada vez fusiona dos bloques vecinos):
+-------------------------------+
| 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)
+-------------------------------+
Esta es una de esas preguntas en las que resulta útil conocer su microarquitectura.Acabo de cronometrar dos variantes en gcc 4.3.3 compiladas con -O3 usando C++ en líneas para eliminar la sobrecarga de llamadas a funciones, mil millones de iteraciones, manteniendo la suma acumulada de todos los recuentos para garantizar que el compilador no elimine nada importante, usando rdtsc para cronometrar ( ciclo de reloj preciso).
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;
}
El Hacker's Delight sin modificar requirió 12,2 gigaciclos.Mi versión paralela (que cuenta el doble de bits) se ejecuta en 13,0 gigaciclos.Transcurrieron 10,5 s en total para ambos juntos en un Core Duo de 2,4 GHz.25 gigaciclos = poco más de 10 segundos a esta frecuencia de reloj, así que estoy seguro de que mis tiempos son correctos.
Esto tiene que ver con las cadenas de dependencia de instrucciones, que son muy malas para este algoritmo.Casi podría duplicar la velocidad nuevamente usando un par de registros de 64 bits.De hecho, si fuera inteligente y agregara x+y un poco antes, podría reducir algunos turnos.La versión de 64 bits con algunos pequeños ajustes saldría casi igualada, pero volvería a contar el doble de bits.
Con registros SIMD de 128 bits, otro factor de dos, y los conjuntos de instrucciones SSE a menudo también tienen atajos inteligentes.
No hay ninguna razón para que el código sea especialmente transparente.La interfaz es simple, se puede hacer referencia al algoritmo en línea en muchos lugares y se puede realizar una prueba unitaria integral.El programador que lo encuentre podría incluso aprender algo.Estas operaciones con brocas son extremadamente naturales a nivel de máquina.
Bien, decidí probar la versión modificada de 64 bits.Para este tamaño de (largo sin firmar) == 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;
}
Eso parece correcto (aunque no lo estoy probando con cuidado).Ahora los tiempos son de 10,70 gigaciclos / 14,1 gigaciclos.Esta última cifra sumó 128 mil millones de bits y corresponde a 5,9 segundos transcurridos en esta máquina.La versión no paralela se acelera un poquito porque estoy ejecutando en modo de 64 bits y le gustan un poco más los registros de 64 bits que los de 32 bits.
Veamos si hay un poco más de canalización de OOO aquí.Esto fue un poco más complicado, así que probé un poco.Cada término por sí solo suma 64, todos combinados suman 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;
}
Me emocioné por un momento, pero resulta que gcc está jugando trucos en línea con -O3 a pesar de que no estoy usando la palabra clave en línea en algunas pruebas.Cuando dejé que gcc jugara una mala pasada, mil millones de llamadas a pop4() tomaban 12,56 gigaciclos, pero determiné que estaba plegando argumentos como expresiones constantes.Un número más realista parece ser 19,6 gc, lo que supone una aceleración adicional del 30 %.Mi ciclo de prueba ahora se ve así, asegurándose de que cada argumento sea lo suficientemente diferente como para evitar que gcc juegue una mala pasada.
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();
Transcurrieron 256 mil millones de bits sumados en 8,17s.Funciona en 1,02 s para 32 millones de bits según lo evaluado en la búsqueda de tablas de 16 bits.No puedo comparar directamente, porque el otro banco no proporciona una velocidad de reloj, pero parece que le he quitado los mocos a la edición de tabla de 64 KB, lo cual es un uso trágico del caché L1 en primer lugar.
Actualizar:Decidí hacer lo obvio y crear pop6() agregando cuatro líneas duplicadas más.Salió a 22,8 gc, transcurrieron 384 mil millones de bits sumados en 9,5 s.Entonces hay otro 20% ahora a 800 ms para 32 mil millones de bits.
¿Por qué no dividir iterativamente por 2?
count = 0
while n > 0
if (n % 2) == 1
count += 1
n /= 2
Estoy de acuerdo en que este no es el más rápido, pero "mejor" es algo ambiguo.Sin embargo, yo diría que "mejor" debería tener un elemento de claridad.
El juego de bits de Hacker's Delight se vuelve mucho más claro cuando escribes los patrones de bits.
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;
}
El primer paso suma los bits pares a los impares, produciendo una suma de bits en cada dos.Los otros pasos agregan fragmentos de orden superior a fragmentos de orden inferior, duplicando el tamaño del fragmento por completo, hasta que tengamos el recuento final que ocupe todo el int.
Para un punto medio feliz entre un 232 tabla de búsqueda e iterando a través de cada bit individualmente:
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;
}
No es la mejor ni la más rápida solución, pero encontré la misma pregunta en mi camino y comencé a pensar y pensar.Finalmente me di cuenta de que se puede hacer así si obtienes el problema desde el punto de vista matemático y dibujas una gráfica, luego descubres que es una función que tiene alguna parte periódica y luego te das cuenta de la diferencia entre los períodos...así que aquí tienes:
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);
}
}
Esto se puede hacer en O(k), dónde k es el número de bits establecidos.
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
La función que busca a menudo se denomina "suma lateral" o "recuento de población" de un número binario.Knuth lo analiza en el fascículo 1A anterior, páginas 11-12 (aunque hubo una breve referencia en el Volumen 2, 4.6.3-(7).)
El lugar clásico es el artículo de Peter Wegner "Una técnica para contar unos en una computadora binaria", del Comunicaciones de la ACM, Volumen 3 (1960) Número 5, página 322.Allí ofrece dos algoritmos diferentes, uno optimizado para números que se espera que sean "escasos" (es decir, que tengan un número pequeño de unos) y otro para el caso opuesto.
Algunas preguntas abiertas: -
- ¿Si el número es negativo entonces?
- Si el número es 1024, entonces el método de "división iterativa entre 2" se repetirá 10 veces.
Podemos modificar el algoritmo para admitir el número negativo de la siguiente manera: -
count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
count += 1
n /= 2
return count
Ahora, para superar el segundo problema, podemos escribir el algo como: -
int bit_count(int num)
{
int count=0;
while(num)
{
num=(num)&(num-1);
count++;
}
return count;
}
para referencia completa ver:
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;
}
Pienso que el Brian Kernighan El método también será útil...Pasa por tantas iteraciones como bits establecidos.Entonces, si tenemos una palabra de 32 bits con solo el bit alto configurado, entonces solo pasará una vez por el bucle.
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;
}
Publicado en 1988, el lenguaje de programación C 2ª edición.(por Brian W.Kernighan y Dennis M.Ritchie) menciona esto en el ejercicio 2-9.El 19 de abril de 2006, Don Knuth me señaló que este método "fue publicado por primera vez por Peter Wegner en CACM 3 (1960), 322.(También descubierto de forma independiente por Derrick Lehmer y publicado en 1964 en un libro editado por Beckenbach)".
Utilizo el siguiente código que es más intuitivo.
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
Lógica:n & (n-1) restablece el último bit establecido de n.
PD:Sé que esta no es la solución O(1), aunque es una solución interesante.
¿Qué quieres decir con "Mejor algoritmo"?¿El código en corto o el código en ayunas?Su código se ve muy elegante y tiene un tiempo de ejecución constante.El código también es muy corto.
Pero si la velocidad es el factor principal y no el tamaño del código, entonces creo que lo siguiente puede ser más rápido:
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 );
}
Creo que esto no será más rápido para un valor de 64 bits, pero un valor de 32 bits puede ser más rápido.
Escribí una macro rápida de conteo de bits para máquinas RISC alrededor de 1990.No utiliza aritmética avanzada (multiplicación, división, %), recuperaciones de memoria (demasiado lentas), ramas (demasiado lentas), pero sí supone que la CPU tiene un cambiador de barril de 32 bits (en otras palabras, >> 1 y >> 32 toman la misma cantidad de ciclos). Se supone que las constantes pequeñas (como 6, 12, 24) no cuestan nada para cargar en los registros, o se almacenan de forma temporal y se reutilizan una y otra vez.
Con estas suposiciones, cuenta 32 bits en aproximadamente 16 ciclos/instrucciones en la mayoría de las máquinas RISC.Tenga en cuenta que 15 instrucciones/ciclos está cerca de un límite inferior en el número de ciclos o instrucciones, porque parece que se necesitan al menos 3 instrucciones (máscara, cambio, operador) para reducir el número de sumandos a la mitad, por lo que log_2(32) = 5, 5 x 3 = 15 instrucciones es un límite casi inferior.
#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;
Aquí tienes un secreto para el primer y más complejo paso:
input output
AB CD Note
00 00 = AB
01 01 = AB
10 01 = AB - (A >> 1) & 0x1
11 10 = AB - (A >> 1) & 0x1
entonces, si tomo la primera columna (A) arriba, la cambio 1 bit a la derecha y la resto de AB, obtengo la salida (CD).La extensión a 3 bits es similar;puedes comprobarlo con una tabla booleana de 8 filas como la mía de arriba si lo deseas.
- don gillies
Si estás usando C++, otra opción es usar metaprogramación de plantillas:
// 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;
}
el uso sería:
// 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 )
Por supuesto, podría ampliar aún más esta plantilla para utilizar diferentes tipos (incluso el tamaño de bits con detección automática), pero lo he mantenido simple para mayor claridad.
editar:Olvidé mencionar que esto es bueno porque debería funciona en cualquier compilador de C++ y básicamente simplemente desenrolla el bucle si se utiliza un valor constante para el recuento de bits (en otras palabras, estoy bastante seguro de que es el método general más rápido que encontrarás)
Me gusta especialmente este ejemplo del archivo Fortune:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333)
- (((x)>>3)&0x11111111))
¡Me gusta más porque es muy bonito!
JavaJDK1.5
Entero.bitCount(n);
donde n es el número cuyos unos se van a contar.
comprobar también,
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);
}
Encontré una implementación del conteo de bits en una matriz usando instrucciones SIMD (SSSE3 y AVX2).Tiene un rendimiento entre 2 y 2,5 veces mejor que si utilizara la función intrínseca __popcnt64.
Versión SSSE3:
#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];
}
Versión AVX2:
#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];
}
Siempre uso esto en programación competitiva y es fácil de escribir y eficiente:
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
Existen muchos algoritmos para contar los bits configurados;¡Pero creo que el mejor es el más rápido!Puedes ver el detalle en esta página:
Te sugiero este:
Contar bits configurados en palabras de 14, 24 o 32 bits usando instrucciones de 64 bits
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;
Este método requiere una CPU de 64 bits con una división de módulo rápida para ser eficiente.La primera opción requiere sólo 3 operaciones;la segunda opción toma 10;y la tercera opción toma 15.
Solución rápida de C# que utiliza una tabla precalculada de recuentos de bytes y bits con ramificación según el tamaño de entrada.
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
};
}
Aquí hay un módulo portátil (ANSI-C) que puede comparar cada uno de sus algoritmos en cualquier arquitectura.
¿Su CPU tiene bytes de 9 bits?No hay problema :-) Por el momento implementa 2 algoritmos, el algoritmo K&R y una tabla de búsqueda de bytes.La tabla de búsqueda es en promedio 3 veces más rápida que el algoritmo K&R.Si alguien puede encontrar una manera de hacer que el algoritmo "Hacker's Delight" sea portátil, no dude en agregarlo.
#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 bits o no?Acabo de encontrar este método en Java después de leer "descifrando la entrevista de codificación" 4ª edición ejercicio 5.5 (capítulo 5:Manipulación de bits).Si el bit menos significativo es de 1 incremento count, luego desplaza el número entero hacia la derecha.
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
Creo que esta es más intuitiva que las soluciones con 0x33333333 constante por muy rápidas que sean.Depende de su definición de "mejor algoritmo".
