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

many people answer my questions, so me will answer yours (hopefully it's right):

probably most simple (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 many ways if you want to optimize.

Answer 2

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 3

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.

Answer 4

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 5

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).