Il modo più veloce per contare il numero di transizioni di bit in un unsigned

Question

Sto cercando il modo più veloce di contare il numero di transizioni di bit in un unsigned int.

Se l'int contiene: 0b00000000000000000000000000001010

Il numero di transizioni sono: 4

Se l'int contiene: 0b00000000000000000000000000001001

Il numero di transizioni sono: 3

lingua è C.

Answer 1

int numTransitions(int a) 
{ 
    int b = a >> 1; // sign-extending shift properly counts bits at the ends 
    int c = a^b; // xor marks bits that are not the same as their neighbors on the left 
    return CountBits(c); // count number of set bits in c 
} 

Per un'efficace attuazione CountBits vedi http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Answer 2

Che lingua?

Vorrei eseguire il ciclo 64 volte e quindi spostare il numero per controllare i bit, quindi memorizzare il bit precedente e confrontarlo con quello corrente. Se è diverso, conferma il tuo conteggio.

Answer 3

Ok, con transizioni vuoi dire se si cammina attraverso la stringa di 0-s e 1-s, si contano ogni avvenimento che un 0 segue un 1 o un 1 segue una 0.

Questo è facile da spostamento dei bit e conteggio delle modifiche:

transitions(n) 
    result = 0 
    prev = n mod 2 
    n = n div 2 
    while n<>0 
    if n mod 2 <> prev then 
     result++ 
     prev = n mod 2 
    fi 
    n = n div 2 
    elihw 
    return result 

è possibile sostituire il mod e div con turni.

Answer 4

Il più veloce dipende dallo scenario: Come è stato specificato il tipo di dati come dimensioni costanti (int unsigned), è possibile con la tabella di ricerca. Ma quando hai bisogno di questa operazione solo una volta che il sovraccarico costante per iniziare la tabella è troppo grande, e la scansione + il conteggio attraverso l'int è molto più veloce nonostante.

Immagino che il migliore complessivo sarebbe una combinazione: cercare la tabella per un byte o una parola (le voci 256 o 64k non sono tanto), e quindi combinare i byte/parole con il loro ultimo/primo bit.

Answer 5

In C/C++ Vorrei effettuare le seguenti operazioni:

unsigned int Transitions(unsigned int value) 
{ 
    unsigned int result = 0; 

    for (unsigned int markers = value^(value >> 1); markers; markers = markers >> 1) 
    { 
     if (markers & 0x01) result++; 
    } 

    return result; 
} 

Answer 6

Ecco il codice utilizzando spostamento aritmetico + xor e il metodo di Kernighan per il conteggio bit :

int count_transitions(int x) 
{ 
    assert((-1 >> 1) < 0); // check for arithmetic shift 
    int count = 0; 
    for(x ^= (x >> 1); x; x &= x - 1) 
     ++count; 
    return count; 
}