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

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.