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

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

Decimal | Binary | Comments |
---|---|---|

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 **n **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 have any suggestions or queries, feel free to 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 🙂

- Binary Tree Introduction - August 1, 2018
- Tree Data Structure Terminologies – Set 2 - July 2, 2018
- Tree Data Structure Terminologies – Set 1 - July 1, 2018
- Immutable class with mutable member fields in Java - April 30, 2018
- Breaking Singleton using reflection and Enum Singleton - January 14, 2018

Tags: Bit Manipulation, Bitwise Operators, Core Java, Right Shift Operation

## Comments and Queries

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>For more information on supported HTML tags in disqus comment, click here.