Contare i bit nel numero [duplicato]

Question

Duplica:

  

Migliore algoritmo per contare il numero di bit impostati in un numero intero a 32 bit?

---

Supponi di avere un numero. C'è un modo per contare i bit che equivalgono a 1 nella rappresentazione binaria di quel numero, non usando l'iterazione? Voglio dire, c'è un modo per farlo in tempo costante usando alcuni operatori bit e maschere. Ho bisogno di una soluzione che funzioni bene per entrambe le architetture a 32 e 64 bit. Ah quasi dimenticavo, ne ho bisogno per il linguaggio C o anche l'assemblatore è buono.

Answer 1

Esiste un algoritmo di conteggio dei bit senza loop in http: //graphics.stanford. edu / ~ seander / bithacks.html . Molti algoritmi di conteggio dei bit su http: //gurmeetsingh.wordpress .com / 2008/08/05 / fast-bit di conteggio-routine /

Answer 2

Beh, certo che c'è, ma non ti piacerà.

Ovviamente potresti creare una tabella di ricerca con tutti i valori corretti al suo interno:

tabella [1] = 1, tabella [2] = 1, tabella [3] = 2, ecc.

Quindi, questo ti darebbe una risposta molto veloce , ma è una soluzione completamente inutile da sola, dato che il tavolo dovrebbe essere molto, molto grande.

Potresti ottimizzarlo un po ', ma richiede solo una piccola iterazione. È sufficiente creare una versione a 8 bit della soluzione della tabella, una semplice tabella a 256 voci, quindi scorrere su ciascun BYTE nel valore da verificare, sommando i risultati della ricerca della tabella. Qualcosa del tipo:

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, sembra che questo sia ben noto (e qui lo stavo facendo dalla cima della mia testa): http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Answer 3

Sì, puoi farlo utilizzando una cerca tabella .