**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 32There 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 = 32In 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

## 0 comments:

## Post a Comment