In this post, we will discuss about one of the easiest and commonly asked Bit Manipulation Interview Question i.e. Write a program to check if a given number is power of two or not?  

This post is continuation of our previuos article Program To Find Number Of Set Bits In The Number.  Both of the approach mentioned in that post can be used to find if a number is power of two or not. 

1. & and >> Approach (Naive Approach)
2. Brian Kernighan's Approach

How can we determine if a number is power of two or not?

Well If number is having only one set bit, we can say that number is power of two. For example, Lets look at the binary values of 0 to 16 numbers

1) & and >> Approach (naive Approach)

In this approach, we perform bitwise and (&) and  bitwise right shift (>>) operations for each bit in a number.

Step 1: (n&1) operation returns 1, if right most bit of the number is 1. 

Step 2 : If this returns 1, we increment our counter.

Step 3 : perform n=(n>>1) , so that we can check the value of 2nd right most bit.

Step 4 : We will continue step 1 to 3 until n becomes zero.  If we find second set bit in the  number, we will break the loop and return false.

Let's understand this by example, n=5 and n=4

public static boolean isPowerOfTwoApproach1(int n)
{
	int count=0;
	while(n>0)
	{
		if((n&1)==1)
		{
			if(count==1)
			{
				return false;
			}
			count++;
		}
		n = n>>1;

	}
	return (count==1);
}

public static boolean isPowerOfTwoApproach2(int n)
{
    return (n>0 && (n&(n-1))==0);
}