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.
Input : n = 5
Output: 8
Input : n = 17
Output : 32
Input : n = 32
Output : 32
There are plenty of solutions for this. Let us take the example of 17 to explain some of them.
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
[ad type=”banner”]
Method 2 (By getting the position of only set bit in result )
/* If n is a power of 2 then return n */
1 If (n & !(n&(n-1))) 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
/* Now count has the position of set bit in result */
3 Return (1 << count)
Example:
Let us try for 17
count = 5
p = 32
[pastacode lang=”c” manual=”unsigned%20int%20nextPowerOf2(unsigned%20int%20n)%0A%7B%0A%20%20unsigned%20count%20%3D%200%3B%0A%20%0A%20%20%2F*%20First%20n%20in%20the%20below%20condition%20is%20for%20the%20case%20where%20n%20is%200*%2F%0A%20%20if%20(n%20%26%26%20!(n%26(n-1)))%0A%20%20%20%20return%20n%3B%0A%20%0A%20%20while(%20n%20!%3D%200)%0A%20%20%7B%0A%20%20%20%20n%20%20%3E%3E%3D%201%3B%0A%20%20%20%20count%20%2B%3D%201%3B%0A%20%20%7D%0A%20%0A%20%20return%201%20%3C%3C%20count%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20unsigned%20int%20n%20%3D%200%3B%0A%20%20printf(%22%25d%22%2C%20nextPowerOf2(n))%3B%0A%20%20return%200%3B%0A%7D” message=”C Programming” highlight=”” provider=”manual”/]
[ad type=”banner”]
Method 3(Shift result one by one)
Thanks to coderyogi for suggesting this method . This method is a variation of method 2 where instead of getting count, we shift the result one by one in a loop.
Time Complexity: O(lgn)
[ad type=”banner”] Method 4(Customized and Fast)
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
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)
Program:
[pastacode lang=”c” manual=”%23include%20%3Cstdio.h%3E%0A%20%0A%2F*%20Finds%20next%20power%20of%20two%20for%20n.%20If%20n%20itself%0A%20%20%20is%20a%20power%20of%20two%20then%20returns%20n*%2F%0Aunsigned%20int%20nextPowerOf2(unsigned%20int%20n)%0A%7B%0A%20%20%20%20n–%3B%0A%20%20%20%20n%20%7C%3D%20n%20%3E%3E%201%3B%0A%20%20%20%20n%20%7C%3D%20n%20%3E%3E%202%3B%0A%20%20%20%20n%20%7C%3D%20n%20%3E%3E%204%3B%0A%20%20%20%20n%20%7C%3D%20n%20%3E%3E%208%3B%0A%20%20%20%20n%20%7C%3D%20n%20%3E%3E%2016%3B%0A%20%20%20%20n%2B%2B%3B%0A%20%20%20%20return%20n%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20unsigned%20int%20n%20%3D%205%3B%0A%20%20%20%20printf(%22%25d%22%2C%20nextPowerOf2(n))%3B%0A%20%20%20%20return%200%3B%0A%7D%20%20%20%20%20%20″ message=”C Programming” highlight=”” provider=”manual”/]Time Complexity: O(lgn)
[ad type=”banner”]