algorithm - tipo - ¿Cómo contar el número de bits establecidos en un entero de 32 bits?
tipos de datos enteros en programacion (30)
8 bits que representan el número 7 se ven así:
00000111
Se establecen tres bits.
¿Qué son los algoritmos para determinar el número de bits establecidos en un entero de 32 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 esto no es lo más rápido, pero "lo mejor" es algo ambiguo. Aunque argumentaría que "lo mejor" debería tener un elemento de claridad.
Creo que la forma más rápida, sin utilizar tablas de búsqueda y popcount, es la siguiente. Cuenta los bits establecidos con solo 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 puede contar el número total de bits establecidos dividiendo en dos mitades, contando el número de bits establecidos en ambas mitades y luego sumándolos. También conocido como paradigma Divide and Conquer . Vamos a entrar en detalles ..
v = v - ((v >> 1) & 0x55555555);
El número de bits en dos bits puede ser 0b00 , 0b01 o 0b10 . Vamos a tratar de 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 conteo de bits establecidos en cada par de dos bits. Si el número de dos bits es >= 2 (0b10) and produce 0b01 , de lo contrario, produce 0b00 .
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
Esta declaración debe ser fácil de entender. Después de la primera operación tenemos el conteo de bits establecidos en cada dos bits, ahora resumimos ese conteo en cada 4 bits.
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
Luego, resumimos el resultado anterior, lo que nos da 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;
Vamos a desglosarlo aún más ...
v + (v >> 4)
Es similar a la segunda declaración; estamos contando los bits establecidos en grupos de 4 en su lugar. Sabemos, debido a nuestras operaciones anteriores, que cada nibble tiene la cuenta de bits establecidos. Veamos un ejemplo. Supongamos que tenemos el byte 0b01000010 . Significa que el primer nibble tiene su conjunto de 4 bits y el segundo tiene su conjunto de 2 bits. Ahora añadimos esos mordiscos juntos.
0b01000010 + 0b01000000
Nos da el recuento de bits establecidos en un byte, en el primer nibble 0b01100010 y, por lo tanto, enmascaramos los últimos cuatro bytes de todos los bytes en el número (descartándolos).
0b01100010 & 0xF0 = 0b01100000
Ahora cada byte tiene el conteo de bits establecidos en él. Necesitamos sumarlos todos juntos. El truco es multiplicar el resultado por 0b10101010 que tiene una propiedad interesante. Si nuestro número tiene cuatro bytes, ABCD , se obtendrá un nuevo número con estos bytes A+B+C+D B+C+D C+DD . Un número de 4 bytes puede tener un máximo de 32 bits establecido, que se puede 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 por >> 24 . Este algoritmo fue diseñado para palabras de 32 bit pero puede modificarse fácilmente para palabras de 64 bit .
En mi opinión, la "mejor" solución es la que puede leer otro programador (o el programador original dos años después) sin comentarios importantes. Es posible que desee la solución más rápida o más inteligente que algunos ya han proporcionado, pero prefiero la legibilidad sobre 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), podría usar una búsqueda en la 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 se basan en 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 todas formas, eso puede no ser un problema. Si quieres portabilidad, me quedo con la solución legible.
Esta es una de esas preguntas donde te ayuda conocer tu microarquitectura. Acabo de cronometrar dos variantes bajo gcc 4.3.3 compilado con -O3 usando líneas C ++ para eliminar la sobrecarga de llamadas a funciones, mil millones de iteraciones, manteniendo la suma de todos los conteos para asegurar que el compilador no elimine nada importante, usando rdtsc para el tiempo ( 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 no modificado tomó 12.2 gigaciclos. Mi versión paralela (contando el doble de bits) se ejecuta en 13.0 gigaciclos. 10.5s en total transcurrieron para ambos juntos en un Core Duo de 2.4GHz. 25 gigaciclos = poco más de 10 segundos en 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 usando un par de registros de 64 bits. De hecho, si era inteligente y añadía x + ya poco antes, podría afeitarme algunos turnos. La versión de 64 bits con algunos pequeños ajustes saldría casi igual, pero contaría el doble de bits nuevamente.
Con los registros SIMD de 128 bits, otro factor más de dos, y los conjuntos de instrucciones SSE a menudo también tienen atajos inteligentes.
No hay 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 es susceptible de una prueba unitaria exhaustiva. El programador que se tropieza con eso podría incluso aprender algo. Estas operaciones de bits son extremadamente naturales en el nivel de la máquina.
OK, decidí acomodar la versión de 64 bits modificada. Para esto one 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; }
Eso parece correcto (aunque no estoy probando con cuidado). Ahora los tiempos salen en 10.70 gigacycles / 14.1 gigacycles. Ese número posterior sumó 128 mil millones de bits y corresponde a los 5.9s transcurridos en esta máquina. La versión no paralela se acelera un poco porque ejecuto en modo de 64 bits y le gustan los registros de 64 bits un poco mejor que los registros de 32 bits.
Vamos a ver si hay un poco más de tubería de OOO que se tendrá aquí. Esto fue un poco más complicado, así que en realidad probé un poco. Cada término solo suma a 64, todo suma sumada a 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; }
Estuve emocionado por un momento, pero resulta que gcc está jugando trucos en línea con -O3 aunque no estoy usando la palabra clave en línea en algunas pruebas. Cuando dejo que gcc juegue trucos, mil millones de llamadas a pop4 () toman 12.56 gigaciclos, pero determiné que estaba plegando argumentos como expresiones constantes. Un número más realista parece ser 19.6 gc para otro 30% de aceleración. Mi ciclo de prueba ahora se ve así, asegurándome de que cada argumento sea lo suficientemente diferente como para evitar que gcc haga trucos.
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 mil millones de bits sumados en 8.17s transcurridos. Funciona hasta 1.02s para 32 millones de bits como referencia en la búsqueda de tablas de 16 bits. No se puede comparar directamente, porque el otro banco no da una velocidad de reloj, pero parece que he eliminado el moco de la edición de la tabla de 64 KB, que es un uso trágico del caché L1 en primer lugar.
Actualización: decidió hacer lo obvio y crear pop6 () agregando cuatro líneas duplicadas más. Llegó a 22.8gc, 384 mil millones de bits sumados en 9.5 s transcurridos. Así que hay otro 20% Ahora a 800 ms para 32 mil millones de bits.
Esto se conoce como '' Peso Hamming '', ''popcount'' o ''adición lateral''.
El "mejor" algoritmo realmente depende de en qué CPU se encuentre y cuál sea su patrón de uso.
Algunas CPU tienen una sola instrucción incorporada para hacerlo y otras tienen instrucciones paralelas que actúan sobre vectores de bits. Las instrucciones paralelas (como el popcnt de x86, en las CPU en las que se admite) seguramente serán las más rápidas. Algunas otras arquitecturas pueden tener una instrucción lenta implementada con un bucle microcodificado que prueba un bit por ciclo ( cita requerida ).
Un método de búsqueda de tabla previamente rellenado puede ser muy rápido si su CPU tiene una memoria caché grande y / o si está siguiendo muchas de estas instrucciones en un ciclo cerrado. Sin embargo, puede sufrir debido al costo 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 mayormente 0 o mayormente 1, entonces hay algoritmos muy eficientes para estos escenarios.
Creo que un algoritmo de propósito general muy bueno es el siguiente, conocido como ''algoritmo SWAR'' paralelo ''o'' variable-precisión ''. He expresado esto en un pseudo lenguaje similar a C, es posible que deba ajustarlo para que funcione con un idioma en particular (por ejemplo, utilizando 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 analizados, por lo que tratará de manera eficiente con cualquier patrón de uso o valores que le arrojemos.
Este algoritmo SWAR en modo bit a bit podría paralelizarse para realizarse en múltiples elementos vectoriales a la vez, en lugar de en un solo registro de enteros, para una aceleración en las CPU con SIMD pero sin instrucción popcount utilizable. (por ejemplo, el código x86-64 que debe ejecutarse en cualquier CPU, no solo en Nehalem o posterior).
Sin embargo, la mejor manera de usar instrucciones vectoriales para popcount es usualmente usando una mezcla aleatoria para hacer una búsqueda de tabla de 4 bits a la vez de cada byte en paralelo. (Los 4 bits indexan una tabla de 16 entradas contenida en un registro vectorial).
En las CPU Intel, la instrucción popcnt de 64 bits de hardware puede superar a una PSHUFB SSSE3 PSHUFB bits en paralelo en aproximadamente un factor de 2, pero solo si su compilador lo hace bien . De lo contrario SSE puede salir significativamente por delante. Las versiones más recientes del compilador son conscientes del problema de dependencia falsa popcnt 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)
Los giros de bits de The Hacker''s Delight se vuelven mucho más claros cuando se escriben 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 agrega los bits pares a los bits impares, produciendo una suma de bits en cada dos. Los otros pasos agregan trozos de alto orden a los de bajo orden, duplicando el tamaño del trozo hasta el final, hasta que el recuento final ocupe todo el int.
Me aburrí y cronometré mil millones de iteraciones de tres enfoques. El compilador es gcc -O3. CPU es lo que ponen en la 1ra generación de Macbook Pro.
Lo más rápido es lo siguiente, a 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 va al mismo código pero busca 4 bytes en lugar de 2 medias palabras. Eso llevó alrededor de 5,5 segundos.
El tercer lugar es para el enfoque de ''adición lateral'' de twitsdling de bits, que tomó 8,6 segundos.
El cuarto lugar es para __builtin_popcount () de GCC, en un vergonzoso 11 segundos.
El enfoque del conteo de bit a bit fue muy lento, y me aburrí de esperar a que se completara.
Entonces, si te interesa el rendimiento por encima de todo, entonces utiliza el primer enfoque. Si te importa, pero no lo suficiente como para gastar 64Kb de RAM en él, usa 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 se quiera utilizar el enfoque de la manipulación de bits.
Edición: resultados similares here .
No es la mejor solución o la más rápida, pero encontré la misma pregunta en mi camino y empecé a pensar y pensar. Finalmente, me di cuenta de que se puede hacer así si se obtiene el problema del lado matemático y se dibuja una gráfica, luego se encuentra que es una función que tiene una parte periódica, y luego se da cuenta de la diferencia entre los períodos ... aqui 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);
}
}
Para un medio feliz entre una tabla de búsqueda de 32 y una iteración 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;
}
Si está utilizando Java, el método integrado Integer.bitCount lo hará.
También considere 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 la CPU para hacer el mismo trabajo más rápido.
Los intrínsecos de GCC incluso funcionan en múltiples plataformas. Popcount se convertirá en la corriente principal de la arquitectura x86, por lo que tiene sentido comenzar a usar el intrínseco ahora. Otras arquitecturas tienen el popcount desde hace años.
En x86, puede decirle al compilador que puede asumir la compatibilidad con la instrucción -mpopcnt 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 asuma y sintonice su código) 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 hacer binarios optimizados para la máquina en la que los construyes, usa -march=native (con gcc, clang o ICC).
MSVC proporciona una intrínseca para la instrucción popcnt x86 , pero a diferencia de gcc, es realmente una intrínseca para la instrucción de hardware y requiere soporte de hardware.
Usando std::bitset<>::count() lugar de un incorporado
En teoría, cualquier compilador que sepa cómo hacer 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 esté mejor con el pirateo AND / shift / ADD en algunos casos para algunas CPU de destino.
Para las arquitecturas de destino donde el hardware popcount es una extensión opcional (como x86), no todos los compiladores tienen un std::bitset que lo aproveche cuando esté disponible. Por ejemplo, MSVC no tiene manera de habilitar el soporte de popcnt 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 una cuenta de hardware para las 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();
}
Vea asm 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 -O3 gcc -O3 -std=gnu++11 emite (para la versión int 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 o específica de GNU en absoluto, sino que solo compila bien para x86 con gcc / clang / icc.
También tenga en cuenta que el respaldo de gcc para arquitecturas sin popcount de instrucción única es una búsqueda de tabla de bytes en una vez. Esto no es maravilloso para ARM, por ejemplo .
De Hacker''s Delight, p. 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;
}
Ejecuta en ~ 20-ish instrucciones (dependiente del arco), sin ramificación.
Hacker''s Delight es una delicia! Muy recomendable.
Aquí hay un módulo portátil (ANSI-C) que puede evaluar cada uno de sus algoritmos en cualquier arquitectura.
¿Tu CPU tiene 9 bit bytes? No hay problema :-) En este 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
Escribí una macro de bitcount rápido para máquinas RISC en aproximadamente 1990. No usa aritmética avanzada (multiplicación, división,%), captura de memoria (demasiado lenta), ramas (demasiado lenta), pero asume que la CPU tiene una Palanca de cambios de barril de 32 bits (en otras palabras, >> 1 y >> 32 toman la misma cantidad de ciclos). Supone que las constantes pequeñas (como 6, 12, 24) no cuestan nada para cargar en los registros o se almacenan En temporarios y reutilizados 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án cerca de un límite inferior en el número de ciclos o instrucciones, ya que parece tomar al menos 3 instrucciones (máscara, cambio, operador) para reducir a la mitad el número de sumandos, por lo tanto log_2 (32) = 5, 5 x 3 = 15 instrucciones es casi un límite 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í es 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
así que si tomo la primera columna (A) anterior, la desplazo a la derecha 1 bit y la resto de AB, obtengo la salida (CD). La extensión a 3 bits es similar; puedes verificarlo con una tabla booleana de 8 filas como la mía de arriba si lo deseas.
- Don gillies
Java JDK1.5
Integer.bitCount (n);
donde n es el número cuyos 1''s deben ser contados.
ver 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);
}
Me encanta este ejemplo del archivo de fortuna:
#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 bonita!
Pocas preguntas abiertas: -
- Si el número es negativo entonces?
- Si el número es 1024, el método de "dividir iterativamente por 2" iterará 10 veces.
Podemos modificar el algo 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 algo así 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
Si está utilizando C ++, otra opción es utilizar la 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 expandir aún más esta plantilla para usar diferentes tipos (incluso el tamaño de bits de detección automática) pero lo he mantenido simple para mayor claridad.
edit: olvidé mencionar que esto es bueno porque debería funcionar en cualquier compilador de C ++ y básicamente simplemente desenrolla su bucle si se usa un valor constante para el conteo de bits (en otras palabras, estoy bastante seguro de que es el método general más rápido) encontrarás)
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();
}
Solución rápida de C # usando una tabla precalculada de conteos de bits de bytes con bifurcación en 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
};
}
Yo uso 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 esto no es una solución O (1), aunque sea 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, creo que el seguimiento 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.
32 bits o no? Acabo de venir con este método en Java después de leer " craqueo de la entrevista de codificación ", cuarta edición del ejercicio 5.5 (capítulo 5: Manipulación de bits). Si el bit menos significativo es 1 incremento count, desplace a la derecha el entero.
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 constante 0x33333333 sin importar qué tan rápido sean. Depende de su definición de "mejor algoritmo".
Creo que el método de Brian Kernighan también será útil ... Pasa por tantas iteraciones como bits establecidos. Entonces, si tenemos una palabra de 32 bits con solo el bit alto establecido, 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 2da ed. (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 por Derrick Lehmer y publicado en 1964 en un libro editado por Beckenbach)
Encontré una implementación de conteo de bits en una matriz con el uso de instrucciones SIMD (SSSE3 y AVX2). Tiene un rendimiento 2-2.5 veces mejor que si usara 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];
}
Esto se puede hacer en O(k), donde kse establece el número de bits.
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
Hay muchos algoritmos para contar los bits establecidos; ¡Pero creo que el mejor es el más rápido! Puedes ver el detalle en esta página:
Sugiero este:
El recuento de bits se establece en palabras de 14, 24 o 32 bits mediante 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 división de módulo rápido para ser eficiente. La primera opción toma solo 3 operaciones; la segunda opción toma 10; y la tercera opción toma 15.
La función que está buscando a menudo se denomina "suma lateral" o "recuento de población" de un número binario. Knuth lo analiza en el pre-fascículo 1A, pp11-12 (aunque hubo una breve referencia en el volumen 2, 4.6.3- (7).)
El locus classicus es el artículo de Peter Wegner "Una técnica para contarlos en una computadora binaria", de Comunicaciones de la ACM , Volumen 3 (1960), Número 5, página 322 . Da dos algoritmos diferentes allí, uno optimizado para los números que se espera sea "disperso" (es decir, tiene un número pequeño de unos) y otro para el caso opuesto.
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;
}
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 de dividir y vencer. Supongamos que hay un entero 213 de 8 bits (11010101 en binario), el algoritmo funciona así (cada vez que se combinan 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)
+-------------------------------+