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

Posted July 24, 2008

on:- In: Code | Java
**8**Comments

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; } } [/sourcecode] 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.

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

OR we can just.

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

//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).

1 | sileryti

November 24, 2009 at 8:43 pm

hmm… wouldn’t this be simpler ? 😉

return n^n;

sileryti

November 24, 2009 at 8:44 pm

no it wouldn’t… my bad 🙂