c - tag and title near me

Redondeando al siguiente poder de 2

Question

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 utilizar ningún bucle sino simplemente utilizando algunos operadores bit a bit?

Answer 1

Asumiendo que tienes un buen compilador y puede hacer el truco antes de la mano, eso está por encima de mí 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);
}

Productos:

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

Answer 2

Comprueba los bits Twiddling Hacks . Necesitas obtener el logaritmo de la base 2, luego agrega 1 a eso.

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

Answer 3

Creo que esto también funciona:

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

Y la respuesta es power .

Answer 4

En x86 puedes usar las instrucciones de manipulación de bits sse4 para hacerlo 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 los intrínsecos coincidentes.

Answer 5

Intento obtener la potencia más baja más baja de 2 e hice esta función. Puede ayudarle. Simplemente multiplique el número más bajo más cercano por 2 para obtener la potencia superior más cercana a 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;
}

Answer 6

Muchas arquitecturas de procesador admiten la log base 2 o una operación muy similar: count leading zeros . Muchos compiladores tienen aspectos intrínsecos. Ver en.wikipedia.org/wiki/Find_first_set

Answer 7

Para completar esto, hay una implementación de punto flotante en Cog-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);
}

Answer 8

Para cualquier tipo sin firmar, basándose en los 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;
}

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

Answer 9

Para flotadores 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 ensamblado 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.

Answer 10

Si está utilizando GCC, le recomendamos echar un vistazo a la Optimización de la función next_pow2 () de Lockless Inc .. Esta página describe una forma de usar la función builtin_clz() (conteo de cero builtin_clz() ) y luego usar directamente x86 (ia32) instrucción de ensamblador bsr (bit scan reverse), 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 va a utilizar instrucciones de ensamblador y tipo de datos de 64 bits, puede 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));
}

Answer 11

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

Answer 12

Una más, aunque utilizo 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;

poder de la opción de dos "ceil":

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

Answer 13

/*
** 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 incursionar 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 el tiempo de compilación.

Answer 14

next = pow(2, ceil(log(x)/log(2)));

Esto funciona al encontrar el número que tendría que aumentar 2 para obtener x (tomar el registro del número, y dividir por el registro de la base deseada, ver wikipedia para más información ). Luego redondea eso con ceil para obtener el poder del número entero más cercano.

Este es un método más general (¡más lento!) Que los métodos bit a bit enlazados en otro lugar, pero es bueno saber las matemáticas, ¿eh?

Answer 15

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;

}