Non-recursive solution to tower of hanoi
January 17, 2013
Sorting a linked list
January 21, 2013

Next greater power of 2

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

  1. Raj Chaudhary says:

    I thinks Instead of (n &&!(n & (n – 1))) if (!(n & (n – 1)) is sufficient.

Leave a Reply to Sarah B Cancel reply

Your email address will not be published. Required fields are marked *