Handy Java Snippet: Check if number is power of two

Posted on January 1, 2012

I recently had a java assignment involving calculations on an array, where the objects where located at a location index which was the power of two (what an incoherent sentence…). In other word, to find the objects at index: 1, 2, 4, 8, 16…

I wrote a simple function in Java to determine if an integer is a power of two:

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

It works on the principle that numbers 2^n only contain one “1” when represented in binary, see the following numbers:
2 = 10
4 = 100
8 = 1000 It first checks that the number isn’t equal to 0 (since 2^n can never be zero), whereafter it uses some binary trickery. Take a number n (for example 4), this can be represented in binary as 100. Then take the number n-1 (4-1=3). Using binary OR, we get something that looks like this:

100  
011  
----  
000  

Which is equal to 0.
Now if take a number n that isn’t a power of two (e.g. 6), we get:

110  
101  
----  
100  

Which isn’t equal to 0.

Therefore is a number n (binary) OR n-1 is equal to 0, it is a power of two.
There you have it!

blog comments powered by Disqus