Come implementare Bitcount utilizzando solo operatori bitwise?

Question

L'attività consiste nell'implementare una logica di conteggio di bit utilizzando solo operatori bit a bit. Ho funzionato bene, ma mi chiedo se qualcuno possa suggerire un approccio più elegante.

Sono consentiti solo operazioni bitwise. No "se", "per" ecc.

int x = 4; 

printf("%d\n", x & 0x1); 
printf("%d\n", (x >> 1) & 0x1); 
printf("%d\n", (x >> 2) & 0x1); 
printf("%d\n", (x >> 3) & 0x1); 

Grazie.

Answer 1

Da http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

unsigned int v; // count bits set in this (32-bit value) 
unsigned int c; // store the total here 

c = v - ((v >> 1) & 0x55555555); 
c = ((c >> 2) & 0x33333333) + (c & 0x33333333); 
c = ((c >> 4) + c) & 0x0F0F0F0F; 
c = ((c >> 8) + c) & 0x00FF00FF; 
c = ((c >> 16) + c) & 0x0000FFFF; 

Edit: Certo è un po 'ottimizzato che rende più difficile da leggere. E 'facile da leggere come:

c = (v & 0x55555555) + ((v >> 1) & 0x55555555); 
c = (c & 0x33333333) + ((c >> 2) & 0x33333333); 
c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F); 
c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF); 
c = (c & 0x0000FFFF) + ((c >> 16)& 0x0000FFFF); 

Ogni passaggio di questi cinque, aggiunge bit adiacenti insieme in gruppi di 1, poi 2, poi 4 ecc Il metodo si basa in dividi e conquista.

Nel primo passaggio sommiamo i bit 0 e 1 e inseriamo il risultato nel segmento a due bit 0-1, aggiungiamo i bit 2 e 3 e inseriamo il risultato nel segmento 2-3 bit ecc ...

Nel secondo passaggio aggiungiamo i due bit 0-1 e 2-3 insieme e mettiamo il risultato in quattro bit 0-3, sommiamo due bit 4-5 e 6-7 e inseriamo il risultato in quattro bit 4-7 ecc ...

Esempio:

So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1) 
After the first step I have:  0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10 
In the second step I have:  0000000100010011 (00+00 00+01 01+00 01+10) = 0000 0001 0001 0011 
In the fourth step I have:  0000000100000100 ( 0000+0001  0001+0011 ) = 00000001 00000100 
In the last step I have:   0000000000000101 (  00000001+00000100  ) 

che è uguale a 5, che è il risultato corretto

Answer 2

Diverse soluzioni interessanti here.

Se le soluzioni sopra sono troppo noioso, ecco una versione ricorsiva C esente condizione di test o ad anello:

int z(unsigned n, int count); 
    int f(unsigned n, int count); 

    int (*pf[2])(unsigned n, int count) = { z,f }; 

    int f(unsigned n, int count) 
    { 
    return (*pf[n > 0])(n >> 1, count+(n & 1)); 
    } 

    int z(unsigned n, int count) 
    { 
    return count; 
    } 

    ... 
    printf("%d\n", f(my_number, 0)); 

Answer 3

avrei usato un pre-calcolate matrice

uint8_t set_bits_in_byte_table[ 256 ]; 

The i - la voce in questa tabella memorizza il numero di bit impostati nel byte i, ad es. set_bits_in_byte_table[ 100 ] = 3 poiché ci sono 3 1 bit nella rappresentazione binaria del decimale 100 (= 0x64 = 0110-0100).

Poi vorrei provare

size_t count_set_bits(uint32_t x) { 
    size_t count = 0; 
    uint8_t * byte_ptr = (uint8_t *) &x; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    count += set_bits_in_byte_table[ *byte_ptr++ ]; 
    return count; 
} 

Answer 4

Ecco una semplice illustrazione alla answer:

a b c d  0 a b c  0 b 0 d  
&    &    + 
0 1 0 1  0 1 0 1  0 a 0 c 
-------  -------  ------- 
0 b 0 d  0 a 0 c  a+b c+d 

Così abbiamo esattamente 2 bit per memorizzare un + b e 2 bit per memorizzare c + d. a = 0, 1 ecc., quindi 2 bit è ciò di cui abbiamo bisogno per memorizzare la loro somma. Al prossimo passaggio avremo 4 bit per memorizzare la somma dei valori a 2 bit, ecc.