Jan 192013
 

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 Responses to “Next greater power of 2”

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

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)