Code Pumpkin

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

August 20, 2017
Posted by Pumpkin
Subscribe

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

    1. Program To Find Unique Array Element
    2. Program To Check Whether A Number Is Prime Or Not
    3. Program To Find Number Of Set Bits In The Binary Number
    4. Sudoku Solver
    5. N Queen Problem
    6. Graph Search – Breadth First Search
    7. Graph Search – Depth First Search
    8. interface VS abstract class
    9. Access Modifiers (public, private, protected and default scope)
    10. HashMap vs Hashtable Vs SynchronizedMap Vs ConcurrentHashMap
    11. CountDownLatch Vs CyclicBarrier

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

    Total Post : 80
    Subscribe
    Contribute Your Articles

    Interview Experiences

    Related Books

    Like Us On Facebook

    Alexa Page Rank