Contagem de bits no número [duplicado]

Question

Duplicate:

Melhor algoritmo para contar o número de bits definidos em um inteiro de 32 bits?

---

Suponha que você tenha um número. Existe alguma maneira de contar os bits que é igual a 1 em representação binária desse número, não usando iteração? Quer dizer, existe alguma maneira de fazê-lo em tempo constante usando alguns operadores bit a bit e máscaras. solução necessidade I, que irá funcionar bem para ambas arquiteturas de 32 bits e 64 bits. Ah quase esqueci, eu preciso dele para a linguagem C ou assembler também é bom.

Answer 1

Há um algoritmo bit contagem sem um loop em http: //graphics.stanford. edu / ~ seander / bithacks.html . Lotes de algoritmos de contagem de bits em http: //gurmeetsingh.wordpress .com / 2008/08/05 / fast-bit de contagem de-rotinas /

Answer 2

Bem, é claro que é, mas você não vai gostar.

Você poderia, naturalmente, construir uma tabela de pesquisa com todos os valores corretos em que:

mesa [1] = 1, tabela [2] = 1, tabela [3] = 2, etc.

Então, isso lhe daria uma muito rápido resposta, mas é uma solução completamente inútil por si só, uma vez que a tabela teria que ser muito, muito grande.

Você pode otimizar isso um pouco, mas requer apenas um pouco de iteração. Basta criar uma versão da solução de mesa, uma simples mesa de entrada de 256 8-bit, em seguida, iterar sobre cada byte no valor a ser verificado, resumindo os resultados da pesquisa da tabela. Algo como:

short int tableLookup[256] = { 0, 1, 1, 2, 1, ... };
unsigned int valueToCheck = 89392491;
int result = 0;
while ( valueToCheck != 0 ) {
   result += tableLookup[ (valueToCheck & 0xFF) ];
   valueToCheck >>= 8;
}
// result should now have the correct bit count, if the table is correct.

Hmm, parece que este é bem conhecido (e aqui eu estava fazendo isso em cima da minha cabeça): http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Answer 3

Sim, você pode fazer isso usando um olhar para cima da tabela .