Operazioni bit a bit efficienti per contare i bit o trovare quelli più a destra

Dato un int unsigned, devo implementare le seguenti operazioni:

  1. Contare il numero di bit impostato su 1
  2. Trova l’indice del 1 bit più a sinistra
  3. Trova l’indice del 1 ° righ-most

(l’operazione non dovrebbe essere dipendente dall’architettura).

L’ho fatto usando il bit-shift, ma devo scorrere tutte le parti (es.32). Ad esempio, contando 1:

unsigned int number= ...; while(number != 0){ if ((number & 0x01) != 0) ++count; number >>=1; } 

Le altre operazioni sono simili.

Quindi la mia domanda è: c’è un modo più veloce per farlo?

    Se si desidera il modo più veloce , sarà necessario utilizzare metodi non portatili.

    Finestre / MSVC:

    • _BitScanForward ()
    • _BitScanReverse ()
    • __popcnt ()

    GCC:

    • __builtin_ffs ()
    • __builtin_ctz ()
    • __builtin_clz ()
    • __builtin_popcount ()

    Questi in genere si mappano direttamente alle istruzioni hardware native. Quindi non diventa molto più veloce di questi.

    Ma dal momento che non ci sono funzionalità C / C ++ per loro, sono accessibili solo tramite l’intrinseco del compilatore.

    Dai un’occhiata a ffs (3), ffsl (3), fls (3), flsl (3).

    Le funzioni ffs () e ffsl () trovano il primo bit impostato (che inizia con il bit meno significativo) in i e restituiscono l’indice di quel bit.

    Le funzioni fls () e flsl () trovano l’ultimo bit impostato in i e restituiscono l’indice di quel bit.

    Potresti anche essere interessato a bitstring (3).

    Citando da http://graphics.stanford.edu/~seander/bithacks.html

    Il metodo migliore per contare i bit in un intero v a 32 bit è il seguente:

     unsigned int v; // count bits set in this (32-bit value) unsigned int c; // store the total here v = v - ((v >> 1) & 0x55555555); // reuse input as temporary v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count 

    Il miglior metodo di conteggio dei bit richiede solo 12 operazioni, che è lo stesso del metodo della tabella di ricerca, ma evita la memoria e i potenziali errori di cache di una tabella. È un ibrido tra il metodo puramente parallelo sopra e i metodi precedenti che utilizzano i multipli (nella sezione sui bit di conteggio con istruzioni a 64 bit), sebbene non utilizzi istruzioni a 64 bit. I conteggi dei bit impostati nei byte vengono eseguiti in parallelo e la sum totale dei bit impostati nei byte viene calcasting moltiplicando per 0x1010101 e spostando a destra 24 bit.

    Un approccio consiste nell’utilizzare una tabella di ricerca.

     uint8_t popcount_table[256] = { ... }; uint8_t popcount (uint32_t x) { uint8_t *p = (uint8_t*)&x; return popcount_table[p[0]] + popcount_table[p[1]] + popcount_table[p[2]] + popcount_table[p[3]]; }