Redondeando a la siguiente potencia de 2
Quiero escribir una función que devuelva la siguiente potencia de 2 número más cercana. Por ejemplo, si mi entrada es 789, la salida debería ser 1024. ¿Hay alguna manera de lograr esto sin usar ningún bucle, sino simplemente usando algunos operadores bit a bit?
Relacionado: El algoritmo para encontrar la potencia más pequeña de dos que sea mayor o igual a un valor dado es una pregunta de C++. Se introdujo C++ 20 std:bit_ceil, que permite al compilador hacer lo que sea óptimo para el sistema de destino, pero aún no hay nada equivalente disponible en ISO C portátil para escaneo de bits, recuento pop u otras operaciones de bits comunes que tienen la mayoría de las CPU. El código C portátil tiene que ser menos eficiente y/o más complicado.
Dado un número entero, ¿cómo encuentro la siguiente potencia más grande de dos usando juegos de bits? es una versión de la pregunta independiente del idioma con algunos C++ 11 y 17 constexprque usan extensiones GNU.
No es necesario que las respuestas a esta pregunta sean portátiles; Las versiones rápidas para varias plataformas son útiles.
Consulte los trucos para jugar con bits . Necesitas obtener el logaritmo de base 2 y luego sumarle 1. 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 ampliación a otros anchos debería ser obvia.
Una respuesta sobre Dado un número entero, ¿cómo encuentro la siguiente potencia más grande de dos usando juegos de bits? presenta alguna explicación de cómo funciona y ejemplos de los patrones de bits para un par de entradas.
next = pow(2, ceil(log(x)/log(2)));
Esto funciona encontrando el número por el que habría aumentado 2 para obtener x (tome el registro del número y divídalo por el registro de la base deseada; consulte wikipedia para obtener más información ). Luego redondea eso con ceil para obtener la potencia del número entero más cercano.
Este es un método de propósito más general (¡es decir, más lento!) que los métodos bit a bit vinculados en otros lugares, pero es bueno saber las matemáticas, ¿no?
Creo que esto también funciona:
int power = 1;
while(power < x)
power*=2;
Y la respuesta es power.
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;
}
