Redondeando a la siguiente potencia de 2

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?

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.

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?

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;

}

Creo que esto también funciona:

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

Y la respuesta es power.

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));
}

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

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.

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.

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.

/*
** 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.

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);
}

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.

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.

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

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

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

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

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

 =POWER(2,CEILING.MATH(LOG(A1)/LOG(2)))

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);
}

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.

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

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

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

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

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)); }