Sunday, May 3, 2009

Finding if a number is a power of 2 or not in Java?


How to find whether a number is a power of 2 or not in Java?

There can be many possible solutions to this problem, but probably the most efficient
remains to be the one which uses bit-level manipulation wisely.

We'll talk about only that solution here and since it involves bit-level manipulation of
binary sequences, so should you require a refresh, first go through this article - 2's complement, 1's complement, representation of negative numbers in Java >>

As is the case with many other solutions which use bits intelligently, this one is also very
compact. That's the beauty of bit-handling. Let's first see what the solution is and then try to understand it. It becomes very easy to understand once you get the binary sequence representations right.

Java method to check if the passed parameter is a power of 2 or not


public boolean checkIfItsPowerOf2(int n){

if( (n & -n) == n){

//passed parameter is a power of 2
return true;
}
else{
//not a power of 2
return false;
}
}



Illustration: We'll see the working of the method for a few sample numbers , say '1', '2', and '3' to understand it completely.

1: Binary representation of 1

0000 0000 0000 0000 0000 0000 0000 0001


-1:
Computation of binary representation of -1 by finding 2's complement of 1

1111 1111 1111 1111 1111 1111 1111 1110 (1's complement of '1')

0000 0000 0000 0000 0000 0000 0000 0001 (adding 1)

---------------------------------------

1111 1111 1111 1111 1111 1111 1111 1111 (-1 = 2's complement of 1)


1 & -1:
applying bit-wise AND (&) operator on 1 and -1

0000 0000 0000 0000 0000 0000 0000 0001

1111 1111 1111 1111 1111 1111 1111 1111

---------------------------------------

0000 0000 0000 0000 0000 0000 0000 0001
(1 & -1)

Thus we see that the test ((1 & -1) == 1) will return 'true'. This is correct as 1 is a
power of 2 (1 = 2^0).

2 & -2:
applying bit-wise AND on 2 and -2

0000 0000 0000 0000 0000 0000 0000 0010 (binary rep of 2)

1111 1111 1111 1111 1111 1111 1111 1110 (-2 = 2's comp of 2)

---------------------------------------

0000 0000 0000 0000 0000 0000 0000 0010
(2 & -2)

i.e., ((2 & -2) == 2) will return 'true' and that's correct as 2 is again a power of 2 (2 =
2^1)

3 & -3:
applying bit-wise AND on 3 and -3

0000 0000 0000 0000 0000 0000 0000 0011
(binary rep of 3)

1111 1111 1111 1111 1111 1111 1111 1101 (-3 = 2's comp of 3)

---------------------------------------

0000 0000 0000 0000 0000 0000 0000 0001
(3 & -3)

i.e., ((3 & -3) == 3) will return 'false' which is correct as 3 is not a power of 2.


Similarly we can see that
the condition ((n & -n) == n) will always return 'true' for a number which is a power of 2 and will always return 'false' otherwise.

A close observation will reveal that 2's complement of a number, which is a power of 2, will always maintain (at the same time it'll never maintain for a number which is not a power of 2) the significant bit sequence of the corresponding positive number and rest of the bits will be all 1s. Hence a bit-wise AND (&) operator applied on the two (n & -n) will always result into the number (n) itself (as it will maintain the significant bit-sequence and will set rest of the bits to 0s as 0 & 1 = 0). Understood? If not then go through the examples once again and think on the same lines. It should not be that difficult to visualize then.

Liked the article? Subscribe to this blog for regular updates. Wanna follow it to tell the world that you enjoy GeekExplains? Please find the 'Followers' widget in the rightmost sidebar.



Share/Save/Bookmark


5 comments:

rast said...

more compact would be

public boolean checkIfItsPowerOf2(int n)
{
return ( (n & -n) == n);
}

Geek said...

Well... yeah. BTW, the emphasis was on the condition statement and on the understanding of the underlying execution. But, thanks for your participation. Keep visiting/posting!

Alex said...

Great artice, every once in a while a refreshment of bitwise operations is in place :)

best blogger said...

How about this?

public boolean checkIfItsPowerOf2(int n)
{
return ( (n & (n-1)) == 0);
}

Geek said...

Yeah, looks good as the binary rep of a power of 2 (say 'n') will have all 0s except the MSB as '1' and hence subtracting one (n - 1) from it would effectively make all 0s as 1s and the only '1' as '0' with an overflow (which will eventually be discarded). Consequently, (n & (n - 1) ) would be '0' for all such 'n' (powers of 2).

TBH, this is my first impression which might require a review, but seems like it covers all possibilities. Moreover, we can probably find few more such conditions. Thanks for your participation. Keep it up!