and - bitwise operators c++

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 usará 10 ¹⁴ a 10 ¹⁶ veces, por lo que el rendimiento es un problema grave.

Answer 1

A menos que se utilicen extensiones específicas de ensamblador o compilador para encontrar el primer / último bit establecido, 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 implementación de bucle para la búsqueda binaria, que el compilador ciertamente podría desenrollar si se considera óptimo:

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;
}

Se supone que val 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 32 bits.

Answer 2

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 CLZ (count leading CLZ ). Para intel, la instrucción BSF (bit-scan forward) o BSR (bit-scan reverse) lo ayudaría.

¡Supongo que esto no es realmente una respuesta C , pero te dará la velocidad que necesitas!

Answer 3

Como la velocidad, presumiblemente no el uso de memoria, es importante, aquí hay una idea loca:

w1 = 1er 16 bits
w2 = 2do 16 bits
w3 = 3º 16 bits
w4 = 4to 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 los bits)

Answer 4

De la fuente de 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 pregenerada de tamaño 2 ^ 16. Esto te ahorrará el 50% de las operaciones en comparación con una búsqueda binaria completa.

Answer 5

Finalmente una solución óptima. Consulte al final de esta sección qué hacer cuando se garantiza que la entrada tiene exactamente un bit distinto de cero: 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];

Es posible que pueda adaptar esto a un algoritmo basado en multiplicación directa 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, así que simplemente coloque sus primos impares (o índices de bit si no desea la cosa de prima impar) en las posiciones correctas de 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];

Este es mi trabajo original, pero obtuve la secuencia B(2,6) De Bruijn de este sitio de ajedrez, así que no puedo atribuirme el mérito de nada más que descubrir qué es una secuencia de De Bruijn y usar Google. ;-)

Algunos comentarios 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 elegimos 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. Entonces la multiplicación de la secuencia De Bruijn por el valor de entrada realiza un cambio de bits por bits log2(value) . 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 usar para enteros arbitrariamente grandes o arbitrariamente pequeños, siempre que esté dispuesto a implementar la multiplicación. Simplemente tiene que encontrar una secuencia B(2,k) De Bruijn 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 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 6

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];
}

Construí la mesa usando 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''

si el compilador se queja:

>>> '', ''.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 sobre claves ordenadas, este 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))

Answer 7

Llame a la función de extensión POSIX de GNU ffsll , que se encuentra en glibc. Si la función no está presente, http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc/Other-Builtins.html a http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc/Other-Builtins.html . Ambas funciones devuelven el index + 1 del primer bit establecido, o cero. Con Visual-C ++, puede usar _BitScanForward64 .

Answer 8

Otra respuesta suponiendo float IEEE:

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

Funciona según lo especificado para los valores de entrada que solicitó (exactamente 1 bit configurado) y también tiene un comportamiento útil para otros valores (intente averiguar exactamente cuál es ese comportamiento). No tengo idea de si es rápido o lento; eso probablemente depende de tu máquina y compilador.

Answer 9

Podría usar 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 bucles que el bucle ya está desenrollado. Sin embargo, si esto es realmente crítico para el rendimiento, querrá probar y medir cada solución propuesta.

Answer 10

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

Answer 11

Si el rendimiento es un problema grave, entonces debe usar intrinsics / builtins para usar instrucciones específicas de CPU como las 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) Devuelve 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 principales 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 de O (1) como los programadores de kernel 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 .

Answer 12

Ver 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 13

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

Luego busca los números primos basados ​​en bit_position como dices.

Answer 14

• precalcula 1 << i (para i = 0..63) y guárdalos en una matriz
• usa una búsqueda binaria para encontrar el índice en la matriz de un valor dado
• busca 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 oposición a 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.