Previous power of 2

Question

There is a lot of information on how to find the next power of 2 of a given value (see refs) but I cannot find any to get the previous power of two.

The only way I find so far is to keep a table with all power of two up to 2^64 and make a simple lookup.

• Acius' Snippets
• gamedev
• Bit Twiddling Hacks
• Stack Overflow

Answer 1

From Hacker's Delight, a nice branchless solution:

uint32_t flp2 (uint32_t x)
{
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x - (x >> 1);
}

This typically takes 12 instructions. You can do it in fewer if your CPU has a "count leading zeroes" instruction.

Answer 2

Here is a one liner for posterity (ruby):

2**Math.log(input, 2).floor(0)

Answer 3

uint32_t previous_power_of_two( uint32_t x ) {
    if (x == 0) {
        return 0;
    }
    // x--; Uncomment this, if you want a strictly less than 'x' result.
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x - (x >> 1);
}

Thanks for the responses. I will try to sum them up and explain a little bit clearer. What this algorithm does is changing to 'ones' all bits after the first 'one' bit, cause these are the only bits that can make our 'x' larger than its previous power of two. After making sure they are 'ones', it just removes them, leaving the first 'one' bit intact. That single bit in its place is our previous power of two.

Answer 4

Probably the simplest approach (for positive numbers):

// find next (must be greater) power, and go one back
p = 1; while (p <= n) p <<= 1; p >>= 1;

You can make variations in many ways if you want to optimize.

Answer 5

The g++ compiler provides a builtin function __builtin_clz that counts leading zeros:

So we could do:

int previousPowerOfTwo(unsigned int x) {
  return 1 << (sizeof(x)*8 - 1) - __builtin_clz(x);
}

int main () {
  std::cout << previousPowerOfTwo(7)  << std::endl;
  std::cout << previousPowerOfTwo(31) << std::endl;
  std::cout << previousPowerOfTwo(33) << std::endl;
  std::cout << previousPowerOfTwo(8)  << std::endl;
  std::cout << previousPowerOfTwo(91) << std::endl;

  return 0;
}

Results:

4
16
32
8
64

But note that, for x == 0, __builtin_clz return is undefined.

Answer 6

If you can get the next-higher power of 2, the next-lower power of 2 is either that next-higher or half that. It depends on what you consider to be the "next higher" for any power of 2 (and what you consider to be the next-lower power of 2).

Answer 7

Solution with bit manipulation only:

long FindLargestPowerOf2LowerThanN(long n)
{
    Assert.IsTrue(n > 0);

    byte digits = 0;
    while (n > 0)
    {
        n >>= 1;
        digits++;
    }                            

    return 1 << (digits - 1);
}

Example:

FindLargestPowerOf2LowerThanN(6):
Our Goal is to get 4 or 100
1) 6 is 110
2) 110 has 3 digits
3) Since we need to find the largest power of 2 lower than n we subtract 1 from digits
4) 1 << 2 is equal to 100 

FindLargestPowerOf2LowerThanN(132):
Our Goal is to get 128 or 10000000
1) 6 is 10000100
2) 10000100 has 8 digits
3) Since we need to find the largest power of 2 lower than n we subtract 1 from digits
4) 1 << 7 is equal to 10000000 

Answer 8

What about

if (tt = v >> 16)
{
   r = (t = tt >> 8) ? 0x1000000 * Table256[t] : 0x10000 * Table256[tt];
}
else 
{
  r = (t = v >> 8) ? 0x100 * Table256[t] : Table256[v];
}

It is just modified method from http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup. This require like 7 operations and it might be faster to replace multiplications whit shift.

Answer 9

I write my answer here just in case I need to reference it in the future.

For C language, this is what I believed to be the "ultimate" solution for the previous power of 2 function. The following code:

• is targeted for C language (not C++),

• uses compiler built-ins to yield efficient code (CLZ or BSR instruction) if compiler supports any,

• is portable (standard C and no assembly) with the exception of built-ins, and

• addresses undefined behavior of the compiler built-ins (when x is 0).

If you're writing in C++, you may adjust the code appropriately. Note that C++20 introduces std::bit_floor which does the exact same thing.

#include <limits.h>

#ifdef _MSC_VER
# if _MSC_VER >= 1400
/* _BitScanReverse is introduced in Visual C++ 2005 and requires
   <intrin.h> (also introduced in Visual C++ 2005). */
#include <intrin.h>
#pragma intrinsic(_BitScanReverse)
#pragma intrinsic(_BitScanReverse64)
#  define HAVE_BITSCANREVERSE 1
# endif
#endif

/* Macro indicating that the compiler supports __builtin_clz().
   The name HAVE_BUILTIN_CLZ seems to be the most common, but in some
   projects HAVE__BUILTIN_CLZ is used instead. */
#ifdef __has_builtin
# if __has_builtin(__builtin_clz)
#  define HAVE_BUILTIN_CLZ 1
# endif
#elif defined(__GNUC__)
# if (__GNUC__ > 3)
#  define HAVE_BUILTIN_CLZ 1
# elif defined(__GNUC_MINOR__)
#  if (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
#   define HAVE_BUILTIN_CLZ 1
#  endif
# endif
#endif


/**
 * Returns the largest power of two that is not greater than x. If x
 * is 0, returns 0.
 */
unsigned int prev_power_of_2(unsigned int x)
{
#ifdef HAVE_BITSCANREVERSE
    if (x <= 0) {
        return 0;
    } else {
        unsigned long int index;
        (void) _BitScanReverse(&index, x);
        return (1U << index);
    }
#elif defined(HAVE_BUILTIN_CLZ)
    if (x <= 0) {
        return 0;
    }
    return (1U << (sizeof(x) * CHAR_BIT - 1 - __builtin_clz(x)));
#else
    /* Fastest known solution without compiler built-ins or integer
       logarithm instructions.
       From the book "Hacker's Delight".
       Converted to a loop for smaller code size.
       ("gcc -O3" will unroll this.) */
    {
        unsigned int shift;
        for (shift = 1; shift < sizeof(x) * CHAR_BIT; shift <<= 1) {
            x |= (x >> shift);
        }
    }
    return (x - (x >> 1));
#endif
}

unsigned long long prev_power_of_2_long_long(unsigned long long x)
{
#if (defined(HAVE_BITSCANREVERSE) && \
    ULLONG_MAX == 18446744073709551615ULL)
    if (x <= 0) {
        return 0;
    } else {
        /* assert(sizeof(__int64) == sizeof(long long)); */
        unsigned long int index;
        (void) _BitScanReverse64(&index, x);
        return (1ULL << index);
    }
#elif defined(HAVE_BUILTIN_CLZ)
    if (x <= 0) {
        return 0;
    }
    return (1ULL << (sizeof(x) * CHAR_BIT - 1 - __builtin_clzll(x)));
#else
    {
        unsigned int shift;
        for (shift = 1; shift < sizeof(x) * CHAR_BIT; shift <<= 1) {
            x |= (x >> shift);
        }
    }
    return (x - (x >> 1));
#endif
}

Answer 10

Using a count leading zeros function (a.k.a. bitscan right), determining the next lowest power of 2 is easy:

uint32_t lower_power_of_2(uint32_t x) {
  assert(x != 0);
  return 1 << (31 - __builtin_clz(x));
}

Here, __builtin_clz is recognized by gcc and clang. Use _BitScanReverse with a Microsoft compiler.

Answer 11

This is my way:

//n is the number you want to find the previus power of 2
long m = 1;
while(n > 1){
    n >>= 1;
    m <<= 1;
}
//m is the previous power of two

Answer 12

When you work in base 2, you can jump from a power of two to the next one by just adding or removing a digit from the right.

For instance, the previous power of two of the number 8 is the number 4. In binary:

01000 -> 0100 (we remove the trailing zero to get number 4)

So the algorithm to solve the calculus of the previous power of two is:

previousPower := number shr 1

previousPower = number >> 1

(or any other syntax)

Answer 13

This can be done in one line.

int nextLowerPowerOf2 = i <= 0
                        ? 0
                        : ((i & (~i + 1)) == i)
                            ? i >> 1
                            : (1 << (int)Math.Log(i, 2));

result

i    power_of_2
-2    0
-1    0
0    0
1    0
2    1
3    2
4    2
5    4
6    4
7    4
8    4
9    8

Here's a more readable version in c#, with the <=0 guard clause distributed to the utility methods.

int nextLowerPowerOf2 = IsPowerOfTwo(i) 
    ? i >> 1 // shift it right
    : GetPowerOfTwoLessThanOrEqualTo(i);

public static int GetPowerOfTwoLessThanOrEqualTo(int x)
{
    return (x <= 0 ? 0 : (1 << (int)Math.Log(x, 2)));
}

public static bool IsPowerOfTwo(int x)
{
    return (((x & (~x + 1)) == x) && (x > 0));
}

Answer 14

Below code will find the previous power of 2:

int n = 100;
    n /= 2;//commenting this will gives the next power of 2
    n |= n>>1;
    n |= n>>2;
    n |= n>>4;
    n |= n>>16;

System.out.println(n+1);

Answer 15

This is my current solution to find the next and previous powers of two of any given positive integer n and also a small function to determine if a number is power of two.

This implementation is for Ruby.

class Integer

  def power_of_two?
    (self & (self - 1) == 0)
  end

  def next_power_of_two
    return 1 if self <= 0
    val = self
    val = val - 1
    val = (val >> 1) | val
    val = (val >> 2) | val
    val = (val >> 4) | val
    val = (val >> 8) | val
    val = (val >> 16) | val
    val = (val >> 32) | val if self.class == Bignum
    val = val + 1
  end

  def prev_power_of_two
   return 1 if self <= 0
   val = self
   val = val - 1
   val = (val >> 1) | val
   val = (val >> 2) | val
   val = (val >> 4) | val
   val = (val >> 8) | val
   val = (val >> 16) | val
   val = (val >> 32) | val if self.class == Bignum
   val = val - (val >> 1)
  end
end

Example use:

10.power_of_two? => false
16.power_of_two? => true
10.next_power_of_two => 16
10.prev_power_of_two => 8

For the previous power of two, finding the next and dividing by two is slightly slower than the method above.

I am not sure how it works with Bignums.