Code Pumpkin

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

August 20, 2017
Posted by Abhi Andhariya

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

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

    n=5 | Is power of two

    n=4 | Is power of two

    Java Program Implementation

    public static boolean isPowerOfTwoApproach1(int n)
    	int count=0;
    				return false;
    		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 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 🙂

    If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.

    We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.

    About the Author

    Surviving Java Developer, Passionate Blogger, Table Tennis Lover, Bookworm, Occasional illustrator and a big fan of Joey Tribbiani, The Walking Dead and Game of Thrones...!!

    Tags: , , ,

    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";
    For more information on supported HTML tags in disqus comment, click here.
    Total Posts : 124
    follow us in feedly

    Like Us On Facebook