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.