## Sunday, March 23, 2014

### 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