La forma más rápida de contar el número de transiciones de bits en un int sin signo

Question

Estoy buscando la forma más rápida de contar el número de transiciones de bits en un unsigned int .

Si el int contiene: 0b00000000000000000000000000001010

El número de transiciones son: 4

Si el int contiene: 0b00000000000000000000000000001001

El número de transiciones son: 3

El idioma es 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
}

Para una implementación eficiente de CountBits vea http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Answer 2

Más rápido depende de su escenario: Como especificó su tipo de datos como de tamaño constante (unsigned int), es posible con la tabla de búsqueda. Pero cuando necesita esta operación solo una vez que la sobrecarga constante para iniciar la tabla es demasiado grande, a pesar de que el escaneo + contar a través de int es mucho más rápido.

Supongo que lo mejor en general sería una combinación: buscar en la tabla un byte o palabra (256 o 64k entradas no es tanto), y luego combinar los bytes / palabras por su último / primer bit.

Answer 3

En C / C ++ haría lo siguiente:

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

Aquí está el código que usa shift aritmético + xor y el método de Kernighan para contar 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

¿Qué idioma?

Realizaría un bucle 64 veces y luego bit cambiaría su número para inspeccionar los bits, luego almacenaría el bit anterior y lo compararía con el actual. Si es diferente, incremente su cuenta.

Answer 6

Ok, con transiciones te refieres si caminas a través de la cadena de 0-sy 1-s, cuentas cada vez que un 0 sigue a un 1 o un 1 sigue a un 0.

Esto es fácil cambiando bits y contando los cambios:

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

puedes reemplazar el mod y div con turnos.