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

Question

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

Si l'entier contient: 0b00000000000000000000000000001010

Le nombre de transitions est: 4

Si l'entier contient: 0b00000000000000000000000000001001

Le nombre de transitions est: 3

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

Answer 2

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), il est possible avec une table de correspondance. Mais lorsque vous n’avez besoin de cette opération qu’une seule fois, la surcharge permanente pour initialiser le tableau est trop importante et la numérisation 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.

Answer 3

En C / C ++, je procéderais comme 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 4

Voici le code utilisant l'arithmétique shift + 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;
}

Answer 5

Quelle langue?

Je ferais une boucle 64 fois, puis décalerais votre numéro pour inspecter les bits, puis stockerais le bit précédent et le comparerais au bit actuel. Si c'est différent, incremember votre compte.

Answer 6

Ok, par transitions, vous voulez dire que si vous parcourez la chaîne 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 le div par des décalages.