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)
Let us try for 17
pos = 5
p = 32
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**](http://k2code.blogspot.in/2009/12/c-code-to-check-if-integer-is-power-of.html).
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;
}
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](http://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](http://stackoverflow.com/users/31486/jasper-bekkers) suggested [good method](http://stackoverflow.com/questions/466204/rounding-off-to-nearest-power-of-2/466392#466392) 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](http://en.wikipedia.org/wiki/Power_of_2)
[geeksforgeeks](http://www.geeksforgeeks.org/next-power-of-2/)
[stackoverflow](http://stackoverflow.com/questions/466204/rounding-off-to-nearest-power-of-2)
[Bit twiddling hacks](http://graphics.stanford.edu/~seander/bithacks.html)
Thanks