Is a number Power of Two

Last week, I was reading through an article written by Bill Venners (don’t read this now). Though the purpose of the article is to highlight some of the key interviewing techniques, I was excited by Josh Bloch question, “Finding is a number power of 2”.

After finding few answers other than the one mentioned in the above article, I put the same question to some of my colleagues/friends. Most of them (99% of people, including me) immediately came up with the following answer “recursive (Number/2)==0, then power of 2” or continuous multiplication with 2 gives that number, as shown below

int number = 8;
int tempNumber = 1;
while(tempNumber<number){
    tempNumber*=2;
}
if(tempNumber==number){
   System.out.println("Power of");
else{
   System.out.println("Not a power of");
}

Yes, the above solve the problem in hand, but is this an efficient one? Will this work for large numbers or gives overflow issues? For sure I can’t see this solution as an efficient one. So I contacted my genius friend Sree. Not to the surprise, he came up with a more efficient solution. I and 99% of my friends have seen the problem in decimal but Sree has seen it in bits. Without further ado let us see the (one line) code

 System.out.println(((number&(number-1))==0)?"Power of":"Not a power of");

Hope you too accept it to be more efficient than mine  One other solution proposed by Josh Bloch in the article http://www.artima.com/wbc/interprog.html (now read it) is

System.out.println(((number&(-number))==number)?"Power of":"Not a power of");

Which answer you came up with? Hey did you come up with some new one? Let us know the same.

Add to FacebookAdd to NewsvineAdd to DiggAdd to Del.icio.usAdd to StumbleuponAdd to RedditAdd to BlinklistAdd to TwitterAdd to TechnoratiAdd to Furl

About these ads

One Response

  1. fiddling with operators and bits..
    if bitwise X-OR of number and -number == 0, then power or 2. Else, Not a power of 2.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: