# My (mostly technical) blog

## Posts Tagged ‘Java’

### 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

### Tweets

Error: Twitter did not respond. Please wait a few minutes and refresh this page.

Advertisements