Bit twiddling: ¿qué bit está configurado?

Question

Tengo un entero sin signo de 64 bits con exactamente 1 bit configurado. Me gustaría asignar un valor a cada uno de los posibles 64 valores (en este caso, los primos impares, por lo que 0x1 corresponde a 3, 0x2 corresponde a 5, ..., 0x8000000000000000 corresponde a 313).

Parece que la mejor manera sería convertir 1 -> 0, 2 -> 1, 4 -> 2, 8 -> 3, ..., 2^63 -> 63 y buscar los valores en una matriz. Pero incluso si eso es así, no estoy seguro de cuál es la forma más rápida de llegar al exponente binario. Y aún puede haber formas más rápidas/mejores.

Esta operación se utilizará a 10 veces, por lo que el rendimiento es un problema grave.

Answer 1

Si el rendimiento es un problema grave, entonces debe usar intrínsecos/órdenes internas para usar las instrucciones específicas de la CPU, como los que se encuentran aquí para gcc:

http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc/Other-Builtins.html

- Función incorporada: int __builtin_ffs (unsigned int x) Devoluciones uno más el índice del menos significativo de 1 bit de x, o si x es cero, devuelve cero.

- Función incorporada: int __builtin_clz (unsigned int x) Devuelve el número de 0 bits iniciales en x, comenzando en la posición de bit más significativa. Si x es 0, el resultado no está definido.

- Función incorporada: int __builtin_ctz (unsigned int x) Devuelve el número de 0 bits finales en x, comenzando en la posición de bit menos significativa. Si x es 0, el resultado no está definido.

Este tipo de cosas son el núcleo de muchos algoritmos O (1) como los programadores de núcleo que necesitan encontrar la primera cola no vacía significada por una matriz de bits.

NOTA: He enumerado las versiones unsigned int, pero gcc también tiene versiones unsigned long long también.

Answer 2

unsigned bit_position = 0; 
while ((value & 1) ==0) 
{ 
    ++bit_position; 
    value >>= 1; 
} 

A continuación, busque los números primos según bit_position como usted dice.

Answer 3

puede encontrar que el registro (n)/log (2) le da el 0, 1, 2, ... que está buscando en un plazo razonable. De lo contrario, alguna forma de enfoque basado en hashtable podría ser útil.

Answer 4

Algunas arquitecturas (un número sorprendente, en realidad) tienen una sola instrucción que puede hacer el cálculo que desee. En ARM sería la instrucción CLZ (contar ceros a la izquierda). Para intel, la instrucción BSF (escaneo de bits hacia adelante) o BSR (escaneo de bit inverso) lo ayudaría.

Supongo que esto no es realmente una respuesta C, pero le dará la velocidad que necesita!

Answer 5

• precalcular 1 < < i (para i = 0..63) y almacenarlos en una matriz
• utilizar una búsqueda binaria para encontrar el índice en la matriz de un valor dado
• buscar el número primo en otra matriz usando este índice

En comparación con la otra respuesta que publiqué aquí, esto solo debería tomar 6 pasos para encontrar el índice (en lugar de un máximo de 64). Pero no está claro para mí si un paso de esta respuesta no consume más tiempo que simplemente cambiar e incrementar un contador. Es posible que desee probar ambos sin embargo.

Answer 6

se puede utilizar una técnica de búsqueda binaria:

int pos = 0; 
if ((value & 0xffffffff) == 0) { 
    pos += 32; 
    value >>= 32; 
} 
if ((value & 0xffff) == 0) { 
    pos += 16; 
    value >>= 16; 
} 
if ((value & 0xff) == 0) { 
    pos += 8; 
    value >>= 8; 
} 
if ((value & 0xf) == 0) { 
    pos += 4; 
    value >>= 4; 
} 
if ((value & 0x3) == 0) { 
    pos += 2; 
    value >>= 2; 
} 
if ((value & 0x1) == 0) { 
    pos += 1; 
} 

Esto tiene la ventaja sobre los lazos que el bucle ya se desenrolla. Sin embargo, si esto es realmente crítico para el rendimiento, querrá probar y medir cada solución propuesta.

Answer 7

Si no se usan las extensiones de compilación o específicas del compilador para encontrar el primer/último bit que se establece, el algoritmo más rápido es una búsqueda binaria. Primero compruebe si alguno de los primeros 32 bits está configurado. Si es así, verifique si alguno de los primeros 16 están configurados. Si es así, verifique si alguno de los primeros 8 está configurado. Etc. Su función para hacer esto puede devolver directamente un primo impar en cada hoja de la búsqueda, o puede devolver un índice de bit que utiliza como un índice de matriz en una tabla de primos impares.

Aquí hay una aplicación de lazo para la búsqueda binaria, que el compilador podría ciertamente desenrollar si eso considera que es óptima:

uint32_t mask=0xffffffff; 
int pos=0, shift=32, i; 
for (i=6; i; i--) { 
    if (!(val&mask)) { 
     val>>=shift; 
     pos+=shift; 
    } 
    shift>>=1; 
    mask>>=shift; 
} 

val se supone que es uint64_t, pero para optimizar esto para máquinas de 32 bits, debe hacer un caso especial en la primera comprobación, luego realizar el ciclo con una variable val de 32 bits.

Answer 8

Ver específicamente http://graphics.stanford.edu/~seander/bithacks.html - Específicamente "Encontrar la base 2 del registro entero de un entero (también conocido como la posición del conjunto de bits más alto)" - para algunos algoritmos alternativos. (Si realmente habla en serio sobre la velocidad, puede considerar abandonar C si su CPU tiene una instrucción específica).

Answer 9

Otra respuesta asumiendo IEEE float:

int get_bit_index(uint64_t val) 
{ 
    union { float f; uint32_t i; } u = { val }; 
    return (u.i>>23)-127; 
} 

Funciona como se especifica para los valores de entrada que pidió (exactamente conjunto 1 bit) y también tiene un comportamiento útil para otros valores (tratar de averiguar exactamente lo que se comportamiento es). No tengo idea de si es rápido o lento; eso probablemente depende de tu máquina y compilador.

Answer 10

Llame a la función de extensión GNU POSIX ffsll, que se encuentra en glibc. Si la función no está presente, retroceda al __builtin_ffsll. Ambas funciones devuelven el index + 1 del primer bit establecido o cero. Con Visual-C++, puede usar _BitScanForward64.

Answer 11

Finalmente una solución óptima. Consulte el final de esta sección para saber qué hacer cuando se garantiza la entrada a tener exactamente un no-cero bits: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

Aquí está el código:

static const int MultiplyDeBruijnBitPosition2[32] = 
{ 
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
}; 
r = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27]; 

Usted puede ser capaz de adaptarse a un directa algoritmo basado en multiplicación para entradas de 64 bits; de lo contrario, simplemente agregue un condicional para ver si el bit está en las 32 posiciones superiores o en las 32 posiciones más bajas, luego use el algoritmo de 32 bits aquí.

Actualización: Aquí hay al menos una versión de 64 bits que acabo de desarrollar, pero usa división (en realidad módulo).

r = Table[v%67]; 

Para cada potencia de 2, v%67 tiene un valor distinto, por lo que sólo hay que poner sus primos impares (o índices de bit si no quiere lo raro de alto riesgo) en las posiciones correctas en la tabla. No se utilizan 3 posiciones (0, 17 y 34), lo que podría ser conveniente si también desea aceptar todos los bits cero como una entrada.

Actualización 2: versión de 64 bits.

r = Table[(uint64_t)(val * 0x022fdd63cc95386dull) >> 58]; 

Ésta es mi obra original, pero me dio la B(2,6)De Bruijn sequence de this chess site así que no puedo tomar el crédito para cualquier cosa menos averiguar lo que una secuencia De Bruijn y es a través de Google. ;-)

Algunas observaciones adicionales sobre cómo funciona esto:

El número mágico es una secuencia B(2,6) De Bruijn. Tiene la propiedad de que, si observa una ventana de 6 bits consecutivos, puede obtener cualquier valor de seis bits en esa ventana girando el número de manera apropiada, y que cada posible valor de seis bits se obtiene con exactamente una rotación.

Arreglamos la ventana en cuestión para que sea la posición más alta de 6 bits, y seleccionamos una secuencia De Bruijn con 0 en los primeros 6 bits. Esto hace que no tengamos que lidiar con rotaciones de bits, solo cambios, ya que los 0 entrarán en los bits inferiores naturalmente (y nunca podríamos terminar mirando más de 5 bits desde la parte inferior en la ventana de los 6 bits superiores) .

Ahora, el valor de entrada de esta función es una potencia de 2. Así que multiplicar la secuencia De Bruijn por el valor de entrada realiza una desviación de bits por log2(value) bits. Ahora tenemos en los 6 bits superiores un número que determina de manera única la cantidad de bits por los que pasamos, y puede usar eso como un índice en una tabla para obtener la duración real del cambio.

Este mismo enfoque se puede utilizar para enteros arbitrariamente grandes o arbitrariamente pequeños, siempre que esté dispuesto a implementar la multiplicación. Simplemente tiene que encontrar una secuencia De Bruijn B(2,k) donde k es la cantidad de bits. El enlace de wiki de ajedrez que proporcioné arriba tiene secuencias de De Bruijn para valores de k que van del 1 al 6, y algunos rápidos de Google muestran que hay algunos artículos sobre algoritmos óptimos para generarlos en el caso general.

Answer 12

Desde la fuente gnuchess:

 
unsigned char leadz (BitBoard b) 
/************************************************************************** 
* 
* Returns the leading bit in a bitboard. Leftmost bit is 0 and 
* rightmost bit is 63. Thanks to Robert Hyatt for this algorithm. 
* 
***************************************************************************/ 
{ 
    if (b >> 48) return lzArray[b >> 48]; 
    if (b >> 32) return lzArray[b >> 32] + 16; 
    if (b >> 16) return lzArray[b >> 16] + 32; 
    return lzArray[b] + 48; 
} 

Aquí lzArray es una matriz pregenerated de tamaño 2^16. Esto te ahorrará el 50% de las operaciones en comparación con una búsqueda binaria completa.

Answer 13

Puesto que la velocidad, probablemente no uso de la memoria, es importante, aquí es una idea loca:

W1 = primera 16 bits
w2 = 2º 16 bits
w3 = 3º 16 bits
w4 = cuarto 16 bits

resultado = array1 [w1] + array2 [w2] + array3 [w3] + array4 [w4]

donde array1 ..4 son matrices de 64K poco pobladas que contienen los valores principales reales (y cero en las posiciones que no corresponden a las posiciones de bit)

Answer 14

La solución @Rs es excelente, esta es solo la variante de 64 bits, con la tabla ya calculada. ..

static inline unsigned char bit_offset(unsigned long long self) { 
    static const unsigned char mapping[64] = { 
     [0]=0, [1]=1, [2]=2, [4]=3, [8]=4, [17]=5, [34]=6, [5]=7, 
     [11]=8, [23]=9, [47]=10, [31]=11, [63]=12, [62]=13, [61]=14, [59]=15, 
     [55]=16, [46]=17, [29]=18, [58]=19, [53]=20, [43]=21, [22]=22, [44]=23, 
     [24]=24, [49]=25, [35]=26, [7]=27, [15]=28, [30]=29, [60]=30, [57]=31, 
     [51]=32, [38]=33, [12]=34, [25]=35, [50]=36, [36]=37, [9]=38, [18]=39, 
     [37]=40, [10]=41, [21]=42, [42]=43, [20]=44, [41]=45, [19]=46, [39]=47, 
     [14]=48, [28]=49, [56]=50, [48]=51, [33]=52, [3]=53, [6]=54, [13]=55, 
     [27]=56, [54]=57, [45]=58, [26]=59, [52]=60, [40]=61, [16]=62, [32]=63 
    }; 
    return mapping[((self & -self) * 0x022FDD63CC95386DULL) >> 58]; 
} 

Creé la tabla con la máscara provista.

>>> ', '.join('[{0}]={1}'.format(((2**bit * 0x022fdd63cc95386d) % 2**64) >> 58, bit) for bit in xrange(64)) 
'[0]=0, [1]=1, [2]=2, [4]=3, [8]=4, [17]=5, [34]=6, [5]=7, [11]=8, [23]=9, [47]=10, [31]=11, [63]=12, [62]=13, [61]=14, [59]=15, [55]=16, [46]=17, [29]=18, [58]=19, [53]=20, [43]=21, [22]=22, [44]=23, [24]=24, [49]=25, [35]=26, [7]=27, [15]=28, [30]=29, [60]=30, [57]=31, [51]=32, [38]=33, [12]=34, [25]=35, [50]=36, [36]=37, [9]=38, [18]=39, [37]=40, [10]=41, [21]=42, [42]=43, [20]=44, [41]=45, [19]=46, [39]=47, [14]=48, [28]=49, [56]=50, [48]=51, [33]=52, [3]=53, [6]=54, [13]=55, [27]=56, [54]=57, [45]=58, [26]=59, [52]=60, [40]=61, [16]=62, [32]=63' 

caso de que el compilador se quejan:

>>> ', '.join(map(str, {((2**bit * 0x022fdd63cc95386d) % 2**64) >> 58: bit for bit in xrange(64)}.values())) 
'0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28, 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11, 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10, 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12' 

^^^^ asume que iteramos de claves ordenadas, esto puede no ser el caso en el futuro ...

unsigned char bit_offset(unsigned long long self) { 
    static const unsigned char table[64] = { 
     0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 
     28, 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 
     18, 29, 11, 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 
     21, 23, 58, 17, 10, 51, 25, 36, 32, 60, 20, 57, 16, 50, 
     31, 19, 15, 30, 14, 13, 12 
    }; 
    return table[((self & -self) * 0x022FDD63CC95386DULL) >> 58]; 
} 

prueba simple:

>>> table = {((2**bit * 0x022fdd63cc95386d) % 2**64) >> 58: bit for bit in xrange(64)}.values() 
>>> assert all(i == table[(2**i * 0x022fdd63cc95386d % 2**64) >> 58] for i in xrange(64))