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.

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 : 88
Subscribe
Contribute Your Articles

Interview Experiences

Like Us On Facebook