Find if a no is Power of Two

Problem: Write a C program to find if a number is of power of 2?

Solution:

Method 1: (Using arithmetic)

Keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.

/* Function to check if x is power of 2*/

bool isPowerOfTwo(int n)
{
	if (n == 0)
		return 0;
	while (n != 1)
	{
		if (n%2 != 0)
			return 0;
		n = n/2;
	}
	return 1;
}

Method 2: (Using Bitwise operator)

If we subtract 1 from a number that is power of 2 then all unset bits after the only set bit become set and the set bit become unset.

For example for 4 ( 100) and 16(10000), we get following after subtracting 1
3 –> 011
15 –> 01111

So, if a number n is a power of 2 then bitwise & of n and n-1 will give zero. We can say n is a power of 2 or not based on value of n &(n-1).

bool IsPowerOfTwo(long x)
{
    return (x & (x - 1)) == 0;
}

For completeness, zero is not a power of two. If you want to take into account that edge case, here’s how:

bool IsPowerOfTwo(long x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

Lets understand this with example
bool b = IsPowerOfTwo(4)
if x = 4

return (4 != 0) && ((4 & (4-1)) == 0);
Well we already know that 4 != 0 evals to true, so far so good. But what about:

((4 & (4-1)) == 0)
This translates to this of course:

((4 & 3) == 0)
But what exactly is 4&3?

The binary representation of 4 is 100 and the binary representation of 3 is 011 (remember the & takes the binary representation of these numbers. So we have:

100 = 4
011 = 3

1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, and 0 & 1 = 0. So we do the math:

100
011
—-
000

One Thought on “Find if a no is Power of Two

  1. Manas Gupta on July 8, 2015 at 4:07 am said:

    public static boolean isPowerOfTwo(int number) {
    int count = 0;
    if (number == 0)
    return true;
    while (number > 0) {
    if ((number & 1) == 1) {
    count++;
    }
    number >>= 1;
    }
    return count == 1 ? true : false;
    }

Leave a Reply

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

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=""> <strike> <strong>

Post Navigation