# Interview Questions

Ritambhara Technologies - Coding Interview Preparations > Interview Questions > Algorithms > Next greater power of 2

# Next greater power of 2

- January 19, 2013
- Posted by: Kamal Rawat
- Category: Algorithms

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; }

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