# Program to check if a given number is power of two or not?

August 20, 2017
Posted by Pumpkin

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.

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

0 00000 Zero is not having any set bit, so it is not a power of two.
1 00001 Power of Two
2 00010 Power of Two
3 00011
4 00100 Power of Two
5 00101
6 00110
7 00111
8 01000 Power of Two
9 01001
10 01010
11 01011
12 01100
13 01101
14 01110
15 01111
16 10000 Power of Two

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

Java Program Implementation

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

The naive approach requires one iteration per bit, until no more bits are set or second set bit is found.

For Example, it will require 7 iteraton to check if 65  (0100 0001)  is power of two or not?

## 2) Brian Kernighan's Approach

It uses n = n & (n-1) approach.

If you perform bitwise operation on n and (n-1), it produces the number with set bits one less than the original number.  For example, if has 4 set bits and if you perform n&(n-1), it produces the number with 3 set bits.

So, if you are having one set bit in n, then n&(n-1) produces zero. We also need to keep additional check of (n>0) as for n=0, it will produce zero, but 0 is not the power of two.

Java Program Implementation

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

To understand more about Brian Kernighan's Approach, you check our article here.

That's all for this topic. If you guys can think of any more similar java programs, feel free drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here

Happy Learning 🙂

## Further Reading For interview Preparation

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
```<pre><code class="java">
String foo = "bar";
</code></pre>
```

Total Post : 80