Handy Java Snippet: Check if number is power of two
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!