¿Cuál es la forma más rápida / eficiente de encontrar el bit de conjunto más alto (msb) en un entero en C?

119

Si tengo un número entero n, y quiero saber la posición del bit más significativo (es decir, si el bit menos significativo está a la derecha, quiero saber la posición del bit más a la izquierda que es un 1), ¿Cuál es el método más rápido / eficaz para averiguarlo?

Sé que POSIX admite un ffs()método en strings.h para encontrar el primer bit establecido, pero no parece haber un fls()método correspondiente .

¿Hay alguna forma realmente obvia de hacer esto que me falta?

¿Qué sucede en los casos en los que no puede usar las funciones POSIX para la portabilidad?

Editar: ¿Qué pasa con una solución que funciona en arquitecturas de 32 y 64 bits (parece que muchos de los listados de código solo funcionarían en entradas de 32 bits)?

Zxaos
fuente
aquí hay algunas implementaciones: graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear (Editar: después de volver a leer su pregunta, me doy cuenta de que el enlace de arriba es para encontrar el bit establecido más a la derecha, no a la izquierda como necesita, aunque sin un sentido del tamaño de la palabra, es difícil de responder)
gastador
Eso cuenta ceros a la derecha ; la pregunta era sobre ceros a la izquierda. Al menos, en un vistazo rápido, no lo veo allí.
Darius Bacon
2
¿Quiere específicamente el número de bit 'n', o sería suficiente con 2 ^ n?
Alnitak
1
Mire los algoritmos "Log Base 2", como dice Anderson en el artículo: "La base log 2 de un entero es la misma que la posición del conjunto de bits más alto (o conjunto de bits más significativo, MSB)"
Michael Burr

Respuestas:

64

GCC tiene :

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

 - Función incorporada: int __builtin_clzl (unsigned long)
     Similar a `__builtin_clz ', excepto que el tipo de argumento es` unsigned
     largo'.

 - Función incorporada: int __builtin_clzll (unsigned long long)
     Similar a `__builtin_clz ', excepto que el tipo de argumento es` unsigned
     largo largo'.

Espero que se traduzcan en algo razonablemente eficiente para su plataforma actual, ya sea uno de esos sofisticados algoritmos de jugueteo de bits o una sola instrucción.


Un truco útil si su entrada puede ser cero es __builtin_clz(x | 1): establecer incondicionalmente el bit bajo sin modificar ningún otro hace que la salida sea 31para x=0, sin cambiar la salida para ninguna otra entrada.

Para evitar tener que hacer eso, su otra opción son intrínsecos específicos de la plataforma como ARM GCC __clz(no se necesita encabezado) o x86 _lzcnt_u32en CPU que admiten la lzcntinstrucción. (Tenga en cuenta que lzcntdecodifica como bsren CPU más antiguas en lugar de fallar, lo que da 31-lzcnt para entradas distintas de cero).

Desafortunadamente, no hay forma de aprovechar de manera portátil las diversas instrucciones CLZ en plataformas que no son x86 que definen el resultado para input = 0 como 32 o 64 (según el ancho del operando). x86 también lzcnthace eso, mientras que bsrproduce un índice de bits que el compilador tiene que cambiar a menos que usted lo use 31-__builtin_clz(x).

(El "resultado indefinido" no es C Undefined Behavior, solo un valor que no está definido. En realidad, es lo que estaba en el registro de destino cuando se ejecutó la instrucción. AMD documenta esto, Intel no lo hace, pero las CPU de Intel implementan ese comportamiento . Pero es que no lo estaba previamente en la variable C que está asignando a, eso no es por lo general cómo funcionan las cosas cuando gcc convierte en C asm. Véase también ¿por qué romper la "dependencia de salida" de LZCNT importa? )

efímero
fuente
5
MSVC tendrá _BitScanReverse
ratchet freak
1
El comportamiento indefinido en cero les permite compilar en una sola instrucción BSR en x86, incluso cuando LZCNT no está disponible. Esta es una gran ventaja para __builtin_ctzover ffs, que se compila en un BSF y un CMOV para manejar el caso de input-was-zero. En arquitecturas sin una implementación lo suficientemente corta (por ejemplo, ARM antiguo sin la clzinstrucción), gcc emite una llamada a una función auxiliar libgcc.
Peter Cordes
41

Asumiendo que está en x86 y juega un poco de ensamblador en línea, Intel proporciona una BSRinstrucción ("exploración de bits inversa"). Es rápido en algunos x86 (microcodificado en otros). Del manual:

Busca en el operando de origen el bit de conjunto más significativo (1 bit). Si se encuentra un 1 bit más significativo, su índice de bits se almacena en el operando de destino. El operando de origen puede ser un registro o una ubicación de memoria; el operando de destino es un registro. El índice de bits es un desplazamiento sin signo del bit 0 del operando fuente. Si el operando de origen del contenido es 0, el contenido del operando de destino no está definido.

(Si está en PowerPC, hay una cntlzinstrucción similar ("contar ceros a la izquierda").)

Código de ejemplo para gcc:

#include <iostream>

int main (int,char**)
{
  int n=1;
  for (;;++n) {
    int msb;
    asm("bsrl %1,%0" : "=r"(msb) : "r"(n));
    std::cout << n << " : " << msb << std::endl;
  }
  return 0;
}

Vea también este tutorial de ensamblador en línea , que muestra (sección 9.4) que es considerablemente más rápido que el código en bucle.

timday
fuente
4
En realidad, esta instrucción suele estar microcodificada en un bucle y es bastante lenta.
rlbond
2
Cúal ? BSR o CNTLZ? Mientras leo el x86-timing.pdf mencionado anteriormente, BSR solo es lento en los Netburst Pentiums. Sin embargo, no sé nada sobre PowerPC.
día
5
... OK, en una inspección más cercana, haga que "BSR solo es rápido en P3 / Pentium-M / Core2 x86s". Lento en Netburst y AMD.
día
1
Solo un aviso: sus dos últimos enlaces están muertos.
Baum mit Augen
2
@rlbond: eh, BSR en P4 Prescott es 2 uops con latencia de 16 ciclos (!), con uno por rendimiento de 4c. Pero en Netburst anterior, es solo una latencia de 4 ciclos (aún 2 uops) y uno por rendimiento de 2c. (fuente: agner.org/optimize ). En la mayoría de las CPU, también tiene una dependencia de su salida que gcc no tiene en cuenta (cuando la entrada es cero, el comportamiento real es dejar el destino sin cambios). Esto puede generar problemas como stackoverflow.com/questions/25078285/… . IDK por qué gcc se perdió BSR al arreglar eso.
Peter Cordes
38

Dado que 2 ^ N es un número entero con solo el N-ésimo conjunto de bits (1 << N), encontrar la posición (N) del conjunto de bits más alto es el número entero base 2 de ese número entero.

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

unsigned int v;
unsigned r = 0;

while (v >>= 1) {
    r++;
}

Este algoritmo "obvio" puede no ser transparente para todos, pero cuando te das cuenta de que el código se desplaza a la derecha un bit repetidamente hasta que el bit más a la izquierda se haya desactivado (ten en cuenta que C trata cualquier valor distinto de cero como verdadero) y devuelve el número de turnos, tiene perfecto sentido. También significa que funciona incluso cuando se establece más de un bit; el resultado es siempre para el bit más significativo.

Si se desplaza hacia abajo en esa página, hay variaciones más rápidas y complejas. Sin embargo, si sabe que está tratando con números con muchos ceros iniciales, el enfoque ingenuo puede proporcionar una velocidad aceptable, ya que el cambio de bits es bastante rápido en C y el algoritmo simple no requiere indexar una matriz.

NOTA: Cuando utilice valores de 64 bits, tenga mucho cuidado con el uso de algoritmos muy inteligentes; muchos de ellos solo funcionan correctamente para valores de 32 bits.

Quinn Taylor
fuente
2
@Johan Pasar por alto con un depurador puede ayudar a explicar por qué sale el bucle. Básicamente, es 'porque la expresión en la condición se evalúa a 0 (que se trata como falsa) una vez que el último bit se ha desplazado hacia la derecha.
Quinn Taylor
2
Buena idea usar el resultado final así :)
Johan
6
nota: debe estar sin signo, para enteros con signo, el desplazamiento a la derecha falla para números negativos.
Xantix
2
Xantix: El cambio en C / C ++ es un cambio lógico, por lo que funciona bien. Para Java, JavaScript o D, debe utilizar el operador de desplazamiento lógico >>>. Más probablemente el comparador != 0y algunos paréntesis no especificados.
Chase
8
@Chase: No, no lo es. Es un cambio lógico para los no firmados . Para con signo , puede ser o no un cambio lógico (y, de hecho, suele ser aritmético).
Tim Čas
17

Esto debería ser increíblemente rápido:

int msb(unsigned int v) {
  static const int pos[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};
  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;
  v = (v >> 1) + 1;
  return pos[(v * 0x077CB531UL) >> 27];
}
Protagonista
fuente
25
Cambios de 7 bits, 5 o instrucciones, una multiplicación y una potencial pérdida de caché. :) ¿Lo comparaste o miraste el ensamblador generado? Se podría acabar bastante lento, dependiendo de cuánto de lo que el compilador puede eliminar.
jalf
5
Soy nuevo aqui. No recibo los votos negativos, chicos. He proporcionado la única respuesta con código fuente que realmente funciona.
Protagonista
9
La "posible falta de caché" probablemente se deba a que este código requiere acceso a su tabla de búsqueda. Si esa tabla no está almacenada en caché cuando se llama, habrá un bloqueo mientras se recupera. Esto podría hacer que el rendimiento en el peor de los casos sea mucho peor que las soluciones que no usan una LUT.
relajarse el
13
no es realmente el punto. Utiliza mucha más caché de datos de la necesaria (más de una línea de caché, incluso) y más caché de instrucciones de la necesaria. Es probable que obtenga errores de caché que podrían haberse evitado la primera vez que llama a la función, y contaminará el caché más de lo necesario, por lo que después de la llamada, otro código puede encontrar más errores de los necesarios. Las LUT a menudo no valen la pena porque las pérdidas de caché son caras. Pero solo dije que era algo que me gustaría comparar antes de afirmar que era "increíblemente rápido". No es que definitivamente sea un problema.
jalf
6
La tabla tiene 32 entradas, y cada valor es <255 (127), así que defina la tabla como tipo unsigned char, y cabrá en una sola línea de caché L1 de 32 bytes. Y todo encaja en dos líneas de caché.
ChuckCottrill
16

Esto es como encontrar una especie de registro de enteros. Hay trucos para jugar un poco, pero he creado mi propia herramienta para ello. El objetivo, por supuesto, es la velocidad.

Me doy cuenta de que la CPU ya tiene un detector de bits automático, que se utiliza para la conversión de enteros a flotantes. Así que usa eso.

double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023;  // assumes x86 endianness

Esta versión convierte el valor en un doble, luego lee el exponente, que le dice dónde estaba el bit. El cambio de fantasía y la resta es extraer las partes adecuadas del valor IEEE.

Es un poco más rápido usar flotadores, pero un flotador solo puede darle las primeras posiciones de 24 bits debido a su menor precisión.


Para hacer esto de manera segura, sin un comportamiento indefinido en C ++ o C, use en memcpylugar de conversión de puntero para juegos de palabras. Los compiladores saben cómo integrarlo de manera eficiente.

// static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64");
// and also static_assert something about FLT_ENDIAN?

double ff=(double)(v|1);

uint32_t tmp;
memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t));
return (tmp>>20)-1023;

O en C99 y posteriores, use a union {double d; uint32_t u[2];};. Pero tenga en cuenta que en C ++, los juegos de palabras de tipo union solo se admiten en algunos compiladores como una extensión, no en ISO C ++.


Por lo general, esto será más lento que un intrínseco específico de la plataforma para una instrucción de conteo de ceros a la izquierda, pero ISO C portátil no tiene tal función. Algunas CPU también carecen de una instrucción de conteo de cero a la izquierda, pero algunas de ellas pueden convertir números enteros a double. Sin embargo, volver a escribir un patrón de bits FP a un número entero puede ser lento (por ejemplo, en PowerPC requiere una función de almacenamiento / recarga y, por lo general, provoca un bloqueo de carga-golpe-almacenamiento).

Este algoritmo podría ser potencialmente útil para implementaciones de SIMD, porque menos CPU tienen SIMD lzcnt. x86 solo recibió tal instrucción con AVX512CD

SPWorley
fuente
2
Si. Y gcc hará cosas desagradables con código como este con -O2 debido a optimizaciones de alias de tipo.
MSN
4
la conversión entre números enteros y punto flotante puede ser sorprendentemente costosa en CPU x86
jalf
1
Sí, los costos de FPU son altos. Pero las mediciones de tiempo real mostraron que esto era más rápido que las operaciones de todos los bits o especialmente cualquier bucle. Pruébalo y toma lo más rápido es siempre el mejor consejo. Sin embargo, no he tenido ningún problema con GCC y -O2 con esto.
SPWorley
1
¿No es este comportamiento indefinido (leer un valor a través de un puntero de un tipo incompatible)?
dreamlax
3
Hacker's Delight explica cómo corregir el error en flotantes de 32 bits en 5-3 contando ceros iniciales. Aquí está su código, que usa una unión anónima para superponer asFloat y asInt: k = k & ~ (k >> 1); asFloat = (flotar) k + 0.5f; n = 158 - (asInt >> 23); (y sí, esto se basa en el comportamiento definido por la implementación)
D Coetzee
11

Kaz Kylheku aquí

Evalué dos enfoques para esto en números de 63 bits (el tipo long long en gcc x86_64), manteniéndome alejado del bit de signo.

(Resulta que necesito este "bit más alto" para algo, ¿sabe?)

Implementé la búsqueda binaria basada en datos (basada en una de las respuestas anteriores). También implementé un árbol de decisiones completamente desenrollado a mano, que es solo código con operandos inmediatos. Sin bucles, sin mesas.

El árbol de decisión (más alto_bits_unrollado) comparado con un 69% más rápido, excepto para el caso n = 0 para el cual la búsqueda binaria tiene una prueba explícita.

La prueba especial de la búsqueda binaria para el caso 0 es solo un 48% más rápida que el árbol de decisiones, que no tiene una prueba especial.

Compilador, máquina: (GCC 4.5.2, -O3, x86-64, Intel Core i5 de 2867 Mhz).

int highest_bit_unrolled(long long n)
{
  if (n & 0x7FFFFFFF00000000) {
    if (n & 0x7FFF000000000000) {
      if (n & 0x7F00000000000000) {
        if (n & 0x7000000000000000) {
          if (n & 0x4000000000000000)
            return 63;
          else
            return (n & 0x2000000000000000) ? 62 : 61;
        } else {
          if (n & 0x0C00000000000000)
            return (n & 0x0800000000000000) ? 60 : 59;
          else
            return (n & 0x0200000000000000) ? 58 : 57;
        }
      } else {
        if (n & 0x00F0000000000000) {
          if (n & 0x00C0000000000000)
            return (n & 0x0080000000000000) ? 56 : 55;
          else
            return (n & 0x0020000000000000) ? 54 : 53;
        } else {
          if (n & 0x000C000000000000)
            return (n & 0x0008000000000000) ? 52 : 51;
          else
            return (n & 0x0002000000000000) ? 50 : 49;
        }
      }
    } else {
      if (n & 0x0000FF0000000000) {
        if (n & 0x0000F00000000000) {
          if (n & 0x0000C00000000000)
            return (n & 0x0000800000000000) ? 48 : 47;
          else
            return (n & 0x0000200000000000) ? 46 : 45;
        } else {
          if (n & 0x00000C0000000000)
            return (n & 0x0000080000000000) ? 44 : 43;
          else
            return (n & 0x0000020000000000) ? 42 : 41;
        }
      } else {
        if (n & 0x000000F000000000) {
          if (n & 0x000000C000000000)
            return (n & 0x0000008000000000) ? 40 : 39;
          else
            return (n & 0x0000002000000000) ? 38 : 37;
        } else {
          if (n & 0x0000000C00000000)
            return (n & 0x0000000800000000) ? 36 : 35;
          else
            return (n & 0x0000000200000000) ? 34 : 33;
        }
      }
    }
  } else {
    if (n & 0x00000000FFFF0000) {
      if (n & 0x00000000FF000000) {
        if (n & 0x00000000F0000000) {
          if (n & 0x00000000C0000000)
            return (n & 0x0000000080000000) ? 32 : 31;
          else
            return (n & 0x0000000020000000) ? 30 : 29;
        } else {
          if (n & 0x000000000C000000)
            return (n & 0x0000000008000000) ? 28 : 27;
          else
            return (n & 0x0000000002000000) ? 26 : 25;
        }
      } else {
        if (n & 0x0000000000F00000) {
          if (n & 0x0000000000C00000)
            return (n & 0x0000000000800000) ? 24 : 23;
          else
            return (n & 0x0000000000200000) ? 22 : 21;
        } else {
          if (n & 0x00000000000C0000)
            return (n & 0x0000000000080000) ? 20 : 19;
          else
            return (n & 0x0000000000020000) ? 18 : 17;
        }
      }
    } else {
      if (n & 0x000000000000FF00) {
        if (n & 0x000000000000F000) {
          if (n & 0x000000000000C000)
            return (n & 0x0000000000008000) ? 16 : 15;
          else
            return (n & 0x0000000000002000) ? 14 : 13;
        } else {
          if (n & 0x0000000000000C00)
            return (n & 0x0000000000000800) ? 12 : 11;
          else
            return (n & 0x0000000000000200) ? 10 : 9;
        }
      } else {
        if (n & 0x00000000000000F0) {
          if (n & 0x00000000000000C0)
            return (n & 0x0000000000000080) ? 8 : 7;
          else
            return (n & 0x0000000000000020) ? 6 : 5;
        } else {
          if (n & 0x000000000000000C)
            return (n & 0x0000000000000008) ? 4 : 3;
          else
            return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
        }
      }
    }
  }
}

int highest_bit(long long n)
{
  const long long mask[] = {
    0x000000007FFFFFFF,
    0x000000000000FFFF,
    0x00000000000000FF,
    0x000000000000000F,
    0x0000000000000003,
    0x0000000000000001
  };
  int hi = 64;
  int lo = 0;
  int i = 0;

  if (n == 0)
    return 0;

  for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
    int mi = lo + (hi - lo) / 2;

    if ((n >> mi) != 0)
      lo = mi;
    else if ((n & (mask[i] << lo)) != 0)
      hi = mi;
  }

  return lo + 1;
}

Programa de prueba rápido y sucio:

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

int highest_bit_unrolled(long long n);
int highest_bit(long long n);

main(int argc, char **argv)
{
  long long n = strtoull(argv[1], NULL, 0);
  int b1, b2;
  long i;
  clock_t start = clock(), mid, end;

  for (i = 0; i < 1000000000; i++)
    b1 = highest_bit_unrolled(n);

  mid = clock();

  for (i = 0; i < 1000000000; i++)
    b2 = highest_bit(n);

  end = clock();

  printf("highest bit of 0x%llx/%lld = %d, %d\n", n, n, b1, b2);

  printf("time1 = %d\n", (int) (mid - start));
  printf("time2 = %d\n", (int) (end - mid));
  return 0;
}

Usando solo -O2, la diferencia se vuelve mayor. El árbol de decisiones es casi cuatro veces más rápido.

También comparé el código ingenuo de cambio de bits:

int highest_bit_shift(long long n)
{
  int i = 0;
  for (; n; n >>= 1, i++)
    ; /* empty */
  return i;
}

Esto solo es rápido para números pequeños, como era de esperar. Al determinar que el bit más alto es 1 para n == 1, se comparó más de un 80% más rápido. Sin embargo, la mitad de los números elegidos al azar en el espacio de 63 bits tienen el bit 63 configurado.

En la entrada 0x3FFFFFFFFFFFFFFF, la versión del árbol de decisión es bastante más rápida que en 1, y muestra ser 1120% más rápida (12,2 veces) que el bit shifter.

También compararé el árbol de decisiones con las incorporaciones de GCC y también probaré una combinación de entradas en lugar de repetirlas con el mismo número. Puede haber alguna predicción de rama pegajosa y quizás algunos escenarios de almacenamiento en caché poco realistas que lo hacen artificialmente más rápido en las repeticiones.

Kaz
fuente
9
No estoy diciendo que esto no sea bueno, pero su programa de prueba aquí solo prueba en el mismo número, que después de 2-3 iteraciones habrá establecido los predictores de rama en su posición final y luego harán predicciones de rama perfectas. Lo bueno es que con una distribución totalmente aleatoria, la mitad de los números tendrán una predicción casi perfecta, es decir, bit63.
Surt el
8

Qué pasa

int highest_bit(unsigned int a) {
    int count;
    std::frexp(a, &count);
    return count - 1;
}

?

Marco Amagliani
fuente
Esta es una versión lenta (pero más portátil) de esta respuesta , lo que explica por qué funciona.
Peter Cordes
6
unsigned int
msb32(register unsigned int x)
{
        x |= (x >> 1);
        x |= (x >> 2);
        x |= (x >> 4);
        x |= (x >> 8);
        x |= (x >> 16);
        return(x & ~(x >> 1));
}

1 registro, 13 instrucciones. Lo crea o no, esto suele ser más rápido que la instrucción BSR mencionada anteriormente, que opera en tiempo lineal. Este es el tiempo logarítmico.

De http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit

rlbond
fuente
7
El código anterior no responde a la pregunta. Devuelve un entero sin signo donde el bit más significativo en x permanece encendido y todos los demás bits están apagados. La cuestión era devolver la posición de los más significativos en bit.
Protagonista
3
Luego puede usar un enfoque de secuencia de De Bruijn para encontrar el índice del bit que está establecido. :-)
R .. GitHub DEJA DE AYUDAR A ICE
5
@Protagonista, dijo en un comentario que tampoco basta.
rlbond
Este (de esa misma página) haría lo que necesita, pero requiere una función adicional. aggregate.org/MAGIC/#Log2%20of%20an%20Integer
Quinn Taylor
1
BSR es rápido en CPU Intel desde Core2 al menos. LZCNT es rápido en las CPU AMD, y gcc lo usa __builtin_clzsi está habilitado con -march=nativeo algo (ya que es rápido en todas las CPU que lo admiten). Incluso en CPU como la familia AMD Bulldozer donde BSR es "lento", no es tan lento: 7 m-ops con 4 ciclos de latencia y uno por 4c de rendimiento. En Atom, BSR es realmente lento: 16 ciclos. En Silvermont, son 10 uops con 10 ciclos de latencia. Esto podría ser una latencia ligeramente menor que BSR en Silvermont, pero IDK.
Peter Cordes
6

Aquí hay algunos puntos de referencia (simples) de algoritmos que se dan actualmente en esta página ...

Los algoritmos no se han probado en todas las entradas de unsigned int; así que verifica eso primero, antes de usar algo a ciegas;)

En mi máquina, clz (__builtin_clz) y asm funcionan mejor. asm parece incluso más rápido que clz ... pero podría deberse al simple punto de referencia ...

//////// go.c ///////////////////////////////
// compile with:  gcc go.c -o go -lm
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/***************** math ********************/

#define POS_OF_HIGHESTBITmath(a) /* 0th position is the Least-Signif-Bit */    \
  ((unsigned) log2(a))         /* thus: do not use if a <= 0 */  

#define NUM_OF_HIGHESTBITmath(a) ((a)               \
                  ? (1U << POS_OF_HIGHESTBITmath(a))    \
                  : 0)



/***************** clz ********************/

unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1);
#define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */

#define NUM_OF_HIGHESTBITclz(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITclz(a))  \
                 : 0)


/***************** i2f ********************/

double FF;
#define POS_OF_HIGHESTBITi2f(a) (FF = (double)(ui|1), ((*(1+(unsigned*)&FF))>>20)-1023)


#define NUM_OF_HIGHESTBITi2f(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITi2f(a))  \
                 : 0)




/***************** asm ********************/

unsigned OUT;
#define POS_OF_HIGHESTBITasm(a) (({asm("bsrl %1,%0" : "=r"(OUT) : "r"(a));}), OUT)

#define NUM_OF_HIGHESTBITasm(a) ((a)                    \
                 ? (1U << POS_OF_HIGHESTBITasm(a))  \
                 : 0)




/***************** bitshift1 ********************/

#define NUM_OF_HIGHESTBITbitshift1(a) (({   \
  OUT = a;                  \
  OUT |= (OUT >> 1);                \
  OUT |= (OUT >> 2);                \
  OUT |= (OUT >> 4);                \
  OUT |= (OUT >> 8);                \
  OUT |= (OUT >> 16);               \
      }), (OUT & ~(OUT >> 1)))          \



/***************** bitshift2 ********************/
int POS[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};

#define POS_OF_HIGHESTBITbitshift2(a) (({   \
  OUT = a;                  \
  OUT |= OUT >> 1;              \
  OUT |= OUT >> 2;              \
  OUT |= OUT >> 4;              \
  OUT |= OUT >> 8;              \
  OUT |= OUT >> 16;             \
  OUT = (OUT >> 1) + 1;             \
      }), POS[(OUT * 0x077CB531UL) >> 27])

#define NUM_OF_HIGHESTBITbitshift2(a) ((a)              \
                       ? (1U << POS_OF_HIGHESTBITbitshift2(a)) \
                       : 0)



#define LOOPS 100000000U

int main()
{
  time_t start, end;
  unsigned ui;
  unsigned n;

  /********* Checking the first few unsigned values (you'll need to check all if you want to use an algorithm here) **************/
  printf("math\n");
  for (ui = 0U; ui < 18; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITmath(ui));

  printf("\n\n");

  printf("clz\n");
  for (ui = 0U; ui < 18U; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITclz(ui));

  printf("\n\n");

  printf("i2f\n");
  for (ui = 0U; ui < 18U; ++ui)
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITi2f(ui));

  printf("\n\n");

  printf("asm\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITasm(ui));
  }

  printf("\n\n");

  printf("bitshift1\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift1(ui));
  }

  printf("\n\n");

  printf("bitshift2\n");
  for (ui = 0U; ui < 18U; ++ui) {
    printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift2(ui));
  }

  printf("\n\nPlease wait...\n\n");


  /************************* Simple clock() benchmark ******************/
  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITmath(ui);
  end = clock();
  printf("math:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITclz(ui);
  end = clock();
  printf("clz:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITi2f(ui);
  end = clock();
  printf("i2f:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITasm(ui);
  end = clock();
  printf("asm:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITbitshift1(ui);
  end = clock();
  printf("bitshift1:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  start = clock();
  for (ui = 0; ui < LOOPS; ++ui)
    n = NUM_OF_HIGHESTBITbitshift2(ui);
  end = clock();
  printf("bitshift2\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);

  printf("\nThe lower, the better. Take note that a negative exponent is good! ;)\n");

  return EXIT_SUCCESS;
}
Josh
fuente
6

Aunque probablemente solo usaría este método si necesitara absolutamente el mejor rendimiento posible (por ejemplo, para escribir algún tipo de IA de juego de mesa que involucre bitboards), la solución más eficiente es usar ASM en línea. Consulte la sección Optimizaciones de esta publicación de blog para obtener código con una explicación.

[...], la bsrlinstrucción de ensamblaje calcula la posición del bit más significativo. Por lo tanto, podríamos usar esta asmdeclaración:

asm ("bsrl %1, %0" 
     : "=r" (position) 
     : "r" (number));
Noldorin
fuente
Para expandir: la solución de bucle estándar (desplazarse a la izquierda y verificar MSB) es probablemente la más legible. Como en todos los casos que involucran la manipulación de bits, la velocidad de ASM no puede ser superada, aunque no tiene sentido saturar el código a menos que sea necesario. Los hacks son una solución intermedia: vaya de una forma u otra.
Noldorin
Yo diría que tomar el logaritmo sería una solución perfectamente legible (verifique el asm generado para ver si el compilador puede optimizarlo para usar esta instrucción asm)
jalf
A veces, la solución ASM en línea es más lenta, según la implementación en el microcódigo de la CPU.
rlbond
5
@rlbound: Apenas puedo creer eso, aunque puedo estar equivocado. En cualquier CPU moderna, uno pensaría que se traduciría a una sola instrucción ....
Noldorin
3
@Noldorin es un poco tarde, pero ... es por definición una sola instrucción, pero si está microcodificada como sugiere rlbond, entonces esa sola instrucción podría decodificar a un montón de µops internamente. Ese suele ser el caso de las microarquitecturas de AMD e Intel Atom, pero en las microarquitecturas normales de Intel es una sola operación hasta el final.
harold
4

Necesitaba una rutina para hacer esto y antes de buscar en la web (y encontrar esta página) se me ocurrió mi propia solución basada en una búsqueda binaria. ¡Aunque estoy seguro de que alguien ha hecho esto antes! Se ejecuta en tiempo constante y puede ser más rápido que la solución "obvia" publicada, aunque no estoy haciendo grandes afirmaciones, solo publico por interés.

int highest_bit(unsigned int a) {
  static const unsigned int maskv[] = { 0xffff, 0xff, 0xf, 0x3, 0x1 };
  const unsigned int *mask = maskv;
  int l, h;

  if (a == 0) return -1;

  l = 0;
  h = 32;

  do {
    int m = l + (h - l) / 2;

    if ((a >> m) != 0) l = m;
    else if ((a & (*mask << l)) != 0) h = m;

    mask++;
  } while (l < h - 1);

  return l;
}
peligro
fuente
4

eso es algún tipo de búsqueda binaria, funciona con todo tipo de tipos enteros (¡sin firmar!)

#include <climits>
#define UINT (unsigned int)
#define UINT_BIT (CHAR_BIT*sizeof(UINT))

int msb(UINT x)
{
    if(0 == x)
        return -1;

    int c = 0;

    for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
    if(static_cast<UINT>(x >> i))
    {
        x >>= i;
        c |= i;
    }

    return c;
}

para completar:

#include <climits>
#define UINT unsigned int
#define UINT_BIT (CHAR_BIT*sizeof(UINT))

int lsb(UINT x)
{
    if(0 == x)
        return -1;

    int c = UINT_BIT-1;

    for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
    if(static_cast<UINT>(x << i))
    {
        x <<= i;
        c ^= i;
    }

    return c;
}

fuente
4
Considere no usar ALL_CAPS para typedefs ni nada excepto macros de preprocesador. Esta es una convención ampliamente aceptada.
underscore_d
4

Algunas respuestas demasiado complejas aquí. La técnica Debruin solo debe usarse cuando la entrada ya es una potencia de dos, de lo contrario, hay una mejor manera. Para una potencia de 2 entradas, Debruin es absolutamente más rápido, incluso más rápido que _BitScanReverseen cualquier procesador que haya probado. Sin embargo, en el caso general, _BitScanReverse(o como se llame al intrínseco en su compilador) es el más rápido (aunque en ciertas CPU se puede microcodificar).

Si la función intrínseca no es una opción, aquí hay una solución de software óptima para procesar entradas generales.

u8  inline log2 (u32 val)  {
    u8  k = 0;
    if (val > 0x0000FFFFu) { val >>= 16; k  = 16; }
    if (val > 0x000000FFu) { val >>= 8;  k |= 8;  }
    if (val > 0x0000000Fu) { val >>= 4;  k |= 4;  }
    if (val > 0x00000003u) { val >>= 2;  k |= 2;  }
    k |= (val & 2) >> 1;
    return k;
}

Tenga en cuenta que esta versión no requiere una búsqueda de Debruin al final, a diferencia de la mayoría de las otras respuestas. Calcula la posición en su lugar.

Sin embargo, las tablas pueden ser preferibles, si las llama repetidamente suficientes veces, el riesgo de una falla de caché se ve eclipsado por la aceleración de una tabla.

u8 kTableLog2[256] = {
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};

u8 log2_table(u32 val)  {
    u8  k = 0;
    if (val > 0x0000FFFFuL) { val >>= 16; k  = 16; }
    if (val > 0x000000FFuL) { val >>=  8; k |=  8; }
    k |= kTableLog2[val]; // precompute the Log2 of the low byte

    return k;
}

Esto debería producir el mayor rendimiento de cualquiera de las respuestas de software que se dan aquí, pero si solo lo llama ocasionalmente, prefiera una solución sin tablas como mi primer fragmento.

VoidStar
fuente
1
Algunas de las respuestas no tienen ramas, pero esto probablemente se compilará con ramas condicionales. ¿Solo comparó con el mismo valor repetidamente, o un patrón simple o algo así? La predicción errónea de las ramas es un asesino para el rendimiento. stackoverflow.com/questions/11227809/…
Peter Cordes
3

Como señalan las respuestas anteriores, hay varias formas de determinar el bit más significativo. Sin embargo, como también se señaló, es probable que los métodos sean exclusivos de los registros de 32 bits o de 64 bits. La página de bithacks de stanford.edu ofrece soluciones que funcionan tanto para la informática de 32 bits como de 64 bits. Con un poco de trabajo, se pueden combinar para proporcionar un enfoque de arquitectura cruzada sólido para obtener el MSB. La solución a la que llegué que compiló / funcionó en computadoras de 64 y 32 bits fue:

#if defined(__LP64__) || defined(_LP64)
# define BUILD_64   1
#endif

#include <stdio.h>
#include <stdint.h>  /* for uint32_t */

/* CHAR_BIT  (or include limits.h) */
#ifndef CHAR_BIT
#define CHAR_BIT  8
#endif  /* CHAR_BIT */

/* 
 * Find the log base 2 of an integer with the MSB N set in O(N)
 * operations. (on 64bit & 32bit architectures)
 */
int
getmsb (uint32_t word)
{
    int r = 0;
    if (word < 1)
        return 0;
#ifdef BUILD_64
    union { uint32_t u[2]; double d; } t;  // temp
    t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
    t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = word;
    t.d -= 4503599627370496.0;
    r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
#else
    while (word >>= 1)
    {
        r++;
    }
#endif  /* BUILD_64 */
    return r;
}
David C. Rankin
fuente
No fue int r; originalmente definido sobre la #ifdef BUILD_64bandera? En cuyo caso no necesitaría redefinirse dentro del condicional.
David C. Rankin
3

Una versión en C usando aproximaciones sucesivas:

unsigned int getMsb(unsigned int n)
{
  unsigned int msb  = sizeof(n) * 4;
  unsigned int step = msb;
  while (step > 1)
 {
    step /=2;
    if (n>>msb)
     msb += step;
   else
     msb -= step;
 }
  if (n>>msb)
    msb++;
  return (msb - 1);
}

Ventaja: el tiempo de ejecución es constante independientemente del número proporcionado, ya que el número de bucles es siempre el mismo. (4 bucles cuando se usa "unsigned int")


fuente
Si lo escribe con un operador ternario ( msb += (n>>msb) ? step : -step;), es probable que más compiladores creen un ensamblaje sin ramificaciones, evitando predicciones erróneas de ramificaciones en cada paso ( stackoverflow.com/questions/11227809/… ).
Peter Cordes
3

Sé que esta pregunta es muy antigua, pero después de haber implementado una función msb () , descubrí que la mayoría de las soluciones presentadas aquí y en otros sitios web no son necesariamente las más eficientes, al menos para mi definición personal de eficiencia (consulte también la Actualización a continuación ). Este es el por qué:

La mayoría de las soluciones (especialmente aquellas que emplean algún tipo de esquema de búsqueda binaria o el enfoque ingenuo que hace un escaneo lineal de derecha a izquierda) parecen descuidar el hecho de que para números binarios arbitrarios, no hay muchas que comiencen con una secuencia muy larga de ceros. De hecho, para cualquier ancho de bit, la mitad de todos los enteros comienzan con 1 y una cuarta parte comienza con 01 . ¿Ves a dónde voy? Mi argumento es que un escaneo lineal que comienza desde la posición de bit más significativa hasta la menos significativa (de izquierda a derecha) no es tan "lineal" como podría parecer a primera vista.

Se puede mostrar 1 , que para cualquier ancho de bit, el número promedio de bits que deben probarse es como máximo 2. Esto se traduce en una complejidad de tiempo amortizado de O (1) con respecto al número de bits (!) .

Por supuesto, el peor de los casos sigue siendo O (n) , peor que el O (log (n)) que se obtiene con los enfoques de búsqueda binaria, pero como hay tan pocos casos peores, son insignificantes para la mayoría de las aplicaciones ( Actualizar : no del todo: puede haber pocos, pero pueden ocurrir con una alta probabilidad; consulte la Actualización a continuación).

Aquí está el enfoque "ingenuo" que se me ocurrió, que al menos en mi máquina supera a la mayoría de los otros enfoques (los esquemas de búsqueda binaria para entradas de 32 bits siempre requieren log 2 (32) = 5 pasos, mientras que este algoritmo tonto requiere menos de 2 en promedio) - perdón por ser C ++ y no C puro:

template <typename T>
auto msb(T n) -> int
{
    static_assert(std::is_integral<T>::value && !std::is_signed<T>::value,
        "msb<T>(): T must be an unsigned integral type.");

    for (T i = std::numeric_limits<T>::digits - 1, mask = 1 << i; i >= 0; --i, mask >>= 1)
    {
        if ((n & mask) != 0)
            return i;
    }

    return 0;
}

Actualización : si bien lo que escribí aquí es perfectamente cierto paraenteros arbitrarios , donde cada combinación de bits es igualmente probable (mi prueba de velocidad simplemente midió cuánto tiempo tomó determinar el MSB para todos los enteros de 32 bits), enteros de la vida real, por que tal función será llamada, generalmente sigue un patrón diferente: en mi código, por ejemplo, esta función se usa para determinar si el tamaño de un objeto es una potencia de 2, o para encontrar la siguiente potencia de 2 mayor o igual que una tamaño del objeto . Supongo que la mayoría de las aplicaciones que utilizan MSB implican números que son mucho más pequeños que el número máximo que puede representar un entero (los tamaños de los objetos rara vez utilizan todos los bits en un tamaño_t). En este caso, mi solución funcionará peor que un enfoque de búsqueda binaria, por lo que probablemente debería preferirse este último, aunque mi solución será más rápida en todos los números enteros.
TL; DR: Los enteros de la vida real probablemente tendrán un sesgo hacia el peor de los casos de este algoritmo simple, lo que hará que su rendimiento sea peor al final, a pesar del hecho de que se amortiza O (1) para enteros verdaderamente arbitrarios.

1 El argumento es el siguiente (borrador): Sea n el número de bits (ancho de bits). Hay un total de 2 n enteros que se pueden representar con n bits. Existen 2 n - 1 enteros que comienzan con 1 (el primer 1 es fijo, los n - 1 bits restantes pueden ser cualquier cosa). Esos números enteros requieren solo una interacción del ciclo para determinar el MSB. Además, hay 2 n - 2 enteros que comienzan con 01 , que requieren 2 iteraciones, 2 n - 3 enteros que comienzan con 001 , que requieren 3 iteraciones, y así sucesivamente.

Si sumamos todas las iteraciones requeridas para todos los números enteros posibles y las dividimos por 2 n , el número total de números enteros, obtenemos el número promedio de iteraciones necesarias para determinar el MSB para enteros de n bits:

(1 * 2 norte - 1 + 2 * 2 norte - 2 + 3 * 2 norte - 3 + ... + norte) / 2 norte

Esta serie de iteraciones promedio es realmente convergente y tiene un límite de 2 para n hacia el infinito

Por lo tanto, el algoritmo ingenuo de izquierda a derecha tiene en realidad una complejidad de tiempo constante amortizada de O (1) para cualquier número de bits.

Finnegan
fuente
2
No creo que sea necesariamente una suposición justa que las entradas a las funciones msb tienden a distribuirse de manera uniforme. En la práctica, estas entradas tienden a ser registros de interrupciones o tableros de bits o alguna otra estructura de datos con valores distribuidos de manera desigual. Para un punto de referencia justo, creo que es más seguro asumir que las salidas (no las entradas) se distribuirán uniformemente.
johnwbyrd
3

nos ha dado log2. Esto elimina la necesidad de todas las log2implementaciones especiales de salsa que ve en esta página. Puede utilizar la log2implementación del estándar así:

const auto n = 13UL;
const auto Index = (unsigned long)log2(n);

printf("MSB is: %u\n", Index); // Prints 3 (zero offset)

Una nde las 0ULnecesidades que protegerse también, porque:

-∞ se devuelve y FE_DIVBYZERO se eleva

He escrito un ejemplo con ese cheque que establece arbitrariamente Index a ULONG_MAXaquí: https://ideone.com/u26vsi


los El corolario de la única respuesta de gcc de ephemient es:

const auto n = 13UL;
unsigned long Index;

_BitScanReverse(&Index, n);
printf("MSB is: %u\n", Index); // Prints 3 (zero offset)

La documentación para_BitScanReverse estados que Indexsea:

Cargado con la posición de bit del primer bit establecido (1) encontrado

En la práctica, he descubierto que si nes 0ULque Indexse establece en0UL , al igual que lo sería para una nde 1UL. Pero lo único garantizado en la documentación en el caso de un nde 0ULes que la devolución es:

0 si no se encontraron bits establecidos

Por lo tanto, de manera similar a la log2implementación preferible anterior, el retorno debe verificarse estableciendo Indexun valor marcado en este caso. He vuelto a escribir un ejemplo de uso ULONG_MAXde este valor de bandera aquí: http://rextester.com/GCU61409

Jonathan Mee
fuente
No, _BitScanReversedevuelve 0 solo si la entrada fue 0. Esto es como la BSRinstrucción de x86 , que establece ZF basándose solo en la entrada, no en la salida. Es interesante que MS diga que los documentos indexno se configuran cuando no 1se encuentra ningún bit; que también coincide con el comportamiento de x86 asm bsr. (AMD lo documenta como dejar el registro de destino sin modificar en src = 0, pero Intel solo dice salida indefinida a pesar de que sus CPU implementan el comportamiento de dejar sin modificar). Esto es diferente a x86 lzcnt, que da 32por no encontrado.
Peter Cordes
@PeterCordes _BitScanReverseusa indexación basada en cero, por lo tanto, si nes 1, entonces el índice del bit establecido es de hecho 0. Desafortunadamente, como dice si nes 0, la salida también es 0 :( Esto significa que no hay forma de usar el retorno a distinguir entre n1 o 0. Eso es lo que estaba tratando de comunicar. ¿Crees que hay una mejor manera de decir esto?
Jonathan Mee
Creo que estás hablando de cómo se pone Index. Ese no es el valor de retorno . Devuelve un valor booleano que es falso si la entrada fue cero (y esta es la razón por la que el índice se pasa por referencia en lugar de devolverse normalmente). godbolt.org/g/gQKJdE . Y lo verifiqué: a pesar de la redacción de los documentos de MS, _BitScanReverseno deja Index sin configurar n==0: solo obtiene el valor que estaba en el registro que usó. (Que en su caso fue probablemente el mismo registro que usó Indexdespués, lo que le llevó a ver a 0).
Peter Cordes
Esta pregunta no está etiquetada como c ++.
tecnosaurus
@technosaurus Gracias, me olvidé de mí mismo. Dado que la pregunta es C, hemos tenidolog2 desde C99.
Jonathan Mee
2

Piense en operadores bit a bit.

Entendí mal la pregunta la primera vez. Debería producir un int con el bit más a la izquierda establecido (los otros cero). Suponiendo que cmp se establezca en ese valor:

position = sizeof(int)*8
while(!(n & cmp)){ 
   n <<=1;
   position--;
}
Vasil
fuente
¿Qué quieres decir con convertir a una cadena? La definición de ffs toma un int y devuelve un int. ¿Dónde estaría la conversión? ¿Y para qué serviría la conversión si buscamos bits en una palabra?
dreamlax
No conocía esa función.
Vasil
El 8debería ser CHAR_BIT. Es muy poco probable que esta sea la forma más rápida, porque la predicción errónea de la rama ocurrirá al salir del bucle, a menos que se use con la misma entrada repetidamente. Además, para entradas pequeñas (muchos ceros), tiene que repetirse mucho. Esta es como la forma alternativa que usaría como versión fácil de verificar en una prueba unitaria para comparar con versiones optimizadas.
Peter Cordes
2

Ampliando el punto de referencia de Josh ... se puede mejorar el clz de la siguiente manera

/***************** clz2 ********************/

#define NUM_OF_HIGHESTBITclz2(a) ((a)                              \
                  ? (((1U) << (sizeof(unsigned)*8-1)) >> __builtin_clz(a)) \
                  : 0)

Con respecto al asm: tenga en cuenta que existen bsr y bsrl (esta es la versión "larga"). el normal podría ser un poco más rápido.

JonesD
fuente
1

Tenga en cuenta que lo que está intentando hacer es calcular el entero log2 de un entero,

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

unsigned int
Log2(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1; int k=0;
    for( step = 1; step < bits; ) {
        n |= (n >> step);
        step *= 2; ++k;
    }
    //printf("%ld %ld\n",x, (x - (n >> 1)) );
    return(x - (n >> 1));
}

Observe que puede intentar buscar más de 1 bit a la vez.

unsigned int
Log2_a(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1;
    int step2 = 0;
    //observe that you can move 8 bits at a time, and there is a pattern...
    //if( x>1<<step2+8 ) { step2+=8;
        //if( x>1<<step2+8 ) { step2+=8;
            //if( x>1<<step2+8 ) { step2+=8;
            //}
        //}
    //}
    for( step2=0; x>1L<<step2+8; ) {
        step2+=8;
    }
    //printf("step2 %d\n",step2);
    for( step = 0; x>1L<<(step+step2); ) {
        step+=1;
        //printf("step %d\n",step+step2);
    }
    printf("log2(%ld) %d\n",x,step+step2);
    return(step+step2);
}

Este enfoque utiliza una búsqueda binaria

unsigned int
Log2_b(unsigned long x)
{
    unsigned long n = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int hbit = bits-1;
    unsigned int lbit = 0;
    unsigned long guess = bits/2;
    int found = 0;

    while ( hbit-lbit>1 ) {
        //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        //when value between guess..lbit
        if( (x<=(1L<<guess)) ) {
           //printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
            hbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
        //when value between hbit..guess
        //else
        if( (x>(1L<<guess)) ) {
            //printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
            lbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
    }
    if( (x>(1L<<guess)) ) ++guess;
    printf("log2(x%ld)=r%d\n",x,guess);
    return(guess);
}

Otro método de búsqueda binaria, quizás más legible,

unsigned int
Log2_c(unsigned long x)
{
    unsigned long v = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int step = bits;
    unsigned int res = 0;
    for( step = bits/2; step>0; )
    {
        //printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
        while ( v>>step ) {
            v>>=step;
            res+=step;
            //printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
        }
        step /= 2;
    }
    if( (x>(1L<<res)) ) ++res;
    printf("log2(x%ld)=r%ld\n",x,res);
    return(res);
}

Y como querrás probarlos,

int main()
{
    unsigned long int x = 3;
    for( x=2; x<1000000000; x*=2 ) {
        //printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
        printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
        printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
        printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
    }
    return(0);
}
ChuckCottrill
fuente
1

Poner esto en 'otro' enfoque, parece ser diferente de otros que ya se han dado.

devuelve -1si x==0, de lo contrariofloor( log2(x)) (resultado máximo 31)

Reduzca el problema de 32 a 4 bits, luego use una tabla. Quizás poco elegante, pero pragmático.

Esto es lo que uso cuando no quiero usar __builtin_clz debido a problemas de portabilidad.

Para hacerlo más compacto, se podría usar un bucle para reducir, agregando 4 ar cada vez, máximo 7 iteraciones. O algún híbrido, como (para 64 bits): bucle para reducir a 8, prueba para reducir a 4.

int log2floor( unsigned x ){
   static const signed char wtab[16] = {-1,0,1,1, 2,2,2,2, 3,3,3,3,3,3,3,3};
   int r = 0;
   unsigned xk = x >> 16;
   if( xk != 0 ){
       r = 16;
       x = xk;
   }
   // x is 0 .. 0xFFFF
   xk = x >> 8;
   if( xk != 0){
       r += 8;
       x = xk;
   }
   // x is 0 .. 0xFF
   xk = x >> 4;
   if( xk != 0){
       r += 4;
       x = xk;
   }
   // now x is 0..15; x=0 only if originally zero.
   return r + wtab[x];
}
Greggo
fuente
1

Guau, eso fueron muchas respuestas. No lamento haber respondido una vieja pregunta.

int result = 0;//could be a char or int8_t instead
if(value){//this assumes the value is 64bit
    if(0xFFFFFFFF00000000&value){  value>>=(1<<5); result|=(1<<5);  }//if it is 32bit then remove this line
    if(0x00000000FFFF0000&value){  value>>=(1<<4); result|=(1<<4);  }//and remove the 32msb
    if(0x000000000000FF00&value){  value>>=(1<<3); result|=(1<<3);  }
    if(0x00000000000000F0&value){  value>>=(1<<2); result|=(1<<2);  }
    if(0x000000000000000C&value){  value>>=(1<<1); result|=(1<<1);  }
    if(0x0000000000000002&value){  result|=(1<<0);  }
}else{
  result=-1;
}

Esta respuesta es bastante similar a otra respuesta ... bueno.

Harry Svensson
fuente
Escribir los importes de turno 1<<kes un buen toque. ¿Y las máscaras? (1 << (1<<k-1)-1<< (1<<k-1)? ( most optimal? ¿Comparas un superlativo?)
greybeard
@greybeard Si miras las ediciones de esta pregunta, verás cuando agregué la parte "óptima". Olvidé eliminarlo porque cambié mi respuesta. Además, no estoy seguro de por qué estás hablando de las máscaras. (¿Qué máscaras? No te estoy siguiendo)
Harry Svensson
(La máscara (de bits) son valores que se utilizan para seleccionar / borrar bits de forma selectiva / utilizados en &y &~.) Puede reemplazar las constantes hexadecimales por similares ((type)1<<(1<<k))-1<<(1<<k).
greybeard
Oh, claro, estoy usando máscaras, me olvidé por completo de eso. Respondí esto hace un par de meses ... - Hmmm, bueno, ya que se evalúa durante el tiempo de compilación, digo que es equivalente a los valores hexadecimales. Sin embargo, uno es críptico y el otro es hexadecimal.
Harry Svensson
0

El código:

    // x>=1;
    unsigned func(unsigned x) {
    double d = x ;
    int p= (*reinterpret_cast<long long*>(&d) >> 52) - 1023;
    printf( "The left-most non zero bit of %d is bit %d\n", x, p);
    }

O obtenga la parte entera de la instrucción FPU FYL2X (Y * Log2 X) configurando Y = 1

jemin
fuente
uhhhhh. ¿Qué? ¿cómo funciona esto? ¿Es portátil de alguna manera?
underscore_d
Los códigos en la ventana son portátiles. La función FYL2X () es una instrucción fpu, pero puede ser transferida y puede encontrarse en alguna biblioteca FPU / matemática.
jemin
@underscore_d Funciona porque los números de coma flotante están normalizados ... la conversión a doble desplaza los bits de mantisa para eliminar los ceros iniciales, y este código extrae el exponente y lo ajusta para determinar la cantidad de bits desplazados. Ciertamente no es independiente de la arquitectura, pero probablemente funcionará en cualquier máquina con la que te encuentres.
Jim Balter
Esta es una versión alternativa de esta respuesta , consulte los comentarios sobre el rendimiento y la portabilidad. (Específicamente la no portabilidad de la conversión de punteros para juegos de palabras de tipos). Utiliza matemáticas de direcciones para recargar solo los 32 bits altos de double, lo que probablemente sea bueno si realmente almacena / recarga en lugar de juegos de palabras de otra manera, por ejemplo, con una movqinstrucción como la que podría obtener aquí en x86.
Peter Cordes
También tenga en cuenta mi [comentario a esa respuesta], donde ofrezco la terrible advertencia de que este método da una respuesta incorrecta para los valores en (al menos) el rango [7FFFFFFFFFFFFE00 - 7FFFFFFFFFFFFFFF].
Glenn Slayden
0

Otro cartel proporcionó una tabla de búsqueda utilizando una búsqueda de ancho de bytes . En caso de que desee obtener un poco más de rendimiento (a costa de 32 K de memoria en lugar de solo 256 entradas de búsqueda), aquí hay una solución que usa una tabla de búsqueda de 15 bits , en C # 7 para .NET .

Lo interesante es inicializar la tabla. Dado que es un bloque relativamente pequeño que queremos durante la vida útil del proceso, asigno memoria no administrada para esto usando Marshal.AllocHGlobal. Como puede ver, para obtener el máximo rendimiento, todo el ejemplo está escrito como nativo:

readonly static byte[] msb_tab_15;

// Initialize a table of 32768 bytes with the bit position (counting from LSB=0)
// of the highest 'set' (non-zero) bit of its corresponding 16-bit index value.
// The table is compressed by half, so use (value >> 1) for indexing.
static MyStaticInit()
{
    var p = new byte[0x8000];

    for (byte n = 0; n < 16; n++)
        for (int c = (1 << n) >> 1, i = 0; i < c; i++)
            p[c + i] = n;

    msb_tab_15 = p;
}

La tabla requiere una inicialización única mediante el código anterior. Es de solo lectura, por lo que se puede compartir una única copia global para acceso simultáneo. Con esta tabla puede buscar rápidamente el registro de enteros 2 , que es lo que estamos buscando aquí, para todos los distintos anchos de enteros (8, 16, 32 y 64 bits).

Observe que la entrada de la tabla para 0, el único entero para el que la noción de 'bit de conjunto más alto' no está definida, recibe el valor-1 . Esta distinción es necesaria para el manejo adecuado de las palabras superiores con valor 0 en el código siguiente. Sin más preámbulos, aquí está el código para cada una de las diversas primitivas enteras:

Versión ulong (64 bits)

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(this ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 0x40) - 1;      // handles cases v==0 and MSB==63

    int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20;
    j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

Versión uint (32 bits)

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(uint v)
{
    if ((int)v <= 0)
        return (int)((v >> 26) & 0x20) - 1;     // handles cases v==0 and MSB==31

    int j = (int)((0x0000FFFFU - v) >> 27) & 0x10;
    return j + msb_tab_15[v >> (j + 1)];
}

Varias sobrecargas por lo anterior

public static int HighestOne(long v) => HighestOne((ulong)v);
public static int HighestOne(int v) => HighestOne((uint)v);
public static int HighestOne(ushort v) => msb_tab_15[v >> 1];
public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1];
public static int HighestOne(char ch) => msb_tab_15[ch >> 1];
public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1];
public static int HighestOne(byte v) => msb_tab_15[v >> 1];

Esta es una solución completa y funcional que representa el mejor rendimiento en .NET 4.7.2 para numerosas alternativas que comparé con un arnés de prueba de rendimiento especializado. Algunos de estos se mencionan a continuación. Los parámetros de prueba fueron una densidad uniforme de todas las posiciones de 65 bits, es decir, 0 ... 31/63 más valor 0(que produce el resultado -1). Los bits por debajo de la posición del índice de destino se completaron al azar. Las pruebas fueron solo x64 , modo de lanzamiento, con optimizaciones JIT habilitadas.




Ese es el final de mi respuesta formal aquí; lo que sigue son algunas notas informales y enlaces al código fuente para candidatos de prueba alternativos asociados con la prueba que ejecuté para validar el rendimiento y la corrección del código anterior.


La versión proporcionada anteriormente, codificada como Tab16A, fue un ganador constante en muchas carreras. Estos diversos candidatos, en forma de trabajo activo / cero, se pueden encontrar aquí , aquí y aquí .

 1 candidatos.HighestOne_Tab16A 622,496
 2 candidatos.HighestOne_Tab16C 628,234
 3 candidatos.HighestOne_Tab8A 649,146
 4 candidatos.HighestOne_Tab8B 656,847
 5 candidatos.HighestOne_Tab16B 657,147
 6 candidatos.HighestOne_Tab16D 659,650
 7 _más_alto_un_bit_UNMANAGED.HighestOne_U 702,900
 8 de_Bruijn.IndexOfMSB 709,672
 9 _old_2.HighestOne_Old2 715,810
10 _prueba_A.HighestOne8 757,188
11 _old_1.HighestOne_Old1 757,925
12 _test_A.HighestOne5 (inseguro) 760,387
13 _test_B.HighestOne8 (inseguro) 763,904
14 _test_A.HighestOne3 (inseguro) 766,433
15 _test_A.HighestOne1 (inseguro) 767,321
16 _test_A.HighestOne4 (inseguro) 771,702
17 _test_B.HighestOne2 (inseguro) 772,136
18 _test_B.HighestOne1 (inseguro) 772,527
19 _test_B.HighestOne3 (inseguro) 774,140
20 _test_A.HighestOne7 (inseguro) 774,581
21 _test_B.HighestOne7 (inseguro) 775,463
22 _test_A.HighestOne2 (inseguro) 776,865
23 candidatos.HighestOne_NoTab 777,698
24 _test_B.HighestOne6 (inseguro) 779,481
25 _test_A.HighestOne6 (inseguro) 781,553
26 _test_B.HighestOne4 (inseguro) 785,504
27 _test_B.HighestOne5 (inseguro) 789,797
28 _test_A.HighestOne0 (inseguro) 809,566
29 _test_B.HighestOne0 (inseguro) 814,990
30 _más_alto_un_bit.Más altoOne 824,345
30 _bitarray_ext.RtlFindMostSignificantBit 894,069
31 candidatos. El más alto_Naive 898,865

Es de destacar que el terrible rendimiento de ntdll.dll!RtlFindMostSignificantBitvia P / Invoke:

[DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical]
public static extern int RtlFindMostSignificantBit(ulong ul);

Es realmente una lástima, porque aquí está toda la función real:

    RtlFindMostSignificantBit:
        bsr rdx, rcx  
        mov eax,0FFFFFFFFh  
        movzx ecx, dl  
        cmovne      eax,ecx  
        ret

No puedo imaginar el bajo rendimiento que se origina con estas cinco líneas, por lo que las penalizaciones de transición administrada / nativa deben ser las culpables. También me sorprendió que las pruebas realmente favorecieran las shorttablas de búsqueda directa de 32 KB (y 64 KB) (16 bits) sobre las tablas de búsqueda de 128 bytes (y 256 bytes) byte(8 bits). Pensé que lo siguiente sería más competitivo con las búsquedas de 16 bits, pero esta última superó consistentemente esto:

public static int HighestOne_Tab8A(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    int j;
    j =  /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
    j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
    j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
    return j + msb_tab_8[v >> j];
}

Lo último que señalaré es que me sorprendió bastante que a mi método deBruijn no le fuera mejor. Este es el método que antes había estado usando de forma generalizada:

const ulong N_bsf64 = 0x07EDD5E59A4E28C2,
            N_bsr64 = 0x03F79D71B4CB0A89;

readonly public static sbyte[]
bsf64 =
{
    63,  0, 58,  1, 59, 47, 53,  2, 60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12, 44, 24, 15,  8, 23,  7,  6,  5,
},
bsr64 =
{
     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,
};

public static int IndexOfLSB(ulong v) =>
    v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;

public static int IndexOfMSB(ulong v)
{
    if ((long)v <= 0)
        return (int)((v >> 57) & 64) - 1;

    v |= v >> 1; v |= v >> 2;  v |= v >> 4;   // does anybody know a better
    v |= v >> 8; v |= v >> 16; v |= v >> 32;  // way than these 12 ops?
    return bsr64[(v * N_bsr64) >> 58];
}

Hay mucha discusión sobre cuán superiores y geniales son los métodos deBruijn en esta pregunta SO , y tendía a estar de acuerdo. Mi especulación es que, si bien los métodos de tabla de búsqueda directa y deBruijn (que encontré que son los más rápidos) tienen que realizar una búsqueda de tabla, y ambos tienen una ramificación mínima, solo deBruijn tiene una operación de multiplicación de 64 bits. Solo probé las IndexOfMSBfunciones aquí, no el deBruijn, IndexOfLSBpero espero que este último tenga muchas más posibilidades, ya que tiene muchas menos operaciones (ver arriba), y es probable que continúe usándolo para LSB.

Glenn Slayden
fuente
1
La caché L1D en las CPU x86 modernas es solo 32kiB. Es probable que una LUT grande sea peor que una LUT pequeña, a menos que utilice los mismos valores repetidamente. Si no es así, obtendrá frecuentes pérdidas de caché.
Peter Cordes
0

Mi humilde método es muy simple:

MSB (x) = INT [Log (x) / Log (2)]

Traducción: El MSB de x es el valor entero de (logaritmo de base x dividido por el logaritmo de base 2).

Esto se puede adaptar fácil y rápidamente a cualquier lenguaje de programación. Pruébelo en su calculadora para comprobar por sí mismo que funciona.

Guerra espartana
fuente
Eso funciona si lo único que le interesa es la eficiencia del desarrollador. Si desea eficiencia en tiempo de ejecución, necesita un algoritmo alternativo.
Mikko Rantalainen
Esto puede fallar debido a un error de redondeo. Por ejemplo, en CPython 2 y 3, int(math.log((1 << 48) - 1) / math.log(2))es 48.
benrg
0

Aquí hay una solución rápida para C que funciona en GCC y Clang ; listo para ser copiado y pegado.

#include <limits.h>

unsigned int fls(const unsigned int value)
{
    return (unsigned int)1 << ((sizeof(unsigned int) * CHAR_BIT) - __builtin_clz(value) - 1);
}

unsigned long flsl(const unsigned long value)
{
    return (unsigned long)1 << ((sizeof(unsigned long) * CHAR_BIT) - __builtin_clzl(value) - 1);
}

unsigned long long flsll(const unsigned long long value)
{
    return (unsigned long long)1 << ((sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(value) - 1);
}

Y una pequeña versión mejorada para C ++ .

#include <climits>

constexpr unsigned int fls(const unsigned int value)
{
    return (unsigned int)1 << ((sizeof(unsigned int) * CHAR_BIT) - __builtin_clz(value) - 1);
}

constexpr unsigned long fls(const unsigned long value)
{
    return (unsigned long)1 << ((sizeof(unsigned long) * CHAR_BIT) - __builtin_clzl(value) - 1);
}

constexpr unsigned long long fls(const unsigned long long value)
{
    return (unsigned long long)1 << ((sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(value) - 1);
}

El código asume que valueno será así 0. Si desea permitir 0, debe modificarlo.

SIN NOMBRE
fuente
0

Supongo que su pregunta es para un número entero (llamado v a continuación) y no un número entero sin signo.

int v = 612635685; // whatever value you wish

unsigned int get_msb(int v)
{
    int r = 31;                         // maximum number of iteration until integer has been totally left shifted out, considering that first bit is index 0. Also we could use (sizeof(int)) << 3 - 1 instead of 31 to make it work on any platform.

    while (!(v & 0x80000000) && r--) {   // mask of the highest bit
        v <<= 1;                        // multiply integer by 2.
    }
    return r;                           // will even return -1 if no bit was set, allowing error catch
}

Si desea que funcione sin tener en cuenta el signo, puede agregar un 'v << = 1;' adicional. antes del bucle (y cambie el valor r a 30 en consecuencia). Por favor avíseme si olvidé algo. No lo he probado pero debería funcionar bien.

Antonin GAVREL
fuente
v <<= 1es un comportamiento indefinido (UB) cuando v < 0.
chux - Reincorporar a Monica
0x8000000, tal vez te refieres a un 0 extra.
MM