algorithm - examples - Redondea a la potencia más cercana de dos.

algorithms book

Question

¿Hay una expresión de una línea (posiblemente booleana) para obtener el número 2^n más cercano para un número entero dado?

Ejemplo: 5,6,7 debe ser 8.

Answer 1

Creo que te refieres al siguiente número 2 ^ n más cercano. Puede hacer un registro en el modo 2 y luego determinar el siguiente valor entero.

Para java, se puede hacer como:

Math.ceil(Math.log(x)/Math.log(2))

Answer 2

Dado que el título de la pregunta es "Redondear a la potencia más cercana de dos", pensé que sería útil incluir una solución a ese problema también.

int nearestPowerOfTwo(int n)
{
    int v = n; 

    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++; // next power of 2

    int x = v >> 1; // previous power of 2

    return (v - n) > (n - x) ? x : v;
}

Básicamente encuentra la potencia anterior y la siguiente de dos y luego devuelve la más cercana.

Answer 3

Esto se puede hacer desplazando a la derecha el número de entrada hasta que se convierta en 0 y manteniendo el recuento de turnos. Esto le dará la posición del bit 1 más significativo. Obtener 2 a la potencia de este número nos dará la siguiente potencia más cercana de 2.

public int NextPowerOf2(int number) {
    int pos = 0;

    while (number > 0) {
        pos++;
        number = number >> 1; 
    }
    return (int) Math.pow(2, pos);
}

Answer 4

Modificado para VBA. NextPowerOf2_1 no parece funcionar. Así que utilicé el método de bucle. Necesitaba un cambio de operador de bit a la derecha sin embargo.

Sub test()
    NextPowerOf2_1(31)
    NextPowerOf2_2(31)
    NextPowerOf2_1(32)
    NextPowerOf2_2(32)
End Sub

Sub NextPowerOf2_1(ByVal number As Long) '' Does not work
    Debug.Print 2 ^ (Int(Math.Log(number - 1) / Math.Log(2)) + 1)
End Sub

Sub NextPowerOf2_2(ByVal number As Long)
    Dim pos As Integer
    pos = 0
    While (number > 0)
        pos = pos + 1
        number = shr(number, 1)
    Wend

    Debug.Print 2 ^ pos
End Sub
Function shr(ByVal Value As Long, ByVal Shift As Byte) As Long
    Dim i As Byte
    shr = Value
    If Shift > 0 Then
        shr = Int(shr / (2 ^ Shift))
    End If
End Function

Answer 5

Para la siguiente potencia de dos a partir de un entero dado x

2^(int(log(x-1,2))+1)

o alternativamente (si no tiene una función de log que acepte un argumento base

2^(int(log(x-1)/log(2))+1)

Tenga en cuenta que esto no funciona para x <2

Answer 6

Redondea a la siguiente potencia más alta de dos: ver hacks de twiddling de bits .

Cía:

unsigned int v; // compute the next highest power of 2 of 32-bit v

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

Answer 7

Sus necesidades son un poco confusas, la potencia más cercana de 2 a 5 es 4. Si lo que desea es la siguiente potencia de 2 a partir del número, la siguiente expresión de Mathematica hace lo que desea:

2^Ceiling[Log[2, 5]] => 8

A partir de eso, debería ser sencillo descubrir una sola línea en la mayoría de los lenguajes de programación.