Eficientes operaciones bit a bit para contar bits o encontrar los más adecuados |

Dado un int sin firmar, tengo que implementar las siguientes operaciones:

  1. Cuente la cantidad de bits configurados en 1
  2. Encuentre el índice del bit más a la izquierda
  3. Encuentre el índice del más cercano 1 bit

(la operación no debería ser dependientes de la architecture).

Lo he hecho usando un desplazamiento bit a bit, pero tengo que iterar a través de casi todos los bits (es.32). Por ejemplo, contar 1’s:

unsigned int number= ...; while(number != 0){ if ((number & 0x01) != 0) ++count; number >>=1; } 

Las otras operaciones son similares.

Entonces mi pregunta es: ¿hay alguna manera más rápida de hacer eso?

Si quieres la forma más rápida, necesitarás usar métodos no portátiles.

Windows / MSVC:

  • _BitScanForward ()
  • _BitScanReverse ()
  • __popcnt ()

GCC:

  • __builtin_ffs ()
  • __builtin_ctz ()
  • __builtin_clz ()
  • __builtin_popcount ()

Por lo general, se asignan directamente a las instrucciones de hardware nativas. Por lo tanto, no es mucho más rápido que estos.

Pero como no hay funcionalidad C / C ++ para ellos, solo se puede acceder a ellos a través de los intrínsecos del comstackdor.

Eche un vistazo a ffs (3), ffsl (3), fls (3), flsl (3).

Las funciones ffs () y ffsl () encuentran el primer bit establecido (comenzando con el bit menos significativo) en i y devuelven el índice de ese bit.

Las funciones fls () y flsl () encuentran el último bit establecido en i y devuelven el índice de ese bit.

También podría estar interesado en bitstring (3).

Citando de http://graphics.stanford.edu/~seander/bithacks.html

El mejor método para contar bits en un entero de 32 bits v es el siguiente:

 unsigned int v; // count bits set in this (32-bit value) unsigned int c; // store the total here v = v - ((v >> 1) & 0x55555555); // reuse input as temporary v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count 

El mejor método de conteo de bits solo requiere 12 operaciones, que es lo mismo que el método de la tabla de búsqueda, pero evita la memoria y las posibles fallas de la memoria caché de una tabla. Es un híbrido entre el método puramente paralelo anterior y los métodos anteriores que usan multiplicaciones (en la sección sobre conteo de bits con instrucciones de 64 bits), aunque no utiliza instrucciones de 64 bits. Los recuentos de bits establecidos en los bytes se realizan en paralelo, y la sum total de los bits configurados en los bytes se calcula multiplicando por 0x1010101 y desplazando a la derecha 24 bits.

Un enfoque es usar una tabla de búsqueda.

 uint8_t popcount_table[256] = { ... }; uint8_t popcount (uint32_t x) { uint8_t *p = (uint8_t*)&x; return popcount_table[p[0]] + popcount_table[p[1]] + popcount_table[p[2]] + popcount_table[p[3]]; }