Il modo più veloce per contare il numero di transizioni di bit in un int senza segno

Question

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

Se int contiene: 0b00000000000000000000000000001010

Il numero di transizioni è: 4

Se int contiene: 0b00000000000000000000000000001001

Il numero di transizioni è: 3

La 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'implementazione efficiente di CountBits vedi http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Answer 2

Il più veloce dipende dal tuo scenario: Quando hai specificato il tipo di dati come dimensione costante (int senza segno), è possibile con la tabella di ricerca. Ma quando hai bisogno di questa operazione solo una volta il sovraccarico costante per iniziare la tabella è troppo grande, e la scansione + il conteggio degli int è molto più veloce nonostante.

Immagino che la migliore sia una combinazione: cerca una tabella per un byte o una parola (256 o 64k voci non sono così tante), quindi combina i byte / parole con il loro ultimo / primo bit.

Answer 3

In C / C ++ farei quanto segue:

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

Ecco il codice usando arithmetic shift + xor e il metodo di Kernighan per il conteggio dei 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;
}

Answer 5

Quale lingua?

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

Answer 6

Ok, con transizioni che intendi se cammini attraverso la stringa di 0-se 1-s, conti ogni occasione in cui uno 0 segue un 1 o un 1 segue uno 0.

Questo è facile spostando i bit e contando le 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

puoi sostituire mod e div con turni.