My (mostly technical) blog

Interview question: Check that an integer number is a power of two

Posted on: July 24, 2008

I got asked this question during an interview last week. I think I gave a wrong answer in the interview but I decided I needed to find the correct answer! I searched and found this solution which involved bit manipulations, though I didn’t find it intuitive.

I came up with this simple solution

public class PowerOfTwo {
	public static void main(String args[]){
		for(int n=0,limit=16; n<Math.pow(2, limit);n++)
			if(isPowerOfTwo(n))
				System.out.println(n);
	}

	private static boolean isPowerOfTwo(int n) {
		double logNbase2 =  Math.log(n)/Math.log(2);	
		int logNbase2Integer = (int) (Math.floor(logNbase2));
		
		if(logNbase2-logNbase2Integer==0)
			return true;
		else
			return false;
	}
}
&#91;/sourcecode&#93;

maybe not quite as elegant as the bit hack, but I understand it!

<b>Update:</b>
Actually, I understood how the bit hack function below works:

	private static boolean isPowerOfTwoFast(int n) {
		return ((n!=0) && (n&(n-1))==0);
	}

Note that powers of two have only 1 bit set to one:

1:  000001
2:  000010
4:  000100
8:  001000
16: 010000
32: 100000

and so on, so we need to check if the number only has one bit that is set, and that the number is not 0 (because zero is not a power of two).

We can count the number of set bits (which is another interview question!), and if the number of set bits is one, then the number is a power of two. A smarter way to do it would be bitwise ANDing of the number and the number-1, and then check that the result == 0.

For example, to check that 32 is a power of 2, convert 32 to binary to be 100000, convert 31 to binary to be 011111. Bitwise ANDing of those 2 numbers would obviously result in 0.

Advertisements

8 Responses to "Interview question: Check that an integer number is a power of two"

hmm… wouldn’t this be simpler ? šŸ˜‰

return n^n;

no it wouldn’t… my bad šŸ™‚

OR we can just.

public static boolean isPowerOfTwoMuchFaster(int N)
{
     return Integer.bitCount(N)==1;
}

Well, according to this, the Integer.bitCount(int n) function is implemented as follows:

public static int bitCount(int i) {
 i = i - ((i >>> 1) & 0x55555555);
 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 i = (i + (i >>> 4)) & 0x0f0f0f0f;
 i = i + (i >>> 8);
 i = i + (i >>> 16);
 return i & 0x3f;
 }

Which do you think is faster? Bitwise ANDing or counting the bits like the code above? šŸ™‚

//include math.h
void main()
{
int n,logval,powval;
printf(“Enter a number to find whether it is s power of 2\n”);
scanf(“%d”,&n);
logval=log(n)/log(2);
powval=pow(2,logval);
if(powval==n)
printf(“The number is a power of 2”);
else
printf(“The number is not a power of 2”);
getch();
}

The n&(n-1) trick is useful in certain circumstances (and nothing using math library functions will come close to its speed), but that is hardly a trick I would expect an interview candidate to know. The only way I would bring that up in an interview is to introduce it and then see if they can understand WHY it works.

Similar to biwise ANDing we could do a similar observation in C :
Let the integer x=16 in binary is:
00000000 00000000 00000000 00010000
Let the integer (-x)=(-16) in binary is:
11111111 11111111 11111111 11110001
(2’s complement)
So bitwise ANDing 16 and (-16) gives us 16 (the first number)
Only integers which are power of 2 behave like that.
Some C code:

if ( (x&(-x))==x) {…
}

Isn’t it more elegant to just do simple looping? I did the same in C, pretty self explanatory and it does consider 2 to the power zero as well:

@#include
int checkPower(int);
int main()
{
int num,val;
// to check if a number is a power of two
printf(“Enter Number: “);
scanf(“%d”, &num);
val = checkPower(num);
if(val == 1)
{
printf(“\nNumber is a power of two.\n”);
}
else
{
printf(“\nNumber is NOT a power of two.\n”);
}
return 0;
}
int checkPower(int num)
{
int i, j = 1;
for(i = 0; i <= num/2; i++)
{
if(j == num)
{
return 1;
break;
}
else
j*=2;
}
return 0;
}@

I did it like this because whatever language you use calling the Math library is always a bad idea and an overkill for such a simple problem. And using bitwise operator is anything but intuitive (at-least I feel it that way).

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

Ahmed Sabbour's Facebook profile
July 2008
S M T W T F S
« May   Oct »
 12345
6789101112
13141516171819
20212223242526
2728293031  

Tweets

RSS StackOverflow

Recently bookmarked

%d bloggers like this: