Potencia anterior de 2

Question

Hay mucha información sobre cómo encontrar la siguiente potencia de 2 de un valor dado (ver refs) pero no puedo encontrar ninguna para obtener la potencia anterior de dos.

La única forma que encuentro hasta ahora es mantener una tabla con toda la potencia de dos hasta 2^64 y hacer una búsqueda simple.

• Acius' Snippets
• gamedev
• Bit Twiddling Hacks
• Stack Overflow

Answer 1

Esta es mi solución actual para encontrar las potencias siguientes y anteriores de dos de cualquier entero positivo n dado y también una pequeña función para determinar si un número es potencia de dos.

Esta implementación es para Ruby.

class Integer 

    def power_of_two? 
    (self & (self - 1) == 0) 
    end 

    def next_power_of_two 
    return 1 if self <= 0 
    val = self 
    val = val - 1 
    val = (val >> 1) | val 
    val = (val >> 2) | val 
    val = (val >> 4) | val 
    val = (val >> 8) | val 
    val = (val >> 16) | val 
    val = (val >> 32) | val if self.class == Bignum 
    val = val + 1 
    end 

    def prev_power_of_two 
    return 1 if self <= 0 
    val = self 
    val = val - 1 
    val = (val >> 1) | val 
    val = (val >> 2) | val 
    val = (val >> 4) | val 
    val = (val >> 8) | val 
    val = (val >> 16) | val 
    val = (val >> 32) | val if self.class == Bignum 
    val = val - (val >> 1) 
    end 
end 

Ejemplo uso:

10.power_of_two? => false 
16.power_of_two? => true 
10.next_power_of_two => 16 
10.prev_power_of_two => 8 

Para la potencia anterior de dos, encontrar el siguiente y dividiendo por dos es ligeramente más lento que el método anterior.

No estoy seguro de cómo funciona con Bignums.

Answer 2

Probablemente el enfoque más simple (para los números positivos):

// find next (must be greater) power, and go one back 
p = 1; while (p <= n) p <<= 1; p >>= 1; 

Usted puede mak e variaciones de muchas maneras si desea optimizar.

Answer 3

De Hacker's Delight, una buena solución sin sucursales:

uint32_t flp2 (uint32_t x) 
{ 
    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 8); 
    x = x | (x >> 16); 
    return x - (x >> 1); 
} 

Esto suele tardar 12 instrucciones. Puedes hacerlo en menos si tu CPU tiene una instrucción de "contar ceros a la izquierda".

Answer 4

Cuando trabaja en la base 2, puede pasar de una potencia de dos a la siguiente simplemente agregando o eliminando un dígito de la derecha.

Por ejemplo, la potencia anterior de dos del número 8 es el número 4. En binaria:

01000 -> 0100 (quito el cero final para obtener el número 4)

Así que el algoritmo para resolver el cálculo de la potencia anterior de dos es:

previousPower: = SHR número 1

previousPower = número >> 1

(o cualquier otra sintaxis)

Answer 5

Si puede obtener la siguiente potencia más alta de 2, la siguiente potencia más baja de 2 es la siguiente más alta o la mitad de eso. Depende de lo que consideras que es el "siguiente más alto" para cualquier potencia de 2 (y lo que consideras que es la siguiente potencia más baja de 2).

Answer 6

Esto se puede hacer en una línea.

int nextLowerPowerOf2 = i <= 0 
         ? 0 
         : ((i & (~i + 1)) == i) 
          ? i >> 1 
          : (1 << (int)Math.Log(i, 2)); 

resultado

i power_of_2 
-2 0 
-1 0 
0 0 
1 0 
2 1 
3 2 
4 2 
5 4 
6 4 
7 4 
8 4 
9 8 

Aquí hay una versión más legible en C#, con la < = 0 cláusula guardia distribuido a los métodos de utilidad.

int nextLowerPowerOf2 = IsPowerOfTwo(i) 
    ? i >> 1 // shift it right 
    : GetPowerOfTwoLessThanOrEqualTo(i); 

public static int GetPowerOfTwoLessThanOrEqualTo(int x) 
{ 
    return (x <= 0 ? 0 : (1 << (int)Math.Log(x, 2))); 
} 

public static bool IsPowerOfTwo(int x) 
{ 
    return (((x & (~x + 1)) == x) && (x > 0)); 
} 

Answer 7

uint32_t previous_power_of_two(uint32_t x) { 
    if (x == 0) { 
     return 0; 
    } 
    // x--; Uncomment this, if you want a strictly less than 'x' result. 
    x |= (x >> 1); 
    x |= (x >> 2); 
    x |= (x >> 4); 
    x |= (x >> 8); 
    x |= (x >> 16); 
    return x - (x >> 1); 
} 

Gracias por las respuestas. Trataré de resumirlos y explicarlos un poco más. Lo que hace este algoritmo es cambiar a 'unos' todos los bits después del primer 'uno', porque estos son los únicos bits que pueden hacer que nuestra 'x' sea más grande que su potencia anterior de dos. Después de asegurarse de que son "únicos", simplemente los elimina, dejando intacto el primer bit "uno". Ese único bit en su lugar es nuestro poder anterior de dos.

Answer 8

Pruebe esto: ~((x + ~x)>>1) Es corto, y realmente fácil.

Answer 9

¿Qué hay de

if (tt = v >> 16) 
{ 
    r = (t = tt >> 8) ? 0x1000000 * Table256[t] : 0x10000 * Table256[tt]; 
} 
else 
{ 
    r = (t = v >> 8) ? 0x100 * Table256[t] : Table256[v]; 
} 

Se acaba método modificado de http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup. Esto requiere como 7 operaciones y podría ser más rápido reemplazar las multiplicaciones con cambio.

Answer 10

Aquí es un chiste para la posteridad (rubí):

2**Math.log(input, 2).floor(0) 

Answer 11

A continuación código se encuentra el poder anterior de 2:

int n = 100; 
    n /= 2;//commenting this will gives the next power of 2 
    n |= n>>1; 
    n |= n>>2; 
    n |= n>>4; 
    n |= n>>16; 

System.out.println(n+1);