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

Si tengo un número entero ny 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 izquierdo que es a 1), ¿cuál es? ¿Cuál es el método más rápido y eficaz para averiguarlo?

Sé que POSIX admite un ffs()método para <strings.h>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é pasa en los casos en los que no se pueden utilizar las funciones POSIX para la portabilidad?

EDITAR : ¿Qué tal una solución que funcione en arquitecturas de 32 y 64 bits (parece que muchas de las listas de códigos solo funcionarían en enteros de 32 bits)?

Mar 23 '09 06:03 Zxaos

Dado que 2^N es un número entero con solo el enésimo bit establecido (1 << N), encontrar la posición (N) del bit establecido más alto es el registro entero en 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 un bit hacia la derecha repetidamente hasta que el bit más a la izquierda se ha desplazado (tenga en cuenta que C trata cualquier valor distinto de cero como verdadero) y devuelve el número de turnos, tiene mucho sentido. También significa que funciona incluso cuando se establece más de un bit; el resultado siempre es 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 a la izquierda, el enfoque ingenuo puede proporcionar una velocidad aceptable, ya que el desplazamiento 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 al utilizar algoritmos muy inteligentes; muchos de ellos sólo funcionan correctamente para valores de 32 bits.

Feb 11 '2011 15:02 Quinn Taylor

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

Busca en el operando de origen el bit establecido más significativo (1 bit). Si se encuentra el bit más significativo, su índice de bits se almacena en el operando de destino. El operando fuente 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 de origen. 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.

Mar 23 '2009 00:03 timday

Esto es algo así como encontrar una especie de registro de números enteros. Hay trucos complicados, pero he creado mi propia herramienta para esto. El objetivo, por supuesto, es la velocidad.

¡Me he dado cuenta de que la CPU ya tiene un detector de bits automático, que se utiliza para la conversión de números enteros a flotantes! Entonces usa eso.

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

Esta versión convierte el valor en doble y luego lee el exponente, que indica dónde estaba el bit. Lo elegante de cambiar y restar es extraer las partes adecuadas del valor IEEE.

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

Para hacer esto de forma segura, sin un comportamiento indefinido en C++ o C, use memcpyen lugar de la conversión de puntero para juegos de palabras. Los compiladores saben cómo incorporarlo 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, utilice un archivo union {double d; uint32_t u[2];};. Pero tenga en cuenta que en C++, los juegos de palabras de tipo unión solo se admiten en algunos compiladores como una extensión, no en ISO C++.

Por lo general, esto será más lento que una instrucción intrínseca específica de la plataforma para una instrucción de conteo de ceros a la izquierda, pero el ISO C portátil no tiene esa función. Algunas CPU también carecen de una instrucción de conteo de ceros a la izquierda, pero algunas de ellas pueden convertir de manera eficiente 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 un almacenamiento/recarga y generalmente provoca una parada de carga y almacenamiento).

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

Mar 22 '2009 23:03 SPWorley