Posición del bit menos significativo que se establece

120

Estoy buscando una forma eficiente de determinar la posición del bit menos significativo que se establece en un entero, por ejemplo, para 0x0FF0 sería 4.

Una implementación trivial es esta:

unsigned GetLowestBitPos(unsigned value)
{
   assert(value != 0); // handled separately

   unsigned pos = 0;
   while (!(value & 1))
   {
      value >>= 1;
      ++pos;
   }
   return pos;
}

¿Alguna idea de cómo sacarle algunos ciclos?

(Nota: esta pregunta es para personas que disfrutan de tales cosas, no para que me digan que la xzoptimización es mala).

[editar] ¡ Gracias a todos por las ideas! También he aprendido algunas otras cosas. ¡Frio!

Peterchen
fuente
while ((valor _N >> (++ pos))! = 0);
Thomas

Respuestas:

170

Bit Twiddling Hacks ofrece una excelente colección de, er, pequeños trucos , con una discusión sobre rendimiento / optimización adjunta. Mi solución favorita para su problema (de ese sitio) es «multiplicar y buscar»:

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[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 = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

Referencias útiles:

Anton Tykhyy
fuente
18
¿Por qué el voto negativo? Esta es posiblemente la implementación más rápida, dependiendo de la velocidad de la multiplicación. Ciertamente es un código compacto, y el truco (v & -v) es algo que todos deberían aprender y recordar.
Adam Davis
2
+1 muy bueno, ¿qué tan costosa es una operación de multiplicación en comparación con una operación if (X&Y)?
Brian R. Bondy
4
¿Alguien sabe cómo se compara el rendimiento de esto con el __builtin_ffslo ffsl?
Steven Lu
2
@Jim Balter, pero el módulo es muy lento en comparación con la multiplicación en hardware moderno. Así que no lo llamaría una mejor solución.
A priori
2
Me parece que tanto el valor 0x01 como el 0x00 dan como resultado el valor 0 de la matriz. Aparentemente, este truco indicará que el bit más bajo se establece si se pasa 0.
abelenky
80

¿Por qué no utilizar los ffs integrados ? (Tomé una página de manual de Linux, pero está más disponible que eso).

ffs (3): página de manual de Linux

Nombre

ffs - encuentra el primer conjunto de bits en una palabra

Sinopsis

#include <strings.h>
int ffs(int i);
#define _GNU_SOURCE
#include <string.h>
int ffsl(long int i);
int ffsll(long long int i);

Descripción

La función ffs () devuelve la posición del primer conjunto de bits (menos significativo) en la palabra i. El bit menos significativo es la posición 1 y la posición más significativa, por ejemplo, 32 o 64. Las funciones ffsll () y ffsl () hacen lo mismo pero toman argumentos de tamaño posiblemente diferente.

Valor devuelto

Estas funciones devuelven la posición del primer conjunto de bits, o 0 si no hay bits en i.

De acuerdo a

4.3BSD, POSIX.1-2001.

Notas

Los sistemas BSD tienen un prototipo en formato <string.h>.

efímero
fuente
6
Para su información, esto se compila en el comando de ensamblaje correspondiente cuando está disponible.
Jérémie
46

Hay una instrucción de ensamblaje x86 ( bsf) que lo hará. :)

¿Más optimizado?

Nota al margen:

La optimización en este nivel depende inherentemente de la arquitectura. Los procesadores actuales son demasiado complejos (en términos de predicción de rama, fallos de caché, canalización) que es tan difícil predecir qué código se ejecuta más rápido en qué arquitectura. Disminuir las operaciones de 32 a 9 o cosas por el estilo podría incluso disminuir el rendimiento en algunas arquitecturas. El código optimizado en una sola arquitectura puede resultar en un código peor en la otra. Creo que optimizaría esto para una CPU específica o lo dejaría como está y dejaría que el compilador elija lo que cree que es mejor.

Mehrdad Afshari
fuente
20
@dwc: Entiendo, pero creo que esta cláusula: "¿Alguna idea de cómo sacarle algunos ciclos?" hace que esa respuesta sea perfectamente aceptable.
Mehrdad Afshari
5
+1 Su respuesta depende necesariamente de su arquitectura debido a la endianidad, por lo que pasar a las instrucciones de ensamblaje es una respuesta perfectamente válida.
Chris Lutz
3
+1 Respuesta inteligente, sí, no es C o C ++, pero es la herramienta adecuada para el trabajo.
Andrew Hare
1
Espera, no importa. El valor real del número entero no importa aquí. Lo siento.
Chris Lutz
2
@Bastian: establecen ZF = 1 si el operando es cero.
Mehrdad Afshari
43

La mayoría de las arquitecturas modernas tendrán alguna instrucción para encontrar la posición del bit establecido más bajo, o el bit establecido más alto, o contar el número de ceros iniciales, etc.

Si tiene alguna instrucción de esta clase, puede emular a las demás de forma económica.

Tómese un momento para trabajarlo en papel y darse cuenta de que x & (x-1)borrará el bit establecido más bajo en x, y ( x & ~(x-1) )devolverá solo el bit establecido más bajo, independientemente de la arquitectura, la longitud de la palabra, etc. Sabiendo esto, es trivial usar hardware de conteo líder -zeroes / mayor-conjunto-bit para encontrar el bit de conjunto más bajo si no hay una instrucción explícita para hacerlo.

Si no hay soporte de hardware relevante en absoluto, la implementación de multiplicar y buscar de los ceros delanteros del recuento que se proporciona aquí iniciales o uno de los de la página Bit Twiddling Hacks se puede convertir trivialmente para dar el bit más bajo usando las identidades anteriores y tiene la ventaja de no tener ramificaciones.

sombra de Luna
fuente
18

Vaya, muchas soluciones y ni un punto de referencia a la vista. Ustedes deberían estar avergonzados de ustedes mismos ;-)

Mi máquina es una Intel i530 (2,9 GHz), con Windows 7 de 64 bits. Compilé con una versión de 32 bits de MinGW.

$ gcc --version
gcc.exe (GCC) 4.7.2

$ gcc bench.c -o bench.exe -std=c99 -Wall -O2
$ bench
Naive loop.         Time = 2.91  (Original questioner)
De Bruijn multiply. Time = 1.16  (Tykhyy)
Lookup table.       Time = 0.36  (Andrew Grant)
FFS instruction.    Time = 0.90  (ephemient)
Branch free mask.   Time = 3.48  (Dan / Jim Balter)
Double hack.        Time = 3.41  (DocMax)

$ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native
$ bench
Naive loop.         Time = 2.92
De Bruijn multiply. Time = 0.47
Lookup table.       Time = 0.35
FFS instruction.    Time = 0.68
Branch free mask.   Time = 3.49
Double hack.        Time = 0.92

Mi código:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


#define ARRAY_SIZE 65536
#define NUM_ITERS 5000  // Number of times to process array


int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            if (value == 0)
                continue;
            unsigned pos = 0;
            while (!(value & 1))
            {
                value >>= 1;
                ++pos;
            }
            total += pos + 1;
        }
    }

    return total;
}


int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE])
{
    static const int MultiplyDeBruijnBitPosition[32] = 
    {
       1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9, 
       32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
    };

    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned int c = nums[i];
            total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27];
        }
    }

    return total;
}


unsigned char lowestBitTable[256];
int get_lowest_set_bit(unsigned num) {
    unsigned mask = 1;
    for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
        if (num & mask) {
            return cnt;
        }
    }

    return 0;
}
int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned int value = nums[i];
            // note that order to check indices will depend whether you are on a big 
            // or little endian machine. This is for little-endian
            unsigned char *bytes = (unsigned char *)&value;
            if (bytes[0])
                total += lowestBitTable[bytes[0]];
            else if (bytes[1])
              total += lowestBitTable[bytes[1]] + 8;
            else if (bytes[2])
              total += lowestBitTable[bytes[2]] + 16;
            else
              total += lowestBitTable[bytes[3]] + 24;
        }
    }

    return total;
}


int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            total +=  __builtin_ffs(nums[i]);
        }
    }

    return total;
}


int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            int i16 = !(value & 0xffff) << 4;
            value >>= i16;

            int i8 = !(value & 0xff) << 3;
            value >>= i8;

            int i4 = !(value & 0xf) << 2;
            value >>= i4;

            int i2 = !(value & 0x3) << 1;
            value >>= i2;

            int i1 = !(value & 0x1);

            int i0 = (value >> i1) & 1? 0 : -32;

            total += i16 + i8 + i4 + i2 + i1 + i0 + 1;
        }
    }

    return total;
}


int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            double d = value ^ (value - !!value); 
            total += (((int*)&d)[1]>>20)-1022; 
        }
    }

    return total;
}


int main() {
    unsigned nums[ARRAY_SIZE];
    for (int i = 0; i < ARRAY_SIZE; i++) {
        nums[i] = rand() + (rand() << 15);
    }

    for (int i = 0; i < 256; i++) {
        lowestBitTable[i] = get_lowest_set_bit(i);
    }


    clock_t start_time, end_time;
    int result;

    start_time = clock();
    result = find_first_bits_naive_loop(nums);
    end_time = clock();
    printf("Naive loop.         Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_de_bruijn(nums);
    end_time = clock();
    printf("De Bruijn multiply. Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_lookup_table(nums);
    end_time = clock();
    printf("Lookup table.       Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_ffs_instruction(nums);
    end_time = clock();
    printf("FFS instruction.    Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_branch_free_mask(nums);
    end_time = clock();
    printf("Branch free mask.   Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_double_hack(nums);
    end_time = clock();
    printf("Double hack.        Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}
Andrew Bainbridge
fuente
8
Los puntos de referencia tanto para De Bruijn como para la búsqueda podrían ser engañosos: sentados en un bucle cerrado como ese, después de la primera operación, las tablas de búsqueda para cada tipo se anclarán en la caché L1 hasta después del último bucle. No es probable que coincida con el uso del mundo real.
MattW
1
Para las entradas con un cero en el byte bajo, obtiene los bytes más altos almacenando / recargando en lugar de desplazarse, debido a la conversión del puntero. (Por cierto, totalmente innecesario, y lo hace dependiente de endian a diferencia de un cambio que no lo haría). De todos modos, el microbenchmark no solo es poco realista debido a la caché en caliente, sino que también tiene los predictores de rama preparados y prueba las entradas que predicen muy bien y hacen que la LUT funcione menos. Muchos casos de uso reales tienen una distribución más uniforme de resultados, no de entradas.
Peter Cordes
2
Su bucle FFS desafortunadamente se ralentiza por una dependencia falsa en la instrucción BSF que su viejo compilador no evita ( pero el gcc más nuevo debería hacerlo, lo mismo para popcnt / lzcnt / tzcnt . BSFTiene una dependencia falsa en su salida (ya que el comportamiento real cuando input = 0 es dejar la salida sin cambios). gcc desafortunadamente convierte esto en una dependencia de bucle al no borrar el registro entre iteraciones de bucle. Por lo tanto, el bucle debe ejecutarse en uno de cada 5 ciclos, cuello de botella en BSF (3) + CMOV (2) latencia.
Peter Cordes
1
Su punto de referencia encontró que el LUT tiene casi exactamente el doble del rendimiento del método FFS, que coincide con mi predicción de análisis estático muy bien :). Tenga en cuenta que está midiendo el rendimiento, no la latencia, porque la única dependencia en serie en su bucle se suma al total. Sin la falsa dependencia, ffs()debería haber tenido un rendimiento de uno por reloj (3 uops, 1 para BSF y 2 para CMOV, y pueden ejecutarse en diferentes puertos). Con la misma sobrecarga de bucle, son 7 uops ALU que pueden ejecutarse (en su CPU) a 3 por reloj. ¡Domina los gastos generales! Fuente: agner.org/optimize
Peter Cordes
1
Sí, la ejecución fuera de orden podría superponerse a múltiples iteraciones del bucle si bsf ecx, [ebx+edx*4]no se tratara ecxcomo una entrada que tenía que esperar. (ECX fue escrito por última vez por CMOV del iteraton anterior). Pero la CPU se comporta de esa manera, para implementar el comportamiento "dejar dest sin modificar si la fuente es cero" (por lo que no es realmente un depósito falso como lo es para TZCNT; se requiere una dependencia de datos porque no hay bifurcación + ejecución especulativa en la suposición que la entrada es distinta de cero). Podríamos superarlo agregando un xor ecx,ecxantes del bsf, para romper la dependencia de ECX.
Peter Cordes
17

La solución más rápida (no intrínseca / no ensambladora) para esto es encontrar el byte más bajo y luego usar ese byte en una tabla de búsqueda de 256 entradas. Esto le da un rendimiento en el peor de los casos de cuatro instrucciones condicionales y en el mejor de los casos de 1. No solo es la menor cantidad de instrucciones, sino la menor cantidad de ramificaciones, lo cual es muy importante en el hardware moderno.

Su tabla (256 entradas de 8 bits) debe contener el índice del LSB para cada número en el rango 0-255. Verifica cada byte de su valor y encuentra el byte más bajo distinto de cero, luego usa este valor para buscar el índice real.

Esto requiere 256 bytes de memoria, pero si la velocidad de esta función es tan importante, entonces vale la pena usar 256 bytes.

P.ej

byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};

unsigned GetLowestBitPos(unsigned value)
{
  // note that order to check indices will depend whether you are on a big 
  // or little endian machine. This is for little-endian
  byte* bytes = (byte*)value;
  if (bytes[0])
    return lowestBitTable[bytes[0]];
  else if (bytes[1])
      return lowestBitTable[bytes[1]] + 8;
  else if (bytes[2])
      return lowestBitTable[bytes[2]] + 16;
  else
      return lowestBitTable[bytes[3]] + 24;  
}
Andrew Grant
fuente
1
En realidad, es el peor de los casos de tres condicionales :) Pero sí, este es el enfoque más rápido (y generalmente lo que la gente busca en preguntas de entrevistas como esta).
Brian
4
¿No quieres un +8, +16, +24 en alguna parte?
Mark Ransom
7
Cualquier tabla de búsqueda aumenta la posibilidad de que se pierda la memoria caché y puede incurrir en el costo de acceso a la memoria, que puede ser varios órdenes de magnitud más alto que ejecutar instrucciones.
Mehrdad Afshari
1
Incluso usaría cambios de bits (cambiándolos en 8 cada vez). entonces podría hacerse completamente usando registros. utilizando punteros, tendrá que acceder a la memoria.
Johannes Schaub - litb
1
Solución razonable, pero entre la posibilidad de que la tabla de búsqueda no esté en la memoria caché (que se puede resolver, como se señaló) y la cantidad de ramas (posible error de predicción de la rama), prefiero la solución de multiplicar y buscar (sin ramas, tabla de búsqueda más pequeña). Por supuesto, si puede usar intrínsecos o ensamblado en línea, probablemente sean una mejor opción. Aún así, esta solución no está mal.
13

Dios mío tiene esto en espiral.

Lo que falta en la mayoría de estos ejemplos es un poco de comprensión sobre cómo funciona todo el hardware.

Siempre que tenga una rama, la CPU tiene que adivinar qué rama se tomará. La tubería de instrucciones se carga con las instrucciones que conducen por la ruta adivinada. Si la CPU ha adivinado mal, la tubería de instrucciones se vacía y se debe cargar la otra rama.

Considere el simple bucle while en la parte superior. La suposición será mantenerse dentro del ciclo. Estará mal al menos una vez cuando salga del bucle. Esto descargará la tubería de instrucciones. Este comportamiento es un poco mejor que adivinar que abandonará el bucle, en cuyo caso eliminaría la tubería de instrucciones en cada iteración.

La cantidad de ciclos de CPU que se pierden varía mucho de un tipo de procesador a otro. Pero puede esperar entre 20 y 150 ciclos de CPU perdidos.

El siguiente grupo peor es donde cree que va a ahorrar algunas iteraciones dividiendo el valor en partes más pequeñas y agregando varias ramas más. Cada una de estas ramas agrega una oportunidad adicional para descargar la tubería de instrucción y cuesta otros 20 a 150 ciclos de reloj.

Consideremos lo que sucede cuando busca un valor en una tabla. Es probable que el valor no esté actualmente en la caché, al menos no la primera vez que se llama a su función. Esto significa que la CPU se detiene mientras el valor se carga desde la caché. Nuevamente, esto varía de una máquina a otra. Los nuevos chips de Intel utilizan esto como una oportunidad para intercambiar subprocesos mientras el subproceso actual espera a que se complete la carga de la caché. Esto podría ser fácilmente más costoso que una descarga de tubería de instrucciones, sin embargo, si realiza esta operación varias veces, es probable que solo ocurra una vez.

Claramente, la solución de tiempo constante más rápida es aquella que involucra matemáticas deterministas. Una solución pura y elegante.

Mis disculpas si esto ya estaba cubierto.

Todos los compiladores que utilizo, excepto XCODE AFAIK, tienen elementos intrínsecos de compilador tanto para la exploración de bits directa como para la exploración de bits inversa. Estos se compilarán en una sola instrucción de ensamblaje en la mayoría de hardware sin Cache Miss, sin Branch Miss-Prediction y Ningún otro programador generó obstáculos.

Para los compiladores de Microsoft, use _BitScanForward & _BitScanReverse.
Para GCC, use __builtin_ffs, __builtin_clz, __builtin_ctz.

Además, absténgase de publicar una respuesta y engañar a los recién llegados si no tiene el conocimiento suficiente sobre el tema que se está discutiendo.

Lo siento, olvidé totalmente proporcionar una solución. Este es el código que uso en el iPad que no tiene instrucciones de nivel de ensamblaje para la tarea:

unsigned BitScanLow_BranchFree(unsigned value)
{
    bool bwl = (value & 0x0000ffff) == 0;
    unsigned I1 = (bwl * 15);
    value = (value >> I1) & 0x0000ffff;

    bool bbl = (value & 0x00ff00ff) == 0;
    unsigned I2 = (bbl * 7);
    value = (value >> I2) & 0x00ff00ff;

    bool bnl = (value & 0x0f0f0f0f) == 0;
    unsigned I3 = (bnl * 3);
    value = (value >> I3) & 0x0f0f0f0f;

    bool bsl = (value & 0x33333333) == 0;
    unsigned I4 = (bsl * 1);
    value = (value >> I4) & 0x33333333;

    unsigned result = value + I1 + I2 + I3 + I4 - 1;

    return result;
}

Lo que hay que entender aquí es que no es la comparación lo que es caro, sino la rama que se produce después de la comparación. En este caso, la comparación se fuerza a un valor de 0 o 1 con .. == 0, y el resultado se usa para combinar las matemáticas que se habrían producido en cualquier lado de la rama.

Editar:

El código anterior está totalmente roto. Este código funciona y aún no tiene ramificaciones (si está optimizado):

int BitScanLow_BranchFree(ui value)
{
    int i16 = !(value & 0xffff) << 4;
    value >>= i16;

    int i8 = !(value & 0xff) << 3;
    value >>= i8;

    int i4 = !(value & 0xf) << 2;
    value >>= i4;

    int i2 = !(value & 0x3) << 1;
    value >>= i2;

    int i1 = !(value & 0x1);

    int i0 = (value >> i1) & 1? 0 : -32;

    return i16 + i8 + i4 + i2 + i1 + i0;
}

Esto devuelve -1 si se le da 0. Si no le importa 0 o está feliz de obtener 31 por 0, elimine el cálculo i0, ahorrando una gran cantidad de tiempo.

Dan
fuente
3
Yo te lo arreglé. Asegúrese de probar lo que publica.
Jim Balter
5
¿Cómo se puede llamar "sin sucursales" cuando incluye un operador ternario?
BoltBait
2
Es un movimiento condicional. Una única instrucción en lenguaje ensamblador que toma ambos valores posibles como parámetros y realiza una operación mov basada en la evaluación del condicional. Y así es "Branch Free". no hay salto a otra dirección desconocida o posiblemente incorrecta.
Dan
FWIW gcc genera ramas incluso en -O3 godbolt.org/z/gcsUHd
Qix - MONICA FUE MALTRATADA
7

Inspirado por esta publicación similar que implica buscar un bit, ofrezco lo siguiente:

unsigned GetLowestBitPos(unsigned value)
{
   double d = value ^ (value - !!value); 
   return (((int*)&d)[1]>>20)-1023; 
}

Pros:

  • sin bucles
  • sin ramificaciones
  • corre en tiempo constante
  • maneja valor = 0 al devolver un resultado que de otro modo estaría fuera de los límites
  • solo dos lineas de codigo

Contras:

  • asume poca endianidad como codificado (se puede arreglar cambiando las constantes)
  • asume que double es un flotante IEEE real * 8 (IEEE 754)

Actualización: como se señaló en los comentarios, una unión es una implementación más limpia (para C, al menos) y se vería así:

unsigned GetLowestBitPos(unsigned value)
{
    union {
        int i[2];
        double d;
    } temp = { .d = value ^ (value - !!value) };
    return (temp.i[1] >> 20) - 1023;
}

Esto supone entradas de 32 bits con almacenamiento little-endian para todo (piense en procesadores x86).

DocMax
fuente
1
Interesante: todavía tengo miedo de usar dobles para aritmética de bits, pero lo tendré en cuenta
peterchen
Usar frexp () podría hacerlo un poco más portátil
conocido como agradable
1
Los juegos de palabras mediante la conversión de punteros no son seguros en C o C ++. Use memcpy en C ++, o una unión en C. (O una unión en C ++ si su compilador garantiza que es seguro. Por ejemplo, las extensiones GNU para C ++ (soportadas por muchos compiladores) garantizan que la combinación de juegos de palabras sea segura)
Peter Cordes
1
El gcc más antiguo también hace un mejor código con una unión en lugar de un puntero-cast: se mueve directamente desde un FP reg (xmm0) a rax (con movq) en lugar de almacenar / recargar. Los gcc y clang más nuevos usan movq en ambos sentidos. Consulte godbolt.org/g/x7JBiL para obtener una versión de unión. ¿Es intencional que esté haciendo un cambio aritmético en 20? Sus supuestos También se enumerarán que intes int32_t, y que firmó desplazamiento a la derecha es un desplazamiento aritmético (en C ++ es de aplicación definidos)
Peter Cordes
1
También por cierto, Visual Studio (2013 al menos) también usa el enfoque test / setcc / sub. Me gusta más el cmp / adc.
DocMax
5

Se puede hacer con el peor de los casos de menos de 32 operaciones:

Principio: comprobación de 2 o más bits es tan eficaz como la comprobación de 1 bit.

Entonces, por ejemplo, no hay nada que le impida verificar en qué agrupación está primero y luego verificar cada bit de menor a mayor en ese grupo.

Entonces ...
si verifica 2 bits a la vez, tiene en el peor de los casos (Nbits / 2) + 1 verificaciones en total.
si marca 3 bits a la vez, tiene en el peor de los casos (Nbits / 3) + 2 comprobaciones en total.
...

Lo óptimo sería verificar en grupos de 4. Lo que en el peor de los casos requeriría 11 operaciones en lugar de 32.

El mejor caso va desde la 1 verificación de sus algoritmos hasta 2 verificaciones si usa esta idea de agrupación. Pero ese 1 cheque adicional en el mejor de los casos vale la pena para ahorrar en el peor de los casos.

Nota: lo escribo en su totalidad en lugar de usar un bucle porque es más eficiente de esa manera.

int getLowestBitPos(unsigned int value)
{
    //Group 1: Bits 0-3
    if(value&0xf)
    {
        if(value&0x1)
            return 0;
        else if(value&0x2)
            return 1;
        else if(value&0x4)
            return 2;
        else
            return 3;
    }

    //Group 2: Bits 4-7
    if(value&0xf0)
    {
        if(value&0x10)
            return 4;
        else if(value&0x20)
            return 5;
        else if(value&0x40)
            return 6;
        else
            return 7;
    }

    //Group 3: Bits 8-11
    if(value&0xf00)
    {
        if(value&0x100)
            return 8;
        else if(value&0x200)
            return 9;
        else if(value&0x400)
            return 10;
        else
            return 11;
    }

    //Group 4: Bits 12-15
    if(value&0xf000)
    {
        if(value&0x1000)
            return 12;
        else if(value&0x2000)
            return 13;
        else if(value&0x4000)
            return 14;
        else
            return 15;
    }

    //Group 5: Bits 16-19
    if(value&0xf0000)
    {
        if(value&0x10000)
            return 16;
        else if(value&0x20000)
            return 17;
        else if(value&0x40000)
            return 18;
        else
            return 19;
    }

    //Group 6: Bits 20-23
    if(value&0xf00000)
    {
        if(value&0x100000)
            return 20;
        else if(value&0x200000)
            return 21;
        else if(value&0x400000)
            return 22;
        else
            return 23;
    }

    //Group 7: Bits 24-27
    if(value&0xf000000)
    {
        if(value&0x1000000)
            return 24;
        else if(value&0x2000000)
            return 25;
        else if(value&0x4000000)
            return 26;
        else
            return 27;
    }

    //Group 8: Bits 28-31
    if(value&0xf0000000)
    {
        if(value&0x10000000)
            return 28;
        else if(value&0x20000000)
            return 29;
        else if(value&0x40000000)
            return 30;
        else
            return 31;
    }

    return -1;
}
Brian R. Bondy
fuente
+1 de mi parte. No es el más rápido, pero es más rápido que el original, que era el punto ...
Andrew Grant
@ onebyone.livejournal.com: Incluso si había un error en el código, el concepto de agrupación es el punto que estaba tratando de transmitir. La muestra de código real no importa mucho y podría hacerse más compacta pero menos eficiente.
Brian R. Bondy
Me pregunto si hay una parte realmente mala de mi respuesta, o si a la gente no le gustó que la escribí en su totalidad.
Brian R. Bondy
@ onebyone.livejournal.com: cuando compara 2 algoritmos, debe compararlos tal como son, sin asumir que uno será transformado mágicamente por una fase de optimización. Tampoco dije nunca que mi algoritmo fuera "más rápido". Solo que son menos operaciones.
Brian R. Bondy
@ onebyone.livejournal.com: ... No necesito perfilar el código anterior para saber que son menos operaciones. Puedo ver eso claramente. Nunca hice ninguna afirmación que requiriera un perfil.
Brian R. Bondy
4

¿Por qué no utilizar la búsqueda binaria ? Esto siempre se completará después de 5 operaciones (asumiendo un tamaño int de 4 bytes):

if (0x0000FFFF & value) {
    if (0x000000FF & value) {
        if (0x0000000F & value) {
            if (0x00000003 & value) {
                if (0x00000001 & value) {
                    return 1;
                } else {
                    return 2;
                }
            } else {
                if (0x0000004 & value) {
                    return 3;
                } else {
                    return 4;
                }
            }
        } else { ...
    } else { ...
} else { ...
fusión de almas
fuente
+1 Esto es muy similar a mi respuesta. El mejor tiempo de ejecución del caso es peor que mi sugerencia, pero el peor tiempo de ejecución es mejor.
Brian R. Bondy
2

Otro método (división y búsqueda de módulos) merece una mención especial aquí desde el mismo enlace proporcionado por @ anton-tykhyy. este método es muy similar en rendimiento al método de multiplicación y búsqueda de DeBruijn con una diferencia leve pero importante.

división y búsqueda de módulos

 unsigned int v;  // find the number of trailing zeros in v
    int r;           // put the result in r
    static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
    {
      32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
      7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
      20, 8, 19, 18
    };
    r = Mod37BitPosition[(-v & v) % 37];

La división de módulo y el método de búsqueda devuelven valores diferentes para v = 0x00000000 yv = FFFFFFFF, mientras que el método de multiplicación y búsqueda de DeBruijn devuelve cero en ambas entradas.

prueba:-

unsigned int n1=0x00000000, n2=0xFFFFFFFF;

MultiplyDeBruijnBitPosition[((unsigned int )((n1 & -n1) * 0x077CB531U)) >> 27]); /* returns 0 */
MultiplyDeBruijnBitPosition[((unsigned int )((n2 & -n2) * 0x077CB531U)) >> 27]); /* returns 0 */
Mod37BitPosition[(((-(n1) & (n1))) % 37)]); /* returns 32 */
Mod37BitPosition[(((-(n2) & (n2))) % 37)]); /* returns 0 */
RaviSharma
fuente
1
modes lento. En su lugar, puede utilizar el método de multiplicar-y-lookup original y restar !va partir rde manejar los casos extremos.
Eitan T
3
@EitanT un optimizador puede también transformar ese mod en una multiplicación rápida como en los hackers deleite
phuclv
2

Según la página BitScan de programación de ajedrez y mis propias medidas, restar y xor es más rápido que negar y enmascarar.

(Tenga en cuenta que si va a contar los ceros finales 0, el método que tengo regresa 63mientras que la negación y la máscara regresan 0).

Aquí hay una resta y xor de 64 bits:

unsigned long v;  // find the number of trailing zeros in 64-bit v 
int r;            // result goes here
static const int MultiplyDeBruijnBitPosition[64] = 
{
  0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
  54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
  46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
  25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v ^ (v-1)) * 0x03F79D71B4CB0A89U)) >> 58];

Como referencia, aquí hay una versión de 64 bits del método de negar y enmascarar:

unsigned long v;  // find the number of trailing zeros in 64-bit v 
int r;            // result goes here
static const int MultiplyDeBruijnBitPosition[64] = 
{
  0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4,
  62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5,
  63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11,
  46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x03F79D71B4CB0A89U)) >> 58];
jnm2
fuente
Esto (v ^ (v-1))funciona proporcionado v != 0. En caso de v == 0que devuelva 0xFF .... FF while (v & -v)da cero (que por cierto también es incorrecto, buf al menos conduce a un resultado razonable).
CiaPan
@CiaPan: Ese es un buen punto, lo mencionaré. Supongo que hay un número de De Bruijn diferente que resolvería esto poniendo 0 en el índice 63.
jnm2
Duh, ahí no es donde está el problema. 0 y 0x8000000000000000 dan como resultado 0xFFFFFFFFFFFFFFFF después v ^ (v-1), por lo que no es posible diferenciarlos. En mi escenario, nunca se ingresará cero.
jnm2
1

Puede comprobar si está configurado alguno de los bits de orden inferior. Si es así, observe el orden inferior de los bits restantes. p.ej,:

32bit int: compruebe si alguno de los primeros 16 está configurado. Si es así, compruebe si alguno de los primeros 8 está configurado. si es así, ....

si no es así, compruebe si alguno de los 16 superiores está configurado.

Esencialmente es una búsqueda binaria.

Ella a
fuente
1

Vea mi respuesta aquí para saber cómo hacerlo con una sola instrucción x86, excepto que para encontrar el bit establecido menos significativo, querrá la BSFinstrucción ("bit scan forward") en lugar de la que se BSRdescribe allí.

timday
fuente
1

Otra solución, posiblemente no la más rápida, pero parece bastante buena.
Al menos no tiene ramas. ;)

uint32 x = ...;  // 0x00000001  0x0405a0c0  0x00602000
x |= x <<  1;    // 0x00000003  0x0c0fe1c0  0x00e06000
x |= x <<  2;    // 0x0000000f  0x3c3fe7c0  0x03e1e000
x |= x <<  4;    // 0x000000ff  0xffffffc0  0x3fffe000
x |= x <<  8;    // 0x0000ffff  0xffffffc0  0xffffe000
x |= x << 16;    // 0xffffffff  0xffffffc0  0xffffe000

// now x is filled with '1' from the least significant '1' to bit 31

x = ~x;          // 0x00000000  0x0000003f  0x00001fff

// now we have 1's below the original least significant 1
// let's count them

x = x & 0x55555555 + (x >>  1) & 0x55555555;
                 // 0x00000000  0x0000002a  0x00001aaa

x = x & 0x33333333 + (x >>  2) & 0x33333333;
                 // 0x00000000  0x00000024  0x00001444

x = x & 0x0f0f0f0f + (x >>  4) & 0x0f0f0f0f;
                 // 0x00000000  0x00000006  0x00000508

x = x & 0x00ff00ff + (x >>  8) & 0x00ff00ff;
                 // 0x00000000  0x00000006  0x0000000d

x = x & 0x0000ffff + (x >> 16) & 0x0000ffff;
                 // 0x00000000  0x00000006  0x0000000d
// least sign.bit pos. was:  0           6          13
CiaPan
fuente
para obtener todos los 1s del 1 menos significativo a LSB, utilice ((x & -x) - 1) << 1en su lugar
phuclv
de una manera aún más rápida:x ^ (x-1)
phuclv
1
unsigned GetLowestBitPos(unsigned value)
{
    if (value & 1) return 1;
    if (value & 2) return 2;
    if (value & 4) return 3;
    if (value & 8) return 4;
    if (value & 16) return 5;
    if (value & 32) return 6;
    if (value & 64) return 7;
    if (value & 128) return 8;
    if (value & 256) return 9;
    if (value & 512) return 10;
    if (value & 1024) return 11;
    if (value & 2048) return 12;
    if (value & 4096) return 13;
    if (value & 8192) return 14;
    if (value & 16384) return 15;
    if (value & 32768) return 16;
    if (value & 65536) return 17;
    if (value & 131072) return 18;
    if (value & 262144) return 19;
    if (value & 524288) return 20;
    if (value & 1048576) return 21;
    if (value & 2097152) return 22;
    if (value & 4194304) return 23;
    if (value & 8388608) return 24;
    if (value & 16777216) return 25;
    if (value & 33554432) return 26;
    if (value & 67108864) return 27;
    if (value & 134217728) return 28;
    if (value & 268435456) return 29;
    if (value & 536870912) return 30;
    return 31;
}

El 50% de todos los números volverán a aparecer en la primera línea de código.

El 75% de todos los números se devolverán en las primeras 2 líneas de código.

El 87% de todos los números volverán en las primeras 3 líneas de código.

El 94% de todos los números volverán en las primeras 4 líneas de código.

El 97% de todos los números volverán en las primeras 5 líneas de código.

etc.

Creo que las personas que se quejan de cuán ineficiente es el peor de los casos para este código no entienden cuán rara sucederá esa condición.

BoltBait
fuente
3
Y el peor de los casos de predicción
1
¿No podría al menos convertirse en un interruptor ...?
Steven Lu
"¿No podría al menos convertirse en un interruptor ...?" ¿Intentaste hacer eso antes de dar a entender que es posible? ¿Desde cuándo puedes hacer cálculos directamente en los casos de un interruptor? Es una tabla de búsqueda, no una clase.
j riv
1

Encontré este ingenioso truco usando 'máscaras mágicas' en "El arte de programar, parte 4", que lo hace en tiempo O (log (n)) para un número de n bits. [con log (n) espacio extra]. Las soluciones típicas que verifican el bit establecido son O (n) o necesitan O (n) espacio adicional para una tabla de consulta, por lo que este es un buen compromiso.

Máscaras mágicas:

m0 = (...............01010101)  
m1 = (...............00110011)
m2 = (...............00001111)  
m3 = (.......0000000011111111)
....

Idea clave: No de ceros finales en x = 1 * [(x & m0) = 0] + 2 * [(x & m1) = 0] + 4 * [(x & m2) = 0] + ...

int lastSetBitPos(const uint64_t x) {
    if (x == 0)  return -1;

    //For 64 bit number, log2(64)-1, ie; 5 masks needed
    int steps = log2(sizeof(x) * 8); assert(steps == 6);
    //magic masks
    uint64_t m[] = { 0x5555555555555555, //     .... 010101
                     0x3333333333333333, //     .....110011
                     0x0f0f0f0f0f0f0f0f, //     ...00001111
                     0x00ff00ff00ff00ff, //0000000011111111 
                     0x0000ffff0000ffff, 
                     0x00000000ffffffff };

    //Firstly extract only the last set bit
    uint64_t y = x & -x;

    int trailZeros = 0, i = 0 , factor = 0;
    while (i < steps) {
        factor = ((y & m[i]) == 0 ) ? 1 : 0;
        trailZeros += factor * pow(2,i);
        ++i;
    }
    return (trailZeros+1);
}
jayadev
fuente
1

Si C ++ 11 está disponible para usted, un compilador a veces puede hacer la tarea por usted :)

constexpr std::uint64_t lssb(const std::uint64_t value)
{
    return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1);
}

El resultado es un índice basado en 1.

Ruslan Garipov
fuente
1
Inteligente, pero se compila en un ensamblaje catastróficamente malo cuando la entrada no es una constante en tiempo de compilación. godbolt.org/g/7ajMyT . (Un bucle tonto sobre los bits con gcc, o una llamada de función recursiva real con clang). Gcc / clang puede evaluar ffs()en tiempo de compilación, por lo que no es necesario usar esto para que funcione la propagación constante. (No tiene que evitar en línea-ASM, por supuesto.) Si realmente necesita algo que funciona como C ++ 11 constexpr, todavía se puede usar GNU C __builtin_ffs.
Peter Cordes
0

Esto es en lo que respecta a la respuesta de @Anton Tykhyy

Aquí está mi implementación de constexpr de C ++ 11 eliminando las conversiones y eliminando una advertencia en VC ++ 17 al truncar un resultado de 64 bits a 32 bits:

constexpr uint32_t DeBruijnSequence[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
};
constexpr uint32_t ffs ( uint32_t value )
{
    return  DeBruijnSequence[ 
        (( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
            >> 27];
}

Para solucionar el problema de 0x1 y 0x0 que devuelven 0, puede hacer lo siguiente:

constexpr uint32_t ffs ( uint32_t value )
{
    return (!value) ? 32 : DeBruijnSequence[ 
        (( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
            >> 27];
}

pero si el compilador no puede o no preprocesa la llamada, agregará un par de ciclos al cálculo.

Finalmente, si está interesado, aquí hay una lista de afirmaciones estáticas para verificar que el código hace lo que se pretende:

static_assert (ffs(0x1) == 0, "Find First Bit Set Failure.");
static_assert (ffs(0x2) == 1, "Find First Bit Set Failure.");
static_assert (ffs(0x4) == 2, "Find First Bit Set Failure.");
static_assert (ffs(0x8) == 3, "Find First Bit Set Failure.");
static_assert (ffs(0x10) == 4, "Find First Bit Set Failure.");
static_assert (ffs(0x20) == 5, "Find First Bit Set Failure.");
static_assert (ffs(0x40) == 6, "Find First Bit Set Failure.");
static_assert (ffs(0x80) == 7, "Find First Bit Set Failure.");
static_assert (ffs(0x100) == 8, "Find First Bit Set Failure.");
static_assert (ffs(0x200) == 9, "Find First Bit Set Failure.");
static_assert (ffs(0x400) == 10, "Find First Bit Set Failure.");
static_assert (ffs(0x800) == 11, "Find First Bit Set Failure.");
static_assert (ffs(0x1000) == 12, "Find First Bit Set Failure.");
static_assert (ffs(0x2000) == 13, "Find First Bit Set Failure.");
static_assert (ffs(0x4000) == 14, "Find First Bit Set Failure.");
static_assert (ffs(0x8000) == 15, "Find First Bit Set Failure.");
static_assert (ffs(0x10000) == 16, "Find First Bit Set Failure.");
static_assert (ffs(0x20000) == 17, "Find First Bit Set Failure.");
static_assert (ffs(0x40000) == 18, "Find First Bit Set Failure.");
static_assert (ffs(0x80000) == 19, "Find First Bit Set Failure.");
static_assert (ffs(0x100000) == 20, "Find First Bit Set Failure.");
static_assert (ffs(0x200000) == 21, "Find First Bit Set Failure.");
static_assert (ffs(0x400000) == 22, "Find First Bit Set Failure.");
static_assert (ffs(0x800000) == 23, "Find First Bit Set Failure.");
static_assert (ffs(0x1000000) == 24, "Find First Bit Set Failure.");
static_assert (ffs(0x2000000) == 25, "Find First Bit Set Failure.");
static_assert (ffs(0x4000000) == 26, "Find First Bit Set Failure.");
static_assert (ffs(0x8000000) == 27, "Find First Bit Set Failure.");
static_assert (ffs(0x10000000) == 28, "Find First Bit Set Failure.");
static_assert (ffs(0x20000000) == 29, "Find First Bit Set Failure.");
static_assert (ffs(0x40000000) == 30, "Find First Bit Set Failure.");
static_assert (ffs(0x80000000) == 31, "Find First Bit Set Failure.");
Rodrigo Hernandez
fuente
0

Aquí hay una alternativa simple, aunque encontrar registros es un poco costoso.

if(n == 0)
  return 0;
return log2(n & -n)+1;   //Assuming the bit index starts from 1
Siva Prakash
fuente
-3

Recientemente, vi que el primer ministro de Singapur publicó un programa que escribió en Facebook, hay una línea para mencionarlo.

La lógica es simplemente "valor & -valor", suponga que tiene 0x0FF0, luego, 0FF0 & (F00F + 1), que es igual a 0x0010, eso significa que el 1 más bajo está en el cuarto bit .. :)

sean
fuente
1
Esto aísla el bit más bajo pero no le da su posición, que es lo que pide esta pregunta.
rhashimoto
Tampoco creo que esto funcione para encontrar el último bit.
yyny
valor & ~ valor es 0.
khw
Uy, mis ojos se están echando a perder. Confundí un menos con una tilde.
ignore
-8

Si tiene los recursos, puede sacrificar memoria para mejorar la velocidad:

static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };

unsigned GetLowestBitPos(unsigned value)
{
    assert(value != 0); // handled separately
    return bitPositions[value];
}

Nota: Esta tabla consumiría al menos 4 GB (16 GB si dejamos el tipo de retorno comounsigned ). Este es un ejemplo de intercambio de un recurso limitado (RAM) por otro (velocidad de ejecución).

Si su función necesita permanecer portátil y ejecutarse lo más rápido posible a cualquier costo, este sería el camino a seguir. En la mayoría de las aplicaciones del mundo real, una mesa de 4 GB no es realista.

e.James
fuente
1
El rango de la entrada ya está especificado por el tipo de parámetro: 'unsigned' es un valor de 32 bits, así que no, no está bien.
Brian
3
umm ... ¿su sistema mítico y su sistema operativo tienen un concepto de memoria paginada? ¿Cuánto tiempo va a costar eso?
Mikeage
14
Esta es una no respuesta. Su solución es completamente irreal en TODAS las aplicaciones del mundo real y llamarla "compensación" es falso. Su mítico sistema que tiene 16GB de RAM para dedicar a una sola función simplemente no existe. También habrías estado respondiendo "usa una computadora cuántica".
Brian
3
¿Sacrificar la memoria por la velocidad? Una tabla de búsqueda de 4GB + nunca encajará en el caché en ninguna máquina existente actualmente, por lo que me imagino que esto es probablemente más lento que casi todas las otras respuestas aquí.
1
Argh. Esta horrible respuesta me persigue :)@Dan: Tienes razón sobre el almacenamiento en caché de la memoria. Vea el comentario de Mikeage arriba.
e.James