Redondeando a la siguiente potencia de 2

189

Quiero escribir una función que devuelva la siguiente potencia más cercana de 2 números. Por ejemplo, si mi entrada es 789, la salida debería ser 1024. ¿Hay alguna forma de lograr esto sin usar ningún bucle sino solo usando algunos operadores bit a bit?

Naveen
fuente
44
Vea aquí para posibles soluciones: http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float
Stefan
44
A modo de aclaración, ¿necesita la potencia más cercana de 2 (es decir, 65 le daría 64, pero 100 le daría 128) o la más cercana anterior (es decir, 65 le daría 128, y también 100)?
Kim Reece
1
Son múltiples preguntas que coinciden con esta. Por ejemplo: stackoverflow.com/questions/364985/…
Yann Droneaud
77
@Nathan Su enlace es 8 meses después de esta pregunta.
Joseph Quinsey

Respuestas:

148

Revisa los Bit Twiddling Hacks . Necesitas obtener el logaritmo de base 2, luego agrega 1 a eso. Ejemplo para un valor de 32 bits:

Redondea a la siguiente potencia más alta de 2

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++;

La extensión a otros anchos debería ser obvia.

florín
fuente
11
Esta no es la solución más eficiente porque muchos procesadores tienen instrucciones especiales para contar los ceros iniciales que se pueden usar para calcular log2 de manera muy eficiente. Ver en.wikipedia.org/wiki/Find_first_set
Simon
77
@ Simon: es la solución portátil. No hay un algoritmo eficiente común para todas las arquitecturas
phuclv
55
¿Qué pasa si el número en sí es una potencia de dos?
Litherum
55
Este hilo todavía está bien referenciado, pero esta respuesta (y la mayoría de las otras) están muy desactualizadas. Las CPU tienen una instrucción para ayudar a esto (¿realmente ya en ese momento?). De: jameshfisher.com/2018/03/30/round-up-power-2.html uint64_t next_pow2(uint64_t x) { return x == 1 ? 1 : 1<<(64-__builtin_clzl(x-1)); } Y por 32 bits: uint32_t next_pow2(uint32_t x) { return x == 1 ? 1 : 1<<(32-__builtin_clz(x-1)); }Eso es si usa GCC (y Clang, creo), pero sería prudente tomarse el tiempo para encuentre la llamada a CLZ en lugar de copiar y pegar todas las opciones.
MappaM
2
@MappaM Esta respuesta sigue siendo muy relevante y la mejor forma portátil de hacerlo. Su versión de 64 bits tiene un comportamiento indefinido si x > UINT32_MAXno tiene ramificaciones. Además, GCC y Clang usan -mtune=genericde forma predeterminada (como lo hacen la mayoría de las distribuciones), por lo que su código NO se expandirá a las lzcntinstrucciones en x86_64; en realidad se expandirá a algo MUCHO más lento (una rutina libgcc) a menos que use algo como -march=native. Por lo tanto, su reemplazo propuesto no es portátil, tiene errores y (típicamente) es más lento.
Craig Barnes
76
next = pow(2, ceil(log(x)/log(2)));

Esto funciona al encontrar el número por el que aumentaría 2 para obtener x (tome el registro del número y divida por el registro de la base deseada, consulte wikipedia para obtener más información ). Luego redondee eso con ceil para obtener la potencia numérica más cercana.

Este es un método de propósito más general (es decir, ¡más lento!) Que los métodos bit a bit vinculados a otros lugares, pero es bueno saber las matemáticas, ¿eh?

Paul Dixon
fuente
3
Desde C99, también puede usar log2 si sus herramientas lo admiten. GCC y VS no parecen :(
Matthew leyó el
2
Te falta un paréntesis ... siguiente = pow (2, ceil (log (x) / log (2)));
Matthieu Cormier
13
Sin embargo, tenga cuidado con la precisión del flotador. log(pow(2,29))/log(2)= 29.000000000000004, por lo que el resultado es 2 30 en lugar de devolver 2 29. Creo que es por eso que existen las funciones log2?
endolito el
48
El costo de esto es probablemente de al menos 200 ciclos y ni siquiera es correcto. ¿Por qué esto tiene tantos votos a favor?
Axel Gneiting
44
@SuperflyJon Pero menciona operadores bit a bit y supongo que cualquier pregunta implica la corrección, a menos que se indique lo contrario.
BlackJack
50
unsigned long upper_power_of_two(unsigned long v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;

}
Eclipse
fuente
62
Sería bueno si lo hubieras atribuido (a menos que lo hayas descubierto). Proviene de la página de trucos poco retorcidos.
florin
3
¿Eso es para un número de 32 bits? Extensión para 64 bits?
Jonathan Leffler
Jonathan, debes hacerlo para la mitad superior, y si eso es cero, lo haces para la mitad inferior.
florin
55
@florin, si v es un tipo de 64 bits, ¿no podría simplemente agregar un "c | = v >> 32" después del de 16?
Evan Teran
3
El código que solo funciona para un ancho de bits específico debe usar tipos de ancho fijo en lugar de tipos de ancho mínimo. Esta función debe tomar y devolver a uint32_t.
Craig Barnes
50

Creo que esto también funciona:

int power = 1;
while(power < x)
    power*=2;

Y la respuesta es power.

Jose Dagoberto
fuente
19
Es justo que la pregunta no pidiera bucles. Pero a pesar de lo inteligentes que son algunas de las otras funciones, para un código que no es sensible al rendimiento, la respuesta que se entiende y verifica que es correcta de manera rápida y fácil siempre me resulta útil.
Tim MB
2
Esto no está devolviendo la potencia más cercana de 2, pero la potencia de eso es inmediatamente mayor que X. Todavía es muy bueno
CoffeDeveloper
1
En lugar de multiplicar, se puede usar algo de "magia" bit a bit en su lugarpower <<= 1
vallentin
55
@Vallentin Eso debería ser optimizado automáticamente por un compilador.
MarkWeston
44
Tenga cuidado con el bucle infinito si xes demasiado grande (es decir, no hay suficientes bits para representar la próxima potencia de 2).
Alban
36

Si está utilizando GCC, es posible que desee echar un vistazo a Optimización de la función next_pow2 () por lockless Inc .. Esta página describe una manera de utilizar función integrada builtin_clz()(cómputo cero inicial) y luego utilizar directamente x86 (IA32) instrucción del ensamblador bsr(exploración de bits inversa), tal como se describe en el enlace de otra respuesta al sitio gamedev . Este código puede ser más rápido que los descritos en la respuesta anterior .

Por cierto, si no vas a usar instrucciones de ensamblador y tipo de datos de 64 bits, puedes usar esto

/**
 * return the smallest power of two value
 * greater than x
 *
 * Input range:  [2..2147483648]
 * Output range: [2..2147483648]
 *
 */
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
    assert(x > 1);
    assert(x <= ((UINT32_MAX/2) + 1));
#endif

    return 1 << (32 - __builtin_clz (x - 1));
}
Yann Droneaud
fuente
3
Tenga en cuenta que esto devuelve la potencia más pequeña de 2 mayor que OR igual a x. Cambiar (x -1) a x cambia la función para devolver la potencia menor de 2 mayor que x.
Guillaume
2
Puede usar _BitScanForwarden Visual C ++
KindDragon
También puede usar__builtin_ctz()
MarkP
@MarkP __builtin_ctz()no será útil para redondear cualquier número que no sea potencia de 2 hasta la próxima potencia de dos
Yann Droneaud el
2
Agregue en su respuesta un enlace a la lista de Wikipedia de funciones bit a bit integradas para otros compiladores: en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support                                Proporcione también una versión de 64 bits. Propongo la siguiente función C ++ 11:              constexpr uint64_t nextPowerOfTwo64 (uint64_t x) { return 1ULL<<(sizeof(uint64_t) * 8 - __builtin_clzll(x)); }
olibre
15

Uno más, aunque uso el ciclo, pero esto es mucho más rápido que los operandos matemáticos

potencia de dos opciones de "piso":

int power = 1;
while (x >>= 1) power <<= 1;

potencia de dos opciones "ceil":

int power = 2;
x--;    // <<-- UPDATED
while (x >>= 1) power <<= 1;

ACTUALIZAR

Como se mencionó en los comentarios, hubo un error en el ceilresultado incorrecto.

Aquí hay funciones completas:

unsigned power_floor(unsigned x) {
    int power = 1;
    while (x >>= 1) power <<= 1;
    return power;
}

unsigned power_ceil(unsigned x) {
    if (x <= 1) return 1;
    int power = 2;
    x--;
    while (x >>= 1) power <<= 1;
    return power;
}
vlk
fuente
2
el resultado no es correcto si la xpotencia es de 2. Se necesita un micro para probar si la entrada es potencia de 2. #define ISPOW2(x) ((x) > 0 && !((x) & (x-1)))
pgplus1628
@zorksylar sería más eficienteif (x == 0) return 1; /* Or 0 (Which is what I use) */ x--; /* Rest of program */
yyny
¡Buena solución! Pero el power of two "ceil" optionno es correcto. Por ejemplo, cuando x = 2el resultado debería ser en 2lugar de4
MZD
10

Para cualquier tipo sin firmar, basándose en Bit Twiddling Hacks:

#include <climits>
#include <type_traits>

template <typename UnsignedType>
UnsignedType round_up_to_power_of_2(UnsignedType v) {
  static_assert(std::is_unsigned<UnsignedType>::value, "Only works for unsigned types");
  v--;
  for (size_t i = 1; i < sizeof(v) * CHAR_BIT; i *= 2) //Prefer size_t "Warning comparison between signed and unsigned integer"
  {
    v |= v >> i;
  }
  return ++v;
}

Realmente no hay un bucle allí, ya que el compilador sabe en tiempo de compilación el número de iteraciones.

Robson
fuente
44
Tenga en cuenta que la pregunta es sobre C.
martinkunev
@martinkunev Simplemente reemplace UnsignedType y trátelo manualmente. Estoy bastante seguro de que un programador en C puede expandir esta plantilla simple ignorando la std::is_unsigned<UnsignedType>::valueafirmación.
user877329
2
@ user877329 Claro, sería bueno tener una respuesta en Javascript, así, por si acaso alguien quiere traducir eso a C
martinkunev
@martinkunev UnsignedType en JavaScript? De todos modos, esta solución muestra cómo hacerlo para cualquier UnsignedType, y está escrito en C ++, en lugar de pseudocódigo [sizeof (v) * CHAR_BIT en lugar de algo así como el número de bits en un objeto de UnsignedType].
user877329
9

Para las carrozas IEEE, podrías hacer algo como esto.

int next_power_of_two(float a_F){
    int f = *(int*)&a_F;
    int b = f << 9 != 0; // If we're a power of two this is 0, otherwise this is 1

    f >>= 23; // remove factional part of floating point number
    f -= 127; // subtract 127 (the bias) from the exponent

    // adds one to the exponent if were not a power of two, 
    // then raises our new exponent to the power of two again.
    return (1 << (f + b)); 
}

Si necesita una solución entera y puede usar el ensamblaje en línea, BSR le dará el log2 de un entero en el x86. Cuenta cuántos bits correctos se establecen, que es exactamente igual al log2 de ese número. Otros procesadores tienen instrucciones similares (a menudo), como CLZ y, dependiendo de su compilador, puede haber un intrínseco disponible para hacer el trabajo por usted.

Jasper Bekkers
fuente
Este es un evento interesante, aunque no esté relacionado con la pregunta (quiero redondear solo los enteros), probaré este ..
Naveen
Se le ocurrió después de leer el artículo de Wikipedia sobre flotadores. Además de eso, lo he usado para calcular raíces cuadradas en precisión entera. También agradable, pero aún más sin relación.
Jasper Bekkers
Esto rompe las estrictas reglas de alias. En algunos compiladores puede no funcionar o emitir una advertencia.
martinkunev
6

A pesar de que la pregunta está etiquetada caquí, mis cinco centavos. Por suerte, C ++ 20 incluiría std::ceil2y std::floor2(ver aquí ). Son consexprfunciones de plantilla, la implementación actual de GCC usa desplazamiento de bits y funciona con cualquier tipo integral sin signo.

kreuzerkrieg
fuente
2
Recientemente lo renombraron como bit_ceil open-std.org/JTC1/SC22/WG21/docs/papers/2020/p1956r1.pdf
Wolfgang Brehm
5
/*
** http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
*/
#define __LOG2A(s) ((s &0xffffffff00000000) ? (32 +__LOG2B(s >>32)): (__LOG2B(s)))
#define __LOG2B(s) ((s &0xffff0000)         ? (16 +__LOG2C(s >>16)): (__LOG2C(s)))
#define __LOG2C(s) ((s &0xff00)             ? (8  +__LOG2D(s >>8)) : (__LOG2D(s)))
#define __LOG2D(s) ((s &0xf0)               ? (4  +__LOG2E(s >>4)) : (__LOG2E(s)))
#define __LOG2E(s) ((s &0xc)                ? (2  +__LOG2F(s >>2)) : (__LOG2F(s)))
#define __LOG2F(s) ((s &0x2)                ? (1)                  : (0))

#define LOG2_UINT64 __LOG2A
#define LOG2_UINT32 __LOG2B
#define LOG2_UINT16 __LOG2C
#define LOG2_UINT8  __LOG2D

static inline uint64_t
next_power_of_2(uint64_t i)
{
#if defined(__GNUC__)
    return 1UL <<(1 +(63 -__builtin_clzl(i -1)));
#else
    i =i -1;
    i =LOG2_UINT64(i);
    return 1UL <<(1 +i);
#endif
}

Si no desea aventurarse en el ámbito del comportamiento indefinido, el valor de entrada debe estar entre 1 y 2 ^ 63. La macro también es útil para establecer constante en tiempo de compilación.

Philip J. Fry
fuente
Esta es probablemente la peor solución (también le falta el sufijo ULL en la constante de 64 bits). Esto generará 32 pruebas por entrada en todos los casos. Es mejor usar un ciclo while, siempre será más rápido o a la misma velocidad.
xryl669
1
PERO ... esto puede ser evaluado por el preprocesador si la entrada es constante y, por lo tanto, ¡operación CERO en tiempo de ejecución!
Michael
4

Para completar, aquí hay una implementación de punto flotante en bog-standard C.

double next_power_of_two(double value) {
    int exp;
    if(frexp(value, &exp) == 0.5) {
        // Omit this case to round precise powers of two up to the *next* power
        return value;
    }
    return ldexp(1.0, exp);
}
doynax
fuente
1
Navegadores aleatorios, si lees este comentario, elige este código. Esta es claramente la mejor respuesta, no hay instrucciones especiales, ni un poco de giro, solo un código eficiente, portátil y estándar. Adivinando por qué nadie más lo votó ^^
CoffeDeveloper
55
Navegadores aleatorios, esto va a ser muy lento si no tiene un hardware especializado de coma flotante. En x86, puede ejecutar círculos alrededor de este código utilizando bit twiddling. rep bsr ecx,eax; mov eax,0; cmovnz eax,2; shl eax,cles aproximadamente 25 veces más rápido.
Johan
4

Una solución específica eficiente de Microsoft (por ejemplo, Visual Studio 2017) en C / C ++ para la entrada de enteros. Maneja el caso de la entrada que coincide exactamente con una potencia de dos valores disminuyendo antes de verificar la ubicación del 1 bit más significativo.

inline unsigned int ExpandToPowerOf2(unsigned int Value)
{
    unsigned long Index;
    _BitScanReverse(&Index, Value - 1);
    return (1U << (Index + 1));
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

#if defined(WIN64) // The _BitScanReverse64 intrinsic is only available for 64 bit builds because it depends on x64

inline unsigned long long ExpandToPowerOf2(unsigned long long Value)
{
    unsigned long Index;
    _BitScanReverse64(&Index, Value - 1);
    return (1ULL << (Index + 1));
}

#endif

Esto genera 5 o más instrucciones en línea para un procesador Intel similar al siguiente:

dec eax
bsr rcx, rax
inc ecx
mov eax, 1
shl rax, cl

Aparentemente, el compilador de Visual Studio C ++ no está codificado para optimizar esto para valores de tiempo de compilación, pero no es que haya muchas instrucciones allí.

Editar:

Si desea que un valor de entrada de 1 produzca 1 (2 a la potencia cero), una pequeña modificación al código anterior aún genera instrucciones directas sin ramificación.

inline unsigned int ExpandToPowerOf2(unsigned int Value)
{
    unsigned long Index;
    _BitScanReverse(&Index, --Value);
    if (Value == 0)
        Index = (unsigned long) -1;
    return (1U << (Index + 1));
}

Genera solo unas pocas instrucciones más. El truco es que Index puede ser reemplazado por una prueba seguida de una instrucción cmove.

NoelC
fuente
Un pequeño error: debería devolver 1 por 1, aunque no lo hace.
0kcats
Gracias. En la aplicación para la que se desarrolló, explícitamente necesitábamos 2 para la primera potencia cuando se ingresa 1. 1 podría tomarse como un caso especial con un condicional sin generar demasiadas instrucciones más, imagino.
NoelC
Se actualizó la respuesta para incluir una versión que devuelve 1 para un valor de entrada de 1.
NoelC
3

En x86 puede usar las instrucciones de manipulación de bits sse4 para hacerlo más rápido.

//assume input is in eax
popcnt edx,eax
lzcnt ecx,eax
cmp edx,1
jle @done       //popcnt says its a power of 2, return input unchanged
mov eax,2
shl eax,cl
@done: rep ret

En c puede usar las intrínsecas coincidentes.

Johan
fuente
Inútil pero IMPRESIONANTE!
Marco
3

Aquí está mi solución en C. ¡Espero que esto ayude!

int next_power_of_two(int n) {
    int i = 0;
    for (--n; n > 0; n >>= 1) {
        i++;
    }
    return 1 << i;
}
Kevin Yang
fuente
0

Muchas arquitecturas de procesador admiten log base 2u operaciones muy similares count leading zeros. Muchos compiladores tienen intrínsecos para ello. Ver https://en.wikipedia.org/wiki/Find_first_set

Simón
fuente
no se trata de encontrar el bit de ajuste más alto (= bsr) o contar los ceros iniciales. quiere redondear a la potencia más cercana de 2. la respuesta con "restar 1, luego hacer bsr y desplazar 1 a la izquierda" hace eso.
Flo
0

Asumiendo que tienes un buen compilador y que puede hacer un poco de tonterías antes de eso, en este punto, ¡pero de todos modos esto funciona!

    // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
    #define SH1(v)  ((v-1) | ((v-1) >> 1))            // accidently came up w/ this...
    #define SH2(v)  ((v) | ((v) >> 2))
    #define SH4(v)  ((v) | ((v) >> 4))
    #define SH8(v)  ((v) | ((v) >> 8))
    #define SH16(v) ((v) | ((v) >> 16))
    #define OP(v) (SH16(SH8(SH4(SH2(SH1(v))))))         

    #define CB0(v)   ((v) - (((v) >> 1) & 0x55555555))
    #define CB1(v)   (((v) & 0x33333333) + (((v) >> 2) & 0x33333333))
    #define CB2(v)   ((((v) + ((v) >> 4) & 0xF0F0F0F) * 0x1010101) >> 24)
    #define CBSET(v) (CB2(CB1(CB0((v)))))
    #define FLOG2(v) (CBSET(OP(v)))

Código de prueba a continuación:

#include <iostream>

using namespace std;

// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
#define SH1(v)  ((v-1) | ((v-1) >> 1))  // accidently guess this...
#define SH2(v)  ((v) | ((v) >> 2))
#define SH4(v)  ((v) | ((v) >> 4))
#define SH8(v)  ((v) | ((v) >> 8))
#define SH16(v) ((v) | ((v) >> 16))
#define OP(v) (SH16(SH8(SH4(SH2(SH1(v))))))         

#define CB0(v)   ((v) - (((v) >> 1) & 0x55555555))
#define CB1(v)   (((v) & 0x33333333) + (((v) >> 2) & 0x33333333))
#define CB2(v)   ((((v) + ((v) >> 4) & 0xF0F0F0F) * 0x1010101) >> 24)
#define CBSET(v) (CB2(CB1(CB0((v)))))
#define FLOG2(v) (CBSET(OP(v))) 

#define SZ4         FLOG2(4)
#define SZ6         FLOG2(6)
#define SZ7         FLOG2(7)
#define SZ8         FLOG2(8) 
#define SZ9         FLOG2(9)
#define SZ16        FLOG2(16)
#define SZ17        FLOG2(17)
#define SZ127       FLOG2(127)
#define SZ1023      FLOG2(1023)
#define SZ1024      FLOG2(1024)
#define SZ2_17      FLOG2((1ul << 17))  // 
#define SZ_LOG2     FLOG2(SZ)

#define DBG_PRINT(x) do { std::printf("Line:%-4d" "  %10s = %-10d\n", __LINE__, #x, x); } while(0);

uint32_t arrTble[FLOG2(63)];

int main(){
    int8_t n;

    DBG_PRINT(SZ4);    
    DBG_PRINT(SZ6);    
    DBG_PRINT(SZ7);    
    DBG_PRINT(SZ8);    
    DBG_PRINT(SZ9); 
    DBG_PRINT(SZ16);
    DBG_PRINT(SZ17);
    DBG_PRINT(SZ127);
    DBG_PRINT(SZ1023);
    DBG_PRINT(SZ1024);
    DBG_PRINT(SZ2_17);

    return(0);
}

Salidas:

Line:39           SZ4 = 2
Line:40           SZ6 = 3
Line:41           SZ7 = 3
Line:42           SZ8 = 3
Line:43           SZ9 = 4
Line:44          SZ16 = 4
Line:45          SZ17 = 5
Line:46         SZ127 = 7
Line:47        SZ1023 = 10
Line:48        SZ1024 = 10
Line:49        SZ2_16 = 17
nimig18
fuente
0

Estoy tratando de obtener la potencia inferior más cercana de 2 e hice esta función. Que te ayude. Simplemente multiplica el número inferior más cercano por 2 para obtener la potencia superior más cercana de 2

int nearest_upper_power(int number){
    int temp=number;
    while((number&(number-1))!=0){
        temp<<=1;
        number&=temp;
    }
    //Here number is closest lower power 
    number*=2;
    return number;
}
Cody Piersall
fuente
0

Respuesta adaptada de Paul Dixon a Excel, esto funciona perfectamente.

 =POWER(2,CEILING.MATH(LOG(A1)/LOG(2)))
Tim Tharratt
fuente
0

Una variante de la respuesta @YannDroneaud válida para x==1, solo para plataformas x86, compiladores, gcc o clang:

__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
    assert(x > 0);
    assert(x <= ((UINT32_MAX/2) + 1));
#endif
  int clz;
  uint32_t xm1 = x-1;
  asm(
    "lzcnt %1,%0"
    :"=r" (clz)
    :"rm" (xm1)
    :"cc"
    );
    return 1 << (32 - clz);
}
Oliv
fuente
0

Esto es lo que estoy usando para que esta sea una expresión constante, si la entrada es una expresión constante.

#define uptopow2_0(v) ((v) - 1)
#define uptopow2_1(v) (uptopow2_0(v) | uptopow2_0(v) >> 1)
#define uptopow2_2(v) (uptopow2_1(v) | uptopow2_1(v) >> 2)
#define uptopow2_3(v) (uptopow2_2(v) | uptopow2_2(v) >> 4)
#define uptopow2_4(v) (uptopow2_3(v) | uptopow2_3(v) >> 8)
#define uptopow2_5(v) (uptopow2_4(v) | uptopow2_4(v) >> 16)

#define uptopow2(v) (uptopow2_5(v) + 1)  /* this is the one programmer uses */

Entonces, por ejemplo, una expresión como:

uptopow2(sizeof (struct foo))

se reducirá muy bien a una constante.

Kaz
fuente
0

Puede encontrar la siguiente aclaración útil para su propósito:

Aashay Sathe
fuente
0

Conviértalo a flotante y luego use .hex () que muestra la representación IEEE normalizada.

>>> float(789).hex() '0x1.8a80000000000p+9'

Luego solo extraiga el exponente y agregue 1.

>>> int(float(789).hex().split('p+')[1]) + 1 10

Y elevar 2 a este poder.

>>> 2 ** (int(float(789).hex().split('p+')[1]) + 1) 1024

David Wallace
fuente
Tenga en cuenta que esta respuesta está en Python
David Wallace
0
import sys


def is_power2(x):
    return x > 0 and ((x & (x - 1)) == 0)


def find_nearest_power2(x):
    if x <= 0:
        raise ValueError("invalid input")
    if is_power2(x):
        return x
    else:
        bits = get_bits(x)
        upper = 1 << (bits)
        lower = 1 << (bits - 1)
        mid = (upper + lower) // 2
        if (x - mid) > 0:
            return upper
        else:
            return lower


def get_bits(x):
    """return number of bits in binary representation"""
    if x < 0:
        raise ValueError("invalid input: input should be positive integer")
    count = 0
    while (x != 0):
        try:
            x = x >> 1
        except TypeError as error:
            print(error, "input should be of type integer")
            sys.exit(1)
        count += 1
    return count
Yossarian42
fuente
-1

Si lo necesita para cosas relacionadas con OpenGL:

/* Compute the nearest power of 2 number that is 
 * less than or equal to the value passed in. 
 */
static GLuint 
nearestPower( GLuint value )
{
    int i = 1;

    if (value == 0) return -1;      /* Error! */
    for (;;) {
         if (value == 1) return i;
         else if (value == 3) return i*4;
         value >>= 1; i *= 2;
    }
}
Paulo Lopes
fuente
8
'for' es un bucle.
florin
1
florin: lo es. y se usa como un bucle aquí, ¿no?
Tamas Czinege
9
DrJokepu - Creo que Florin quiso decir aquí que el OP solicitó una solución sin bucle
Eli Bendersky,
-1

Si quieres una plantilla de una línea. Aquí está

int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>1)>>2)>>4)>>8)>>16); }

o

int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>(1<<0))>>(1<<1))>>(1<<2))>>(1<<3))>>(1<<4)); }
Vo Hoang Anh
fuente
Este es un comportamiento indefinido en C o C ++ y dará lugar a errores. Modificar nvarias veces sin un punto de secuencia no es válido. Lo escribió como si n-=1fuera a suceder primero, pero la única garantía aquí es que ncontiene su nuevo valor después de ;y los paréntesis no cambian eso.
Sam Hocevar
Más al punto, hace que mis ojos sangren.
Donal Fellows