Given an unsigned int n, find the integer greater than or equal to n which is a power of 2. For example:
Input Output ----- ------ 6 8 12 16 64 64
Answer:
The power of 2 will only have one bit set in its binary representation. We just have to find a number greater than n with only one bit set in its binary representation.
we can find so by right-shifting ‘1‘ till it becomes greater than n.
if n = 6 (110)
1 < 110
10 < 110
100 < 110
1000 > 110
Hence 1000, or 8 is the answer (which is greater than 110 or 6).
unsigned int nextPowerOfTwo(unsigned int n) { unsigned int result = 1; // If n is a power of 2 then return n itself if (n && !(n & (n - 1))) return n; while (result < n) result <<= 1; return result; }
3 Comments
I thinks Instead of (n &&!(n & (n – 1))) if (!(n & (n – 1)) is sufficient.
this will fail for n == 0.. the check of extra n is just for the case when n is zero.. because for n==0 (!(n&(n-1)) is true.. but zero is not a power of two..
this will fail for n == 0.. the check of extra n is just for the case when n is zero.. because for n==0 (!(n&(n-1)) is true.. but zero is not a power of two..