¿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?

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)?

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? )

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.

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.

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

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

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.

Qué pasa

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

?

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

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

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

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

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

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.

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

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")

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 ¹ , 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 ₂ (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.

¹ El argumento es el siguiente (borrador): Sea n el número de bits (ancho de bits). Hay un total de 2 ⁿ 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 ⁿ , 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.

c99nos 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 estudio visualEl 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

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

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.

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

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

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.

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

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