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

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

**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)

**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:**

**Time Complexity:** O(lgn)

## Add Comment