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

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

Si l’int contient: 0b00000000000000000000000000001010

Le nombre de transitions est: 4

Si l’int contient: 0b00000000000000000000000000001001

Le nombre de transitions est: 3

La langue est C.

 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 implémentation efficace de CountBits, voir http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Le plus rapide dépend de votre scénario: Comme vous avez spécifié votre type de données comme étant de taille constante (unsigned int), cela est possible avec la table de recherche. Mais lorsque vous n’avez besoin de cette opération qu’une seule fois, la surcharge constante pour initier la table est trop importante, et le balayage et le comptage via l’int sont bien plus rapides.

Je suppose que le meilleur serait une combinaison: recherchez dans la table un octet ou un mot (256 ou 64 000 entrées n’est pas si important), puis combinez les octets / mots par leur dernier / premier bit.

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

Quelle langue?

Je voudrais boucler 64 fois, puis décaler votre numéro pour inspecter les bits, puis stocker le bit précédent et le comparer au bit actuel. Si c’est différent, incremember votre compte.

Voici le code utilisant arithmetic shift + xor et la méthode de comptage de bits de Kernighan:

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

Ok, avec les transitions vous voulez dire que si vous parcourez la chaîne de 0-s et 1-s, vous comptez chaque fois qu’un 0 suit un 1 ou un 1 suit un 0.

Ceci est facile en décalant les bits et en comptant 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 par des décalages.