Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Rounding up to next power of 2

People also ask

How do you find the power of 2?

Another solution is to keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.

How do you find the next power of 2 in physical education?

If the number of teams is a power of 2, then number of rounds will exactly be multiple of 2 up to that number. If number of teams is not a power of 2, then number of rounds will be equal to the multiple of next power of two. The next power of 2 after 21 is 32 which is 25.

Is the power of 2 Bitwise?

It determines whether integer is power of 2 or not. If (x & (x-1)) is zero then the number is power of 2. For example, let x be 8 ( 1000 in binary); then x-1 = 7 ( 0111 ). This outputs the bit is power of 2 .


Check the Bit Twiddling Hacks. You need to get the base 2 logarithm, then add 1 to that. Example for a 32-bit value:

Round up to the next highest power of 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++;

The extension to other widths should be obvious.


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

This works by finding the number you'd have raise 2 by to get x (take the log of the number, and divide by the log of the desired base, see wikipedia for more). Then round that up with ceil to get the nearest whole number power.

This is a more general purpose (i.e. slower!) method than the bitwise methods linked elsewhere, but good to know the maths, eh?


I think this works, too:

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

And the answer is 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;

}

If you're using GCC, you might want to have a look at Optimizing the next_pow2() function by Lockless Inc.. This page describes a way to use built-in function builtin_clz() (count leading zero) and later use directly x86 (ia32) assembler instruction bsr (bit scan reverse), just like it's described in another answer's link to gamedev site. This code might be faster than those described in previous answer.

By the way, if you're not going to use assembler instruction and 64bit data type, you can use this

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

One more, although I use cycle, but thi is much faster than math operands

power of two "floor" option:

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

power of two "ceil" option:

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

UPDATE

As mentioned in comments there was mistake in ceil where its result was wrong.

Here are full functions:

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

For any unsigned type, building on the 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;
}

There isn't really a loop there as the compiler knows at compile time the number of iterations.