Next Power of 2 | GeeksforGeeks
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.
Method 3(Shift result one by one)
This method is a variation of method 2 where instead of getting count, we shift the result one by one in a loop.
Read full article from Next Power of 2 | GeeksforGeeks
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.
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
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;}
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)
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.
unsigned int nextPowerOf2(unsigned int n){ unsigned int p = 1; if (n && !(n & (n - 1))) // java code: n != 0 && ((n & (n - 1)) == 0) return n; while (p < n) { p <<= 1; } return p;}