23/10/2017

[Java] Test if a number is a power of two

Last trick of the day: check whether a number is a power of 2.

The breakdown is:

- 0 is never a power of anything
- a power of 2 in binary representation will always have only one bit set
- we can find the first set LSB in number and XOR it with the number itself
- if the number was a power of two the XOR will cancel out all equal bits (only one) and we are left with a 0

Which leads to our code:

 public static boolean isPower2(long n){  
  if(n == 0) return false;  
  return (n ^ getLowestSetBit(n)) == 0;  
 }  


You can check more bit magic on my Gist along with some test cases.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.