Next Power of 2

Problem

Write a function that, for a given no n, finds a number p which is greater than or equal to n and is a power of 2.

Example

    IP 5
    OP 8     

    IP 17
    OP 32     

    IP 32
    OP 32     

There are plenty of solutions for this. Let us take the example of 17 to explain some of them.

Solutions

Method 0 : Multiply number by 2 until we find it

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

Method 1 - Using Log of the number

    1.  Calculate Position of set bit in p(next power of 2):
        pos =  ceil(lgn)  (ceiling of log n with base 2)
    2.  Now calculate p:
        p   = pow(2, pos) 

Example

    Let us try for 17
            pos = 5
            p   = 32    

In one line

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

Method 2 - By getting the position of only set bit in result 
Here is the pseudocode :

 
    1  If n is a power of 2 then return n
    2  Else keep right shifting n until it becomes zero 
        and count no of shifts
        a. Initialize: count = 0
        b. While n ! = 0
                n = n>>1
                count = count + 1     
    3 Now count has the position of set bit in result  

Now we can check if number is power of 2, if (n &(n-1))==0. Please refer this post here.
Now lets take n = 17. This is not power of 2. Now we go to step 2.  Now we right shift it and increment the count, until it becomes 0.
n = 17
n = 10001
n >> 1 = 01000 , count = 1
n >> 1 = 00100 , count = 2
n >> 1 = 00010 , count = 3
n >> 1 = 00001 , count = 4
n >> 1 = 00000 , count = 5 ... the loop ends here

Now we left shift 1 (00001) count times wich results in 32.

C code

unsigned int nextPowerOf2(unsigned int n)
{
  unsigned count = 0;
 
  /* First n in the below condition is for the case where n is 0*/
  if (n && !(n&(n-1)))
    return n;
 
  while( n != 0)
  {
    n  >>= 1;
    count += 1;
  }
 
  return 1<<count;
}
 

Method 3 - Shift result one by one (Variation of method 2)
This method is a variation of method 2 where instead of getting count, we shift the result one by one in a loop.

C code

unsigned int nextPowerOf2(unsigned int n)
{
    unsigned int p = 1;
    if (n && !(n & (n - 1)))
        return n;
 
    while (p < n) {
        p <<= 1;
    }
    return p;
}

Time Complexity: O(lgn)

Method 4 - Customized and Fast
Pseudocode

    1. Subtract n by 1
       n = n -1

    2. Set all bits after the leftmost set bit.

    /* Below solution works only if integer is 32 bits */
                n = n | (n >> 1);
                n = n | (n >> 2);
                n = n | (n >> 4);
                n = n | (n >> 8);
                n = n | (n >> 16);
    3. Return n + 1

This will work for 32 bit integer. Of course, if you want 64 bit, just add n = n|(n >> 32). More - graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
Example:

Steps 1 & 3 of above algorithm are to handle cases 
of power of 2 numbers e.g., 1, 2, 4, 8, 16,

    Let us try for 17(10001)
    step 1
       n = n - 1 = 16 (10000)  
    step 2
       n = n | n >> 1
       n = 10000 | 01000
       n = 11000
       n = n | n >> 2
       n = 11000 | 00110
       n = 11110
       n = n | n >> 4
       n = 11110 | 00001
       n = 11111
       n = n | n >> 8
       n = 11111 | 00000
       n = 11111
       n = n | n >> 16
       n = 11110 | 00000
       n = 11111    

    step 3: Return n+1
     We get n + 1 as 100000 (32)

C Code

unsigned int nextPowerOf2(unsigned int n)
{
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;
    return n;
}

Time Complexity: O(lgn)

Method 5 -Method for floats (though question asks next power for integers)
Jasper Bekkers suggested good method for IEEE floats, and this may not be language agnostic.

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

References:
http://en.wikipedia.org/wiki/Power_of_2
geeksforgeeks
stackoverflow
Bit twiddling hacks


Thanks