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.
fiddling with operators and bits..
if bitwise X-OR of number and -number == 0, then power or 2. Else, Not a power of 2.