Como contar o número de bits definidos em um número inteiro de 32 bits?

8 bits representando o número 7 são assim:

00000111

Três bits estão definidos.

O que são algoritmos para determinar o número de bits definidos em um número inteiro de 32 bits?

Isso é conhecido como ' Peso de Hamming ', 'popcount' ou 'adição lateral'.

O melhor algoritmo realmente depende de qual CPU você está e qual é o seu padrão de uso.

Algumas CPUs possuem uma única instrução interna para fazê-lo e outras possuem instruções paralelas que atuam em vetores de bits. As instruções paralelas (como x86 popcnt, em CPUs onde é suportado) quase certamente serão mais rápidas. Algumas outras arquiteturas podem ter uma instrução lenta implementada com um loop microcodificado que testa um pouco por ciclo ( citação necessária ).

Um método de pesquisa de tabela pré-preenchido pode ser muito rápido se sua CPU tiver um cache grande e / ou você estiver executando muitas dessas instruções em um loop restrito. No entanto, isso pode sofrer por causa da despesa de uma "falha de cache", em que a CPU precisa buscar parte da tabela da memória principal. (Procure cada byte separadamente para manter a tabela pequena.)

Se você souber que seus bytes serão geralmente 0 ou 1, então existem algoritmos muito eficientes para esses cenários.

Acredito que um algoritmo de uso geral muito bom seja o seguinte, conhecido como 'paralelo' ou 'algoritmo SWAR de precisão variável'. Eu expressei isso em uma pseudo linguagem C, você pode precisar ajustá-la para funcionar em uma linguagem específica (por exemplo, usando uint32_t para C ++ e >>> em Java):

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and 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;
}

Para JavaScript: coagir para inteiro com |0para desempenho: altere a primeira linha parai = (i|0) - ((i >> 1) & 0x55555555);

Esse tem o melhor comportamento de pior caso de qualquer um dos algoritmos discutidos; portanto, ele lida com eficiência com qualquer padrão de uso ou valores que você lançar nele.

Como esse bithack SWAR funciona:

i = i - ((i >> 1) & 0x55555555);

O primeiro passo é uma versão otimizada do mascaramento para isolar os bits ímpares / pares, alternando para alinhá-los e adicionando. Isso efetivamente faz 16 adições separadas em acumuladores de 2 bits ( SWAR = SIMD dentro de um registro ). Like (i & 0x55555555) + ((i>>1) & 0x55555555).

A próxima etapa pega os ímpares / pares oito desses acumuladores de 16x e 2 bits e os adiciona novamente, produzindo somas 8x e 4 bits. A i - ...otimização não é possível neste momento para que ele não apenas mascarar antes / depois da mudança. Usar a mesma 0x33...constante nas duas vezes, em vez de 0xccc...antes da mudança, é uma boa coisa ao compilar ISAs que precisam construir constantes de 32 bits em registradores separadamente.

A etapa final de troca e adição de (i + (i >> 4)) & 0x0F0F0F0Famplia para 4x acumuladores de 8 bits. Ele mascara após adicionar, em vez de antes, porque o valor máximo em qualquer acumulador de 4 bits é 4se todos os 4 bits dos bits de entrada correspondentes foram definidos. 4 + 4 = 8 que ainda cabe em 4 bits, portanto, é impossível transportar entre elementos de mordidela i + (i >> 4).

Até agora, esse é apenas o SIMD normal, usando técnicas SWAR com algumas otimizações inteligentes. Continuar com o mesmo padrão por mais duas etapas pode aumentar para 2x 16 bits e 1x contagem de 32 bits. Mas existe uma maneira mais eficiente em máquinas com multiplicação rápida de hardware:

Uma vez que tenhamos poucos "elementos" suficientes, uma multiplicação por uma constante mágica pode somar todos os elementos no elemento superior . Nesse caso, elementos de byte. A multiplicação é feita deslocando-se para a esquerda e adicionando, portanto, uma multiplicação de x * 0x01010101resultados em x + (x<<8) + (x<<16) + (x<<24). Nossos elementos de 8 bits são amplos o suficiente (e mantêm contagens pequenas o suficiente) para que isso não produza efeito nos 8 bits superiores.

Uma versão de 64 bits pode fazer elementos 8x de 8 bits em um número inteiro de 64 bits com um multiplicador 0x0101010101010101 e extrair o byte alto com >>56. Portanto, não são necessárias etapas extras, apenas constantes mais amplas. É isso que o GCC usa __builtin_popcountllnos sistemas x86 quando a popcntinstrução de hardware não está ativada. Se você pode usar componentes internos ou intrínsecos para isso, faça isso para que o compilador tenha a chance de fazer otimizações específicas de destino.

Com SIMD completo para vetores mais amplos (por exemplo, contando uma matriz inteira)

Esse algoritmo SWAR bit a bit poderia ser paralelo para ser feito em vários elementos vetoriais de uma só vez, em vez de em um único registro inteiro, para acelerar as CPUs com SIMD, mas sem instrução utilizável de contagem de pop-ups. (por exemplo, código x86-64 que precisa ser executado em qualquer CPU, não apenas no Nehalem ou posterior.)

No entanto, a melhor maneira de usar instruções vetoriais para contagem pop-up é geralmente usando um shuffle variável para fazer uma pesquisa na tabela por 4 bits por vez de cada byte em paralelo. (Os 4 bits indexam uma tabela de 16 entradas mantida em um registro vetorial).

Nas CPUs Intel, a instrução popcnt de hardware de 64 bits pode superar uma implementação paralela de bits SSSE3PSHUFB em cerca de um fator de 2, mas apenas se o seu compilador acertar . Caso contrário, o SSE pode sair significativamente à frente. As versões mais recentes do compilador estão cientes do problema da dependência falsa popcnt na 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)

Considere também as funções internas 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);

Na pior das hipóteses, o compilador gerará uma chamada para uma função. Na melhor das hipóteses, o compilador emitirá uma instrução da CPU para fazer o mesmo trabalho mais rapidamente.

As intrínsecas do GCC até funcionam em várias plataformas. O Popcount se tornará popular na arquitetura x86; portanto, faz sentido começar a usar o intrínseco agora. Outras arquiteturas têm o número de habitantes há anos.

No x86, você pode dizer ao compilador que ele pode assumir suporte para popcntinstruções com -mpopcntou -msse4.2também habilitar as instruções vetoriais que foram adicionadas na mesma geração. Consulte as opções do GCC x86 . -march=nehalem(ou -march=qualquer CPU que você queira que seu código assuma e ajuste) pode ser uma boa escolha. A execução do binário resultante em uma CPU mais antiga resultará em uma falha de instrução ilegal.

Para otimizar os binários para a máquina em que você os constrói, use -march=native (com gcc, clang ou ICC).

O MSVC fornece um intrínseco para a popcntinstrução x86 , mas, ao contrário do gcc, é realmente intrínseco para a instrução de hardware e requer suporte de hardware.

Usando em std::bitset<>::count()vez de um built-in

Em teoria, qualquer compilador que saiba contabilizar eficientemente a CPU de destino deve expor essa funcionalidade por meio do ISO C ++ std::bitset<>. Na prática, você pode estar melhor com o bit-hack AND / shift / ADD em alguns casos para algumas CPUs de destino.

Para arquiteturas de destino em que o popcount de hardware é uma extensão opcional (como x86), nem todos os compiladores têm um std::bitsetque aproveita quando disponível. Por exemplo, o MSVC não tem como habilitar o popcntsuporte em tempo de compilação e sempre usa uma pesquisa de tabela , mesmo com /Ox /arch:AVX(o que implica o SSE4.2, embora tecnicamente exista um bit de recurso separado para popcnt).

Mas pelo menos você obtém algo portátil que funciona em qualquer lugar e, com o gcc / clang com as opções de destino corretas, você obtém o número de pop-ups de 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 do gcc, clang, icc e MSVC no Godbolt compiler explorer.

x86-64 gcc -O3 -std=gnu++11 -mpopcntemite isso:

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

Emissões do PowerPC64 gcc -O3 -std=gnu++11(para a intversão arg):

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

Essa fonte não é específica para x86 ou GNU, mas apenas compila bem para x86 com gcc / clang / icc.

Observe também que o fallback do gcc para arquiteturas sem contagem de pop-up de instrução única é uma consulta de tabela de bytes por vez. Isso não é maravilhoso para o ARM, por exemplo .

Na minha opinião, a "melhor" solução é aquela que pode ser lida por outro programador (ou o programador original dois anos depois) sem grandes comentários. Você pode querer a solução mais rápida ou inteligente que alguns já forneceram, mas eu prefiro a legibilidade do que a inteligência a 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ê a documente bem para ajudar seus sucessores), use uma pesquisa de 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 eles dependam de tamanhos específicos de tipos de dados, não são tão portáteis. Porém, como muitas otimizações de desempenho não são portáveis, isso pode não ser um problema. Se você quer portabilidade, eu me ateria à solução legível.

Do prazer do hacker, 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 ~ 20-ish instruções (dependentes do arco), sem ramificação.

O prazer do hacker é delicioso! Altamente recomendado.

Acho que o caminho mais rápido - sem usar tabelas de pesquisa e contagem de pop - ups - é o seguinte. 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;
}

Isso funciona porque você pode contar o número total de bits definidos dividindo-os em duas metades, contando o número de bits definidos em ambas as metades e, em seguida, somando-os. Também conhecido como Divide and Conquerparadigma. Vamos entrar em detalhes ..

v = v - ((v >> 1) & 0x55555555); 

O número de bits em dois bits pode ser 0b00, 0b01ou 0b10. Vamos tentar resolver isso em 2 bits.

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

Isso é necessário: a última coluna mostra a contagem de bits definidos em cada par de dois bits. Se o número dois bits é >= 2 (0b10)então andproduz 0b01, então ele produz 0b00.

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

Essa afirmação deve ser fácil de entender. Após a primeira operação, temos a contagem de bits definidos a cada dois bits, agora somamos essa contagem a cada 4 bits.

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

Em seguida, somamos o resultado acima, fornecendo a contagem total de bits definidos em 4 bits. A última afirmação é a mais complicada.

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

Vamos dividir ainda mais ...

v + (v >> 4)

É semelhante à segunda declaração; estamos contando os bits definidos em grupos de 4. Sabemos - por causa de nossas operações anteriores - que toda mordidela tem a contagem de bits definidos. Vamos dar um exemplo. Suponha que tenhamos o byte 0b01000010. Isso significa que o primeiro nibble tem seu conjunto de 4 bits e o segundo tem seu conjunto de 2 bits. Agora adicionamos esses petiscos.

0b01000010 + 0b01000000

Ele nos fornece a contagem de bits definidos em um byte, na primeira mordida 0b01100010e, portanto, mascaramos os últimos quatro bytes de todos os bytes do número (descartando-os).

0b01100010 & 0xF0 = 0b01100000

Agora, cada byte possui a contagem de bits definidos. Precisamos adicioná-los todos juntos. O truque é multiplicar o resultado pelo 0b10101010qual possui uma propriedade interessante. Se nosso número tiver quatro bytes, A B C Disso resultará em um novo número com esses bytes A+B+C+D B+C+D C+D D. Um número de 4 bytes pode ter um conjunto máximo de 32 bits, que pode ser representado como 0b00100000.

Tudo o que precisamos agora é o primeiro byte que tenha a soma de todos os bits definidos em todos os bytes, e nós o obtemos >> 24. Este algoritmo foi projetado para 32 bitpalavras, mas pode ser facilmente modificado para 64 bitpalavras.

Fiquei entediado e cronometrei um bilhão de iterações de três abordagens. O compilador é gcc -O3. CPU é o que eles colocam no Macbook Pro de 1ª geração.

O mais rápido é 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 procurando 4 bytes em vez de 2 meias palavras. Isso levou cerca de 5,5 segundos.

O terceiro lugar está na abordagem de 'adição lateral', que levou 8,6 segundos.

O quarto lugar vai para __builtin_popcount (), em vergonhosos 11 segundos.

A abordagem de contar um bit de cada vez era muito mais lenta, e eu me cansei de esperar que ela terminasse.

Portanto, se você se preocupa com o desempenho acima de tudo, use a primeira abordagem. Se você se importa, mas não o suficiente para gastar 64 KB de RAM, use a segunda abordagem. Caso contrário, use a abordagem legível (mas lenta) de um bit de cada vez.

É difícil pensar em uma situação em que você queira usar a abordagem de manipulação de bits.

Edit: Resultados semelhantes aqui .

Se você estiver usando Java, o método Integer.bitCountinterno fará isso.

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 esse algoritmo.

Este algoritmo é baseado no algoritmo de divisão e conquista. Suponha que haja um número inteiro de 8 bits 213 (11010101 em binário), o algoritmo funciona assim (cada vez que mescla 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)
+-------------------------------+

Essa é uma daquelas perguntas em que ajuda a conhecer sua microarquitetura. Eu apenas cronometrei duas variantes no gcc 4.3.3 compiladas com -O3 usando inline C ++ para eliminar a sobrecarga de chamadas de função, um bilhão de iterações, mantendo a soma de todas as contagens para garantir que o compilador não remova nada de importante, usando rdtsc para cronometrar ( ciclo do relógio preciso).

inline int pop2 (x não assinado, y não assinado)
{
    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);
    retornar (x + y) & 0x000000FF;
}

O Hacker's Delight não modificado levou 12,2 gigaciclos. Minha versão paralela (contando o dobro de bits) é executada em 13,0 gigaciclos. Total de 10,5 segundos decorridos para ambos juntos em um Core Duo de 2,4 GHz. 25 gigaciclos = pouco mais de 10 segundos nessa freqüência de relógio, por isso estou confiante de que meus horários estão corretos.

Isso tem a ver com cadeias de dependência de instruções, que são muito ruins para esse algoritmo. Eu quase conseguia dobrar a velocidade novamente usando um par de registros de 64 bits. De fato, se eu fosse inteligente e adicionasse x + y um pouco antes, poderia cortar alguns turnos. A versão de 64 bits com alguns pequenos ajustes sairia equilibrada, mas contaria o dobro de bits novamente.

Com os registros SIMD de 128 bits, outro fator é dois, e os conjuntos de instruções SSE também possuem atalhos inteligentes.

Não há 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 testes de unidade abrangentes. O programador que se depara com isso pode até aprender alguma coisa. Essas operações de bits são extremamente naturais no nível da máquina.

OK, decidi testar a versão de 64 bits ajustada. Para esse tamanho único (sem assinatura) == 8

inline int pop2 (sem assinatura x longo, sem assinatura y longo)
{
    x = x - ((x >> 1) & 0x5555555555555555);
    y = y - ((y >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x333333333333333333);
    y = (y & 0x3333333333333333) + ((y >> 2) & 0x333333333333333333);
    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); 
    retornar x & 0xFF;
}

Parece certo (embora não esteja testando com cuidado). Agora, o tempo é de 10,70 gigacycles / 14,1 gigacycles. Esse número posterior somou 128 bilhões de bits e corresponde a 5,9s decorridos nesta máquina. A versão não paralela acelera um pouquinho, porque eu estou executando no modo de 64 bits e gosta de registros de 64 bits um pouco melhor que os de 32 bits.

Vamos ver se há um pouco mais de gasoduto OOO aqui. Isso foi um pouco mais envolvido, então eu realmente testei um pouco. Cada termo sozinho soma 64, todos somados a 256.

inline int pop4 (sem assinatura x longo, sem assinatura long y, 
                sem assinatura longa u, sem assinatura longa v)
{
  enumeração {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 e m2) + ((y >> 2) e 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);
    retornar x & 0x000001FF;
}

Fiquei empolgado por um momento, mas acontece que o gcc está fazendo truques inline com -O3, embora não esteja usando a palavra-chave inline em alguns testes. Quando deixei o gcc fazer truques, um bilhão de chamadas para pop4 () leva 12,56 gigaciclos, mas eu concluí que estava dobrando argumentos como expressões constantes. Um número mais realista parece ser 19,6gc para mais 30% de aceleração. Meu loop de teste agora se parece com isso, garantindo que cada argumento seja diferente o suficiente para impedir que o gcc faça truques.

   hitime b4 = rdtsc (); 
   for (longo não assinado i = 10L * 1000 * 1000 * 1000; i <11L * 1000 * 1000 * 1000; ++ i) 
      soma + = pop4 (i, i ^ 1, ~ i, i | 1); 
   hitime e4 = rdtsc (); 

256 bilhões de bits somados em 8,17s passaram. Funciona em 1,02s para 32 milhões de bits, como comparado na pesquisa de tabela de 16 bits. Não é possível comparar diretamente, porque o outro banco não fornece uma velocidade de clock, mas parece que eu dei um tapa na edição de tabela de 64 KB, que é um uso trágico do cache L1 em ​​primeiro lugar.

Atualização: decidiu fazer o óbvio e criar pop6 () adicionando mais quatro linhas duplicadas. Chegando a 22,8 gc, 384 bilhões de bits somados em 9,5 segundos decorridos. Portanto, há mais 20% do Now a 800ms para 32 bilhões de bits.

Por que não iterativamente dividir por 2?

count = 0
enquanto n> 0
  if (n% 2) == 1
    contagem + = 1
  n / = 2  

Concordo que este não é o mais rápido, mas o "melhor" é um tanto ambíguo. Eu argumentaria que o "melhor" deveria ter um elemento de clareza

A modificação de bits do Hacker's Delight se torna muito mais clara quando você escreve 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 bits pares aos ímpares, produzindo uma soma de bits em cada dois. As outras etapas adicionam pedaços de ordem superior a pedaços de ordem inferior, dobrando o tamanho do pedaço até o fim, até que a contagem final ocupe todo o int.

Para um meio termo entre uma tabela de pesquisa 2 ³² e iterando 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;
}

Em http://ctips.pbwiki.com/CountBits

Isso pode ser feito em O(k), onde kestá o número de bits definido.

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}

Não é a solução mais rápida ou melhor, mas encontrei a mesma pergunta no meu caminho e comecei a pensar e pensar. finalmente percebi que isso pode ser feito assim, se você pegar o problema do lado matemático e desenhar um gráfico, então descobrirá que é uma função que possui alguma parte periódica e, então, perceberá a diferença entre os períodos ... aqui está:

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);
    }
}

A função que você está procurando costuma ser chamada de "soma lateral" ou "contagem da população" de um número binário. Knuth discute isso no pré-fascículo 1A, pp11-12 (embora tenha havido uma breve referência no volume 2, 4.6.3- (7).)

O locus classicus é o artigo de Peter Wegner "Uma técnica para contar em um computador binário", da Communications of the ACM , volume 3 (1960), número 5, página 322 . Ele fornece dois algoritmos diferentes, um otimizado para números que se espera "esparsos" (ou seja, possuem um número pequeno de um) e outro para o caso oposto.

  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;
    }

Poucas perguntas em aberto: -

1. Se o número é negativo, então?
2. Se o número for 1024, o método "dividir iterativamente por 2" repetirá 10 vezes.

podemos modificar o algo para suportar o número negativo da seguinte maneira: -

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 o algo como:

int bit_count(int num)
{
    int count=0;
    while(num)
    {
        num=(num)&(num-1);
        count++;
    }
    return count;
}

para referência completa, consulte:

http://goursaha.freeoda.com/Misc Miscellaneous/IntegerBitCount.html

Acho que o método de Brian Kernighan também será útil ... Ele passa por tantas iterações quanto por bits definidos. Portanto, se tivermos uma palavra de 32 bits apenas com o conjunto de bits alto, ela passará apenas uma vez pelo loop.

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 Programming Language 2nd Ed. (de Brian W. Kernighan e Dennis M. Ritchie) menciona isso no exercício 2-9. Em 19 de abril de 2006, Don Knuth me indicou que esse método "foi publicado pela primeira vez por Peter Wegner no CACM 3 (1960), 322. (Também descoberto de forma independente por Derrick Lehmer e publicado em 1964 em um livro editado por Beckenbach.)"

Eu uso o código abaixo, que é mais intuitivo.

int countSetBits(int n) {
    return !n ? 0 : 1 + countSetBits(n & (n-1));
}

Lógica: n & (n-1) redefine o último bit definido de n.

PS: Eu sei que essa não é a solução O (1), embora seja uma solução interessante.

O que você quer dizer com "Melhor algoritmo"? O código em curto ou o código em jejum? Seu código parece muito elegante e possui 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, acho que o seguinte 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 será 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 de contagem de bits para máquinas RISC por volta de 1990. Ela não usa aritmética avançada (multiplicação, divisão,%), busca de memória (muito lenta), ramificações (muito lenta), mas assume que a CPU tem um Shifter de barril de 32 bits (em outras palavras, >> 1 e >> 32 levam a mesma quantidade de ciclos.) Pressupõe que pequenas constantes (como 6, 12, 24) não custam nada para carregar nos registradores ou são armazenadas temporários e reutilizados repetidamente.

Com essas suposições, conta 32 bits em cerca de 16 ciclos / instruções na maioria das máquinas RISC. Observe que 15 instruções / ciclos está próximo de um limite inferior no número de ciclos ou instruções, porque parece levar pelo menos 3 instruções (máscara, turno, operador) para reduzir pela metade o número de adendas, portanto log_2 (32) = 5, 5 x 3 = 15 instruções é quase um limite 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;

Aqui está um segredo para o primeiro e mais complexo passo:

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 pegar a 1ª coluna (A) acima, deslocar para a direita 1 bit e subtraí-la de AB, recebo a saída (CD). A extensão para 3 bits é semelhante; você pode verificá-lo com uma tabela booleana de 8 linhas como a minha acima, se desejar.

• Don Gillies

se você estiver usando C ++, outra opção é usar a metaprogramação de modelo:

// 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;
}

o 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 )

é claro que você poderia expandir ainda mais esse modelo para usar tipos diferentes (até mesmo o tamanho de bits de detecção automática), mas eu o mantive simples para maior clareza.

edit: esqueci de mencionar que isso é bom porque deve funcionar em qualquer compilador C ++ e basicamente desenrola seu loop para você se um valor constante for usado para a contagem de bits (em outras palavras, tenho certeza de que é o método geral mais rápido você encontrará)

Gosto particularmente deste exemplo do arquivo da sorte:

#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 mais porque é tão bonito!

Java JDK1.5

Integer.bitCount (n);

onde n é o número cujos 1s devem ser contados.

verifique 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 de bits em uma matriz com o uso da instrução SIMD (SSSE3 e AVX2). Tem desempenho 2-2,5 vezes melhor do que se usasse a função intrínseca __popcnt64.

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 escrever e eficiente:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}

Existem muitos algoritmos para contar os bits definidos; mas acho que o melhor é o mais rápido! Você pode ver o detalhado nesta página:

Bit Twiddling Hacks

Eu sugiro este:

Contando bits definidos em palavras de 14, 24 ou 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 que uma CPU de 64 bits com divisão de módulo rápida seja eficiente. A primeira opção leva apenas 3 operações; a segunda opção leva 10; e a terceira opção leva 15.

A solução C # rápida usando a tabela pré-calculada de bits de byte conta com ramificação no tamanho da 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 comparar cada um de seus algoritmos em qualquer arquitetura.

Sua CPU possui bytes de 9 bits? Não tem problema :-) No momento, ele implementa 2 algoritmos, o algoritmo K&R e uma tabela de consulta de bytes. A tabela de pesquisa é, em média, 3 vezes mais rápida que o algoritmo K&R. Se alguém conseguir descobrir uma maneira de tornar portátil o algoritmo "Hacker's Delight", sinta-se à vontade para adicioná-lo.

#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

o que você pode fazer é

while(n){
    n=n&(n-1);
    count++;
}

a lógica por trás disso é que os bits de n-1 são invertidos do bit mais à direita definido de n. se n = 6 ie 110, então 5 é 101, os bits são invertidos do bit mais à direita definido de n. Então, se nós e esses dois, criaremos o bit mais à direita 0 em cada iteração e sempre iremos para o próximo bit definido à direita. Portanto, contando o bit definido. A pior complexidade de tempo será O (logn) quando cada bit estiver definido.