Le moyen le plus rapide de compter le nombre de transitions binaires dans un entier non signé

Question

Je cherche le moyen le plus rapide de compter le nombre de transitions binaires dans un unsigned int.

Si l'int contient: 0b00000000000000000000000000001010

Le nombre de transitions sont: 4

Si l'int contient: 0b00000000000000000000000000001001

Le nombre de transitions sont: 3

Langue est 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 
} 

Pour une mise en œuvre efficace de CountBits voir http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Answer 2

Quelle langue?

Je voudrais boucler 64 fois et ensuite décaler votre nombre pour inspecter les bits, puis stocker le bit précédent et le comparer à celui en cours. Si c'est différent, inscrivez votre compte.

Answer 3

Ok, avec des transitions que vous voulez dire que si vous marchez à travers la chaîne de 0-s et 1 s, on compte chaque occurence que 0 suit un 1 ou un 0. 1 suit un

C'est facile par décaler les bits et compter les changements:

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 

vous pouvez remplacer le mod et div avec des changements.

Answer 4

Le plus rapide dépend de votre scénario: Comme vous avez spécifié votre type de données en tant que taille constante (entier non signé), cela est possible avec une table de recherche. Mais quand vous avez besoin de cette opération seulement une fois que la surcharge constante pour init la table est trop grande, et le balayage + comptage à travers l'int est beaucoup plus rapide malgré.

Je suppose que le meilleur serait une combinaison: Rechercher une table pour un octet ou un mot (256 ou 64k entrées n'est pas beaucoup), puis combiner les octets/mots par leur dernier/premier bit.

Answer 5

en C/C++ je ferais ce qui suit:

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

Voici le code à l'aide décalage arithmétique + XOR et la méthode de Kernighan pour le comptage de bits :

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; 
}