¿Cuál es la forma más rápida de calcular el número de bits necesarios para almacenar un número

Question

Estoy tratando de optimizar algunas rutinas de empaque y desempaquetado de bits. Para hacer el embalaje, necesito calcular la cantidad de bits necesarios para almacenar valores enteros. Aquí está el código actual.

if (n == -1) return 32; 
if (n == 0) return 1; 
int r = 0; 
while (n) 
{ 
    ++r; 
    n >>= 1; 
} 
return r; 

Answer 1

Está buscando determinar la base de registro entero 2 de un número (el l = conjunto de bits más alto). La página "Hack Twiddling Hacks" de Sean Anderson tiene varios métodos que van desde los bits obvios de recuento en un ciclo hasta las versiones que usan la búsqueda de tablas. Tenga en cuenta que la mayoría de los métodos demostrados deberán modificarse un poco para que funcionen con entradas de 64 bits si ese tipo de portabilidad es importante para usted.

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

Sólo asegúrese de que cualquier cambio que está utilizando para calcular el conjunto de bits más alta que hay que hacer' en una versión unsigned de la serie ya que una aplicación compilador podría o no signo extender la operación >> en un valor firmado.

Answer 2

No transportables, utilice el código de operación bit-scan-reverse disponible en la mayoría de las arquitecturas modernas. Está expuesto como intrinsic en Visual C++.

Portably, el código en la pregunta no necesita el manejo de la caja de borde. ¿Por qué necesita un bit para almacenar 0? En cualquier caso, voy a ignorar los bordes del problema. Las tripas se puede hacer de manera eficiente por lo tanto:

if (n >> 16) { r += 16; n >>= 16; } 
if (n >> 8) { r += 8; n >>= 8; } 
if (n >> 4) { r += 4; n >>= 4; } 
if (n >> 2) { r += 2; n >>= 2; } 
if (n - 1) ++r; 

Answer 3

Usted tiene que comprobar el tiempo de ejecución para determinar el nivel de detalle, pero mi conjetura es que hacer 4 bits a la vez, y luego volver a un bit a la vez que hazlo mas rapido. Las operaciones de registro probablemente serían más lentas que las operaciones lógicas/de bits.

if (n < 0) return 32; 
int r = 0; 
while (n && 0x7FFFFFF0) { 
    r+=4; 
    n >>= 4; } 
while (n) { 
    r++; 
    n >>= 1; } 
return r; 

Answer 4

Lo que estás intentando hacer es encontrar el fragmento más significativo. Algunas arquitecturas tienen una instrucción especial solo para este propósito. Para aquellos que no lo hacen, use un método de búsqueda de tablas.

Crea una tabla de 256 entradas, donde cada elemento identifica el bit más alto.

O buclee a través de cada byte en el número, o utilice unas pocas declaraciones if para dividirlas para encontrar el byte no cero de mayor orden.

Te dejo el resto de aquí.

Answer 5

Realice una búsqueda binaria en lugar de una búsqueda lineal.

if ((n >> 16) != 0) 
{ 
    r += 16; 
    n >>= 16; 
} 

if ((n >> 8) != 0) 
{ 
    r += 8; 
    n >>= 8;   
} 

if ((n >> 4) != 0) 
{ 
    r += 4; 
    n >>= 4;   
} 

// etc. 

Si su hardware tiene bit-scan-reverse, un enfoque aún más rápido sería escribir su rutina en lenguaje ensamblador. Para mantener su código portable, se puede hacer

#ifdef ARCHITECTURE_WITH_BSR 
    asm // ... 
#else 
    // Use the approach shown above 
#endif 

Answer 6

number_of_bits = log2(integer_number) 

redondeado al número entero superior.