Como contar o número de bits definidos em um inteiro de 32 bits?
https://stackoverflow.com/questions/109023
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
8 bits representando o olhar número 7 como esta:
00000111
Três bits são definidos.
O que são algoritmos para determinar o número de bits definidos em um inteiro de 32 bits?
Solução
Esta é conhecida como a ' Hamming Peso ', 'popcount' ou 'lado disso' .
O 'melhor' algoritmo realmente depende de qual CPU você está e qual o seu padrão de uso é.
Alguns CPUs tem um único embutido instrução para fazê-lo e os outros têm instruções paralelas que atuam em vetores bits. As instruções paralelas (como popcnt do x86, em CPUs onde é suportado) quase certamente será mais rápido. Algumas outras arquiteturas podem ter uma instrução lento implementado com um circuito de microcódigo que testa um pouco por ciclo ( carece de fontes? ).
A pré-preenchido pode ser muito rápido se o seu CPU tem um grande cache e / ou você está fazendo um monte de estas instruções em um loop apertado. No entanto, pode sofrer por causa da despesa de um 'cache miss', onde a CPU tem que buscar alguma da tabela da memória principal.
Se você sabe que seu bytes será principalmente 0 de ou quase 1s, então existem algoritmos muito eficientes para esses cenários.
Eu acredito que um algoritmo muito bom propósito geral é o seguinte, conhecido como 'paralelo' ou 'algoritmo SWAR variável de precisão'. Eu expressei isso em um C-como a linguagem pseudo, pode ser necessário ajustá-lo para trabalhar para uma linguagem particular (por exemplo, usando uint32_t para C ++ e >>> em 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;
}
Isto tem o melhor comportamento de pior caso de qualquer um dos algoritmos discutidos, por isso vai lidar eficientemente com qualquer padrão de uso ou valores que você jogue com ele.
Este algoritmo bit a bit-SWAR pode paralelizar a ser feito em vários elementos do vetor de uma só vez, em vez de em um único registo inteiro, para um aumento de velocidade em CPUs com SIMD, mas nenhuma instrução popcount utilizável. (Por exemplo x86-64 código que tem de rodar em qualquer CPU, não apenas Nehalem ou mais tarde.)
No entanto, a melhor maneira de usar instruções vetor para popcount é geralmente usando uma variável-shuffle para fazer uma tabela de lookup para 4 bits por vez de cada byte em paralelo. (O índice de 4 bits de uma mesa de entrada 16 realizada num registo vector).
Em Intel CPUs, a instrução hardware de 64 bits POPCNT pode superar um href="http://wm.ite.pl/articles/sse-popcount.html" implementação bit paralelo SSSE3 PSHUFB por um fator de 2, mas apenas se o seu compilador recebe-lo apenas para a direita. Caso contrário SSE pode sair significativamente à frente. As versões mais recentes do compilador estão cientes do POPCNT falsa dependência problema no Intel .
Referências:
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)
Outras dicas
Considere também o built-in funções de seus compiladores.
No compilador GNU, por exemplo, você pode apenas usar:
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
No pior dos casos o compilador irá gerar uma chamada para uma função. No melhor dos casos o compilador irá emitir uma instrução de CPU para fazer o mesmo trabalho mais rápido.
Os intrínsecos do CCG mesmo trabalhar em múltiplas plataformas. Popcount vai se tornar mainstream na arquitetura x86, por isso faz sentido para começar a usar o intrínseco agora. Outras arquiteturas têm a popcount durante anos.
Em x86, você pode dizer ao compilador que ele pode assumir suporte para a instrução popcnt com -mpopcnt ou -msse4.2 para também permitir que as instruções vetoriais que foram adicionados na mesma geração. Consulte GCC x 86 opções . -march=nehalem (ou o que quer que -march= CPU você quiser que seu código para assumir e para sintonizar para) poderia ser uma boa escolha. Executando o binário resultante em uma CPU mais velhos irá resultar em uma falha de-instrução ilegal.
Para fazer binários otimizados para a máquina que você construir-los, uso -march=native (com gcc, clang, ou ICC).
MSVC fornece uma intrínseca para a instrução x86 popcnt , mas gcc ao contrário, é realmente uma intrínseca para a instrução de hardware e requer suporte de hardware.
Usando std::bitset<>::count() em vez de um built-in
Em teoria, qualquer compilador que sabe como popcount eficiente para a CPU alvo deve expor essa funcionalidade através de ISO C ++ std::bitset<> . Na prática, você pode ser melhor fora com o bit-hack E / turno / ADD em alguns casos, para algumas CPUs-alvo.
Para arquiteturas-alvo onde popcount hardware é uma extensão opcional (como x86), nem todos os compiladores têm uma std::bitset que leva vantagem disso quando disponível. Por exemplo, MSVC não tem maneira de ativar o suporte popcnt em tempo de compilação, e sempre usa uma tabela de pesquisa , mesmo com /Ox /arch:AVX (que implica SSE4.2, embora tecnicamente não é um pouco recurso separado para popcnt.)
Mas pelo menos você tem algo portátil que funciona em qualquer lugar, e com gcc / clang com as opções alvo certo, você começa popcount hardware para arquiteturas que o suportam.
#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();
}
Veja asm de gcc, clang, ICC, e MSVC na Godbolt compilador explorador.
gcc -O3 -std=gnu++11 -mpopcnt x86-64 emite o seguinte:
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
emite gcc -O3 -std=gnu++11 PowerPC64 (para a versão int arg):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
Esta fonte não é x86-específica ou específicas do GNU em tudo, mas apenas compila bem para x86 com gcc / clang / ICC.
Observe também que fallback do gcc para arquiteturas sem popcount-instrução individual é uma pesquisa de tabela byte-a-um-tempo. Isso não é maravilhoso para ARM, por exemplo .
Na minha opinião, a solução "melhor" é a única que pode ser lido por outro programador (ou o programador original, dois anos depois) sem comentários copiosas. Você pode muito bem querer a solução mais rápida ou mais inteligente que alguns já fornecidos, mas eu prefiro legibilidade sobre esperteza qualquer 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;
}
Se você quiser mais velocidade (e supondo que você documentá-lo bem para ajudar seus sucessores), você pode usar uma consulta à tabela:
// 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);
}
Embora estes dependem de tamanhos de tipo de dados específico para que eles não são tão portátil. Mas, uma vez que muitas otimizações de desempenho não são portáteis de qualquer maneira, isso pode não ser um problema. Se você quer portabilidade, eu ia ficar à solução legível.
partir do Hacker 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;
}
Executa em ~ instruções 20-ish (arco dependentes), nenhuma ramificação.
prazer do Hacker é delicioso! Altamente recomendado.
Eu acho que a maneira, sem mais rápido usando tabelas de pesquisa e popcount -é o seguinte. Ele conta os bits definidos com apenas 12 operações.
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;
}
Ele funciona porque você pode contar o número total de bits definidos pela divisão em duas metades, contando o número de bits definidos em ambas as partes e, em seguida, adicioná-los para cima. Também conhecido como paradigma Divide and Conquer. Vamos entrar em detalhes ..
v = v - ((v >> 1) & 0x55555555);
O número de bits em dois bits pode ser 0b00, 0b01 ou 0b10. Vamos tentar resolver isso em 2 pedaços ..
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
Este é o que era necessário: os últimos shows da coluna a contagem de bits definidos em cada par de dois bits. Se o número dois bits for >= 2 (0b10) então and produz 0b01, então ele produz 0b00.
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
Esta declaração deve ser fácil de entender. Após a primeira operação, temos a contagem de bits definidos em cada dois bits, agora vamos resumir que a contagem em cada 4 bits.
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
Em seguida, soma-se o resultado acima, dando-nos a contagem total de bits definidos em 4 bits. A última afirmação é o mais complicado.
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
Vamos dividi-la ainda mais ...
v + (v >> 4)
É semelhante à segunda declaração; estamos a contar os bits definidos em grupos de 4 em vez disso. Sabemos, porque dos nossos anteriores operações de que cada mordidela tem a contagem de bits definidos na mesma. Vejamos um exemplo. Suponha que temos o 0b01000010 byte. Isso significa que o primeiro nibble tem as suas 4bits definido e a segunda tem a sua 2bits conjunto. Agora vamos adicionar esses petiscos juntos.
0b01000010 + 0b01000000
Isso nos dá a contagem de bits definidos em um byte, no primeiro 0b01100010 mordidela e, portanto, mascarar os últimos quatro bytes de todos os bytes no número (descartá-los).
0b01100010 & 0xF0 = 0b01100000
Agora, cada byte tem a contagem de bits definidos na mesma. Precisamos adicionar-los todos juntos. O truque consiste em multiplicar o resultado por 0b10101010 que tem uma propriedade interessante. Se o nosso número tem quatro bytes, A B C D, que irá resultar em um novo número com estes bytes A+B+C+D B+C+D C+D D. Um número de 4 byte que pode ter no máximo de 32 bits definida, que pode ser representado como 0b00100000.
Tudo o que precisamos agora é o primeiro byte que tem a soma de todos os bits definidos em todos os bytes, e nós obtê-lo por >> 24. Este algoritmo foi projetado para palavras 32 bit mas pode ser facilmente modificado para palavras 64 bit.
Se acontecer de você estar usando Java, o built-in Integer.bitCount método irá fazer isso.
eu fiquei entediado, e cronometrado de um bilhão de iterações de três abordagens. Compiler é gcc O3. CPU é tudo o que eles colocaram no 1º gen Macbook Pro.
Fastest é o seguinte, em 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] );
}
O segundo lugar vai para o mesmo código, mas olhando para cima 4 bytes em vez de 2 meias palavras. Isso levou cerca de 5,5 segundos.
O terceiro lugar vai para o bit-twiddling 'lateralmente além' abordagem, que levou 8,6 segundos.
O quarto lugar vai para __builtin_popcount do GCC (), a uma vergonhosas 11 segundos.
A abordagem de contagem de um bit-a-um-tempo foi waaaay mais lento, e eu fiquei entediado de esperar por ele para ser concluído.
Então, se você se preocupa com desempenho acima de tudo, em seguida, usar a primeira abordagem. Se você se importa, mas não o suficiente para gastar 64Kb de memória RAM nele, use a segunda abordagem. Caso contrário, use a abordagem legível (mas lento) de um bit-a-um-tempo.
É difícil pensar em uma situação onde você gostaria de usar a abordagem girando pouco.
Edit: Resultados semelhantes aqui .
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;
}
Deixe-me explicar este algoritmo.
Este algoritmo é baseado em divisão e conquista. Suponha que há um 8bit inteiro 213 (11010101 em binário), o algoritmo funciona da seguinte forma (cada vez merge dois blocos vizinhos):
+-------------------------------+
| 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 é uma daquelas questões em que ajuda a conhecer a sua micro-arquitetura. Eu só cronometrado duas variantes sob gcc 4.3.3 compilado com O3 usando C ++ inlines para eliminar chamada de função em cima, um bilhão de iterações, mantendo a soma parcial de todos os aspectos para garantir o compilador não remove qualquer coisa importante, usando rdtsc para o sincronismo ( ciclo de relógio 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;
}
Delight do Hacker não modificada levou 12.2 gigacycles. Minha versão paralela (contando o dobro de bits) é executado em 13,0 gigacycles. 10.5s decorrido total para os dois juntos em uma 2.4GHz Core Duo. 25 gigacycles = pouco mais de 10 segundos a esta frequência de relógio, por isso estou confiante de meus horários estão certos.
Isto tem a ver com cadeias de dependência de instrução, que são muito ruins para este algoritmo. I pode quase o dobro da velocidade de novo, utilizando um par de registos de 64 bits. Na verdade, se eu era inteligente e acrescentou x + y um pouco mais cedo do que eu poderia raspar algumas mudanças. A versão de 64-bit com alguns pequenos ajustes sairia sobre o mesmo, mas contar o dobro de pedaços novamente.
Com 128 registros bit SIMD, outro fator de dois, e os conjuntos de instruções SSE muitas vezes têm atalhos inteligentes também.
Não há nenhuma razão para o código ser especialmente transparente. A interface é simples, o algoritmo pode ser referenciado on-line em muitos lugares, e é passível de teste de unidade abrangente. O programador que se depara com ele pode até aprender alguma coisa. Estas operações de bit são extremamente naturais no nível da máquina.
OK, eu decidi banco a versão de 64-bit beliscada. Para este 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;
}
Isso parece sobre direito (eu não estou testando com cuidado, embora). Agora os horários saem à 10.70 gigacycles / 14.1 gigacycles. Esse número mais tarde resumiu 128 bilhões de bits e corresponde a 5.9s decorridos nesta máquina. A versão não-paralelo acelera um pouco, porque eu estou em execução no modo de 64 bits e gosta registros de 64 bits ligeiramente melhor do que registros de 32 bits.
Vamos ver se há um pouco mais OOO canalizando a ser tido aqui. Este foi um pouco mais envolvidos, então eu realmente testado um pouco. Cada termo sozinho somas a 64, todos combinados soma de 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;
}
Eu estava animado por um momento, mas acontece que gcc está pregando peças em linha com O3 mesmo que eu não estou usando a palavra-chave inline em alguns testes. Quando eu deixar truques jogo gcc, um bilhão de chamadas para POP4 () pega 12,56 gigacycles, mas determinou-se dobrar argumentos como expressões constantes. Um número mais realista parece ser 19.6gc para outra velocidade-up de 30%. Meu circuito de teste agora se parece com isso, certificando-se cada argumento é diferente o suficiente para gcc parada de truques de baralho.
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 bilhões de bits somados em 8.17s decorrido. Trabalha fora de 1.02s para 32 milhões de bits como aferido na pesquisa de tabela de 16 bits. Não se pode comparar diretamente, porque o outro banco não lhe dá uma velocidade de clock, mas parece que eu já bateu o snot fora da edição de mesa 64KB, que é um uso trágica de cache L1, em primeiro lugar.
Update: decidiu fazer o óbvio e criar pop6 (), adicionando quatro linhas mais duplicados. Saiu para 22.8gc, 384 bilhões de bits somados em 9.5s decorrido. Portanto, há mais 20% Agora em 800ms para 32 bilhões de bits.
Por que não iterativa dividir por 2?
count = 0
while n > 0
if (n % 2) == 1
count += 1
n /= 2
Eu concordo que isso não é o mais rápido, mas "melhor" é um pouco ambígua. Eu diria ainda que "melhor" deve ter um elemento de clareza
Delight do Hacker mordeu-twiddling torna-se muito mais clara quando você escrever os padrões 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;
}
O primeiro passo adiciona os mesmo bits para os bits ímpares, produzindo uma soma de bits em cada dois. Os outros passos adicionar pedaços de alta ordem de pedaços de baixa ordem, duplicando o tamanho da parte todo o caminho para cima, até que tenhamos a contagem final ocupando todo o int.
Para um meio termo entre um 32 consulta à tabela 2 e iteração atravé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;
}
A partir http://ctips.pbwiki.com/CountBits
Não é a solução mais rápida ou melhor, mas eu achei a mesma pergunta no meu caminho, e eu comecei a pensar e pensar. finalmente percebi que ele pode ser feito assim se obter o problema de lado matemático, e desenhar um gráfico, então você achar que é uma função que tem alguma parte periódica, e então você percebe a diferença entre os períodos ... então aqui vai:
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);
}
}
Isto pode ser feito em O(k), onde k é o número de bits definidos.
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
A função que você está procurando é frequentemente chamado de "lado sum" ou "contagem da população" de um número binário. Knuth discute-lo na pré-Fascicle 1A, pp11-12 (embora houvesse uma referência breve, no Volume 2, 4.6.3- (7).)
O lócus classicus é o artigo de Peter Wegner "uma técnica para Ones Contando em um computador binário", a partir do Comunicações da ACM , Volume 3 (1960) Number 5 , página 322 . Ele dá dois algoritmos diferentes lá, um otimizado para os números esperado para ser "escassos" (ou seja, tem um pequeno número de ones) e uma para o caso oposto.
Algumas perguntas abertas: -
- Se o número for negativo, então?
- Se o número é de 1024, então o "fosso de forma iterativa por 2" método irá iterar 10 vezes.
podemos modificar o algo para suportar o número negativo como se segue: -
count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
count += 1
n /= 2
return count
Agora, para superar o segundo problema, podemos escrever a algo como: -
int bit_count(int num)
{
int count=0;
while(num)
{
num=(num)&(num-1);
count++;
}
return count;
}
para ver referência completa:
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;
}
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 em 1988, o C Linguagem de programação 2ª Ed. (Por Brian W. Kernighan e Dennis M. Ritchie) menciona isso em exercício 2-9. Em 19 de abril de 2006 Don Knuth indicou-me que este método "foi publicado pela primeira vez por Peter Wegner em CACM 3 (1960), 322. (também descoberto independentemente por Derrick Lehmer e publicado em 1964, em um livro editado por Beckenbach.)"
Eu uso o código abaixo que é mais intuitiva.
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
Logic:. N & (n-1) redefine o último conjunto de bits de n
P.S:. Eu sei que isto não é O (1) solução, embora uma solução interessante
O que você quer dizer com "melhor algoritmo"? O código curto ou o código de jejum? Seu código aparência muito elegante e tem um tempo de execução constante. O código também é muito curto.
Mas, se a velocidade é o principal fator e não o tamanho do código, então eu acho que o acompanhamento pode ser mais 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 );
}
Eu acho que isso não vai mais rápido para um valor de 64 bits, mas um valor de 32 bits pode ser mais rápido.
Eu escrevi uma macro rápida bitcount para máquinas RISC em cerca de 1990. Ele não usa aritmética avançada (multiplicação, divisão,%), buscas de memória (muito lento), ramos (muito lento), mas não assumir a CPU tem uma barrei shifter 32 bits (em outras palavras, um >> >> e 32 tenham a mesma quantidade de ciclos). assume-se que as pequenas constantes (tal como 6, 12, 24) custo nada a carga para os registos, ou são armazenados em temporários e reutilizado uma e outra vez.
Com estes pressupostos, conta 32 bits de cerca de 16 ciclos / instruções na maioria das máquinas RISC. Note-se que 15 instruções / ciclos está próximo de um limite do número de ciclos ou instruções inferior, porque parece demorar pelo menos 3 instruções (máscara, deslocamento, operador) para reduzir o número de parcelas pela metade, de modo log_2 (32) = 5, 5 x 3 = 15 instruções é um quasi-lowerbound.
#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;
Aqui está um segredo para o primeiro e mais complexa etapa:
input output
AB CD Note
00 00 = AB
01 01 = AB
10 01 = AB - (A >> 1) & 0x1
11 10 = AB - (A >> 1) & 0x1
então se eu tomar a 1ª coluna (A) acima, transferi-lo para a direita 1 bit, e subtrai-lo a partir de AB, recebo a saída (CD). A extensão de 3 bits é semelhante; você pode verificá-lo com um 8-linha da tabela boolean como o meu acima, se desejar.
- Don Gillies
Se você estiver usando C ++ outra opção é modelo metaprogramming uso:
// 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;
}
uso seria:
// 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 )
Você poderia naturalmente expandir ainda mais este modelo para usar tipos diferentes (tamanho do bit de detecção de auto mesmo), mas eu mantive-lo simples para maior clareza.
edit: esqueci de mencionar isso é bom porque deve trabalho em qualquer compilador C ++ e é basicamente apenas desenrola seu loop para você, se um valor constante é usado para o bit count (em outras palavras, eu tenho certeza que é o método mais rápido geral você encontrará)
Eu sou particularmente apaixonado por este exemplo do arquivo fortuna:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333)
- (((x)>>3)&0x11111111))
eu gosto melhor porque é tão bonito!
Java jdk1.5
Integer.bitCount (n);
em que n é o número cujo 1 são para serem contados.
verificar também,
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);
}
Eu encontrei uma implementação de contagem bit em uma matriz com o uso de instruções SIMD (SSSE3 e AVX2). Tem em 2-2,5 vezes melhor desempenho do que se ele vai usar __popcnt64 função intrínseca.
Versão 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];
}
Versão 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];
}
Eu sempre uso isso em programação competitiva e é fácil de escrever e eficiente:
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
Há muitos algoritmo para contar os bits definidos; Mas acho que o melhor é o mais rápido um! Você pode ver o detalhados nesta página:
Eu sugiro que esta:
<> fortes bits de contagem definido em 14, 24, ou palavras de 32 bits usando instruções 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 requer uma CPU de 64 bits com a divisão rápida módulo para ser eficiente. A primeira opção leva apenas 3 operações; a segunda opção leva 10; ea terceira opção tem 15.
C # rápida usando solução pré-calculada tabela de bit byte contagens com ramificação em tamanho 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
};
}
Aqui está um módulo portátil (ANSI-C) que pode referência cada um de seus algoritmos em qualquer arquitetura.
O seu CPU tem 9 bytes bit? Nenhum problema :-) No momento em que implementa 2 algoritmos, o K & R algoritmo e um byte tabela de pesquisa sábio. A tabela de pesquisa é, em média, 3 vezes mais rápido do que o algoritmo K & R. Se alguém pode descobrir uma maneira de fazer o "prazer do Hacker" algoritmo sensação portátil livre para adicioná-lo em.
#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-bit ou não? Eu só vim com este método em Java depois de ler " rachar a entrevista de codificação " 4ª edição exercice 5,5 (cap 5: Manipulação Bit). Se o bit menos significativo é 1 incremento count, então shift direita do inteiro.
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
Eu acho que este é mais intuitivo do que as soluções com constante 0x33333333 não importa o quão rápido eles estão. Depende da sua definição de "melhor algoritmo".
