Cómo obtener lg2 de un número que es 2^k

Question

Cuál es la mejor solución para obtener el logaritmo de base 2 de un número que sé que es una potencia de dos (2^k). (. Por supuesto que sé sólo el valor 2^k no k sí mismo)

Una forma se me ocurrió hacer es restando 1 y luego hacer un bitcount:

lg2(n) = bitcount(n - 1) = k, iff k is an integer 
0b10000 - 1 = 0b01111, bitcount(0b01111) = 4 

Pero hay una manera más rápida de hacerlo (sin almacenamiento en caché)? ¿También sería bueno saber algo que no involucra bitcount tan rápido?

Una de las aplicaciones esto es:

suppose you have bitmask 
0b0110111000 

and value 
0b0101010101 

and you are interested of 
(value & bitmask) >> number of zeros in front of bitmask 
(0b0101010101 & 0b0110111000) >> 3 = 0b100010 

this can be done with 

using bitcount 
value & bitmask >> bitcount((bitmask - 1) xor bitmask) - 1 

or using lg2 
value & bitmask >> lg2(((bitmask - 1) xor bitmask) + 1) - 2 

Para que sea más rápido que bitcount sin almacenamiento en caché que debería ser más rápido que O(lg(k)) donde k es el recuento de bits de almacenamiento.

Answer 1

Muchas arquitecturas tienen instrucciones de "encontrar primero" (bsr, clz, bfffo, cntlzw, etc.) que serán mucho más rápidas que los métodos de conteo de bits.

Answer 2

Si sabe que el número es una potencia de 2, puede simplemente desplazarlo a la derecha (>>) hasta que sea igual a 0. La cantidad de veces que se desplazó a la derecha (menos 1) es su k.

Editar: más rápido que esto es el método de la tabla de búsqueda (aunque sacrificas algo de espacio, pero no una tonelada). Ver http://doctorinterview.com/index.html/algorithmscoding/find-the-integer-log-base-2-of-an-integer/.

Answer 3

Si no te importa tratar con flotadores, puedes usar log(x)/log(2).

Answer 4

Sí. Aquí hay una manera de hacerlo sin la bitcount en lg(n), si se conoce el número entero en cuestión es una potencia de 2.

unsigned int x = ...; 
static const unsigned int arr[] = { 
    // Each element in this array alternates a number of 1s equal to 
    // consecutive powers of two with an equal number of 0s. 
    0xAAAAAAAA, // 0b10101010..   // one 1, then one 0, ... 
    0xCCCCCCCC, // 0b11001100..   // two 1s, then two 0s, ... 
    0xF0F0F0F0, // 0b11110000..   // four 1s, then four 0s, ... 
    0xFF00FF00, // 0b1111111100000000.. // [The sequence continues.] 
    0xFFFF0000 
} 

register unsigned int reg = (x & arr[0]) != 0; 
reg |= ((x & arr[4]) != 0) << 4; 
reg |= ((x & arr[3]) != 0) << 3; 
reg |= ((x & arr[2]) != 0) << 2; 
reg |= ((x & arr[1]) != 0) << 1; 

// reg now has the value of lg(x). 

En cada uno de los reg |= pasos, sucesivamente prueba para ver si cualquiera de los bits de x se comparten con las máscaras de bits alternas en arr. Si lo son, eso significa que lg(x) tiene bits que están en esa máscara de bits, y efectivamente agregamos 2^k a reg, donde k es el registro de la longitud de la máscara de bits alterna. Por ejemplo, 0xFF00FF00 es una secuencia alterna de 8 unidades y ceros, por lo que k es 3 (o lg(8)) para esta máscara de bits.

Esencialmente, cada paso reg |= ((x & arr[k]) ... (y la asignación inicial) comprueba si lg(x) tiene el bit k establecido. Si es así, lo agregamos a reg; la suma de todos esos bits será lg(x).

Eso parece mucha magia, así que vamos a probar un ejemplo. Supongamos que queremos saber qué potencia de 2 es el valor 2048:

// x = 2048 
// = 1000 0000 0000 

register unsigned int reg = (x & arr[0]) != 0; 
// reg =  1000 0000 0000 
     & ... 1010 1010 1010 
     =  1000 0000 0000 != 0 
// reg = 0x1 (1)  // <-- Matched! Add 2^0 to reg. 

reg |= ((x & arr[4]) != 0) << 4; 
// reg =  0x .. 0800 
      & 0x .. 0000 
     =    0 != 0 
// reg = reg | (0 << 4) // <--- No match. 
// reg = 0x1 | 0 
// reg remains 0x1. 

reg |= ((x & arr[3]) != 0) << 3; 
// reg =  0x .. 0800 
      & 0x .. FF00 
     =   800 != 0 
// reg = reg | (1 << 3) // <--- Matched! Add 2^3 to reg. 
// reg = 0x1 | 0x8 
// reg is now 0x9.   

reg |= ((x & arr[2]) != 0) << 2; 
// reg =  0x .. 0800 
      & 0x .. F0F0 
     =    0 != 0 
// reg = reg | (0 << 2) // <--- No match. 
// reg = 0x9 | 0 
// reg remains 0x9.   

reg |= ((x & arr[1]) != 0) << 1; 
// reg =  0x .. 0800 
      & 0x .. CCCC 
     =   800 != 0 
// reg = reg | (1 << 1) // <--- Matched! Add 2^1 to reg. 
// reg = 0x9 | 0x2 
// reg is now 0xb (11). 

Vemos que el valor final de reg es 2^0 + 2 + 1^2^3, que es de hecho 11.