0

I saw this efficiently written code at Leetcode.com 

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

This works awesomely fine but I am not able to figure out the working of single '&' in the code. Can some onetake efforts to explain how the code works?

And by the same logic what would eb the code to determine if an integer is power of 3?

fnaticRC ggwp
  • 955
  • 1
  • 11
  • 20
  • 1
    This question has already been answered at: http://stackoverflow.com/questions/4678333/n-n-1-what-does-this-expression-do – Hatward Feb 29 '16 at 01:32

5 Answers5

3

The & in Java is a bitwise and operator. It takes two integers and performs an and operation on each bit, producing an int where each bit is set to '1' if and only if that bit was '1' in both operands. The code uses the understanding that any power of two in binary is a '1' followed by some number of '0's. This means that subtracting one will change ALL the bits of the number. For any non power of two, there will be at least one nonzero digit after the first, so the first digit will remain the same. Since performing an AND on two different values always produces '0', ANDing the original number and itself minus one will produce 0 if and only if that number is a power of two. Because this is a trick with binary number specifically, it wouldn't work for finding powers of other bases.

Vincent
  • 484
  • 3
  • 9
3

The single & is a bitwise 'and' operator (as opposed to &&, which acts on booleans).

So when you use & on two integers, the result is the logical 'and' of their binary representations.

This code works because any power of 2 will be a 1 followed by some number of 0s in binary (eg, 4 is 100, 8 is 1000, etc). Any power of 2, less one, will just be all 1s (eg. 3 is 11, 7 is 111). So, if you take a power of 2, and bitwise and it with itself minus 1, you should just have 0. However, anything other than a power of 2 would give a non-zero answer.

Example:
1000 = 8
0111 = 7 (8-1), and '&'ing these gives
0000 = 0

However, if you had something like 6 (which isnt a power of 2):
110 = 6
101 = 5 (6-1), and '&'ing these gives
100 = 4 (which isnt equal to 0, so the code would return false).

I hope that makes it clear!

Jarrett Spiker
  • 361
  • 3
  • 13
1

To understand how this function works you need to understand how binary numbers are represented. If you don't I suggest reading a tutorial such as Learn Binary (the easy way).

So say we have a number, 8, and we want to find out if it's a power of two. Let's convert it to binary first: 1000. Now let's look at 8-1 = 7's binary form: 0111. The & operator is for binary AND. When we apply the AND operator to 8 and 7 we get:

 1000
 0111
&----
=0000

Every integer which is a power of 2 is a 1 followed by a non-negative amount of zeroes. When you subtract 1 from that number you will always get a 0 followed by a sequence of 1s. Since applying the AND operation to those two numbers will always give you 0, you can always verify if it's a power of 2. If the number is not a power of 2, when you subtract 1 from it it won't invert all of its digits and the AND test will produce a positive number (fail).

Andrew Jenkins
  • 1,590
  • 13
  • 16
0

Its an bitwise operator :

if we take 2 exponent 3 equals to 8, e.g 2³ = 2×2×2 = 8

now to calculate if 8 is a power of 2, it works like this:

n&(n-1) --> 8 AND (8-1) --> 1000 AND 0111 = 0000 thus it satisfies the condition --> (n&(n-1))==0

Ankur Gupta
  • 123
  • 1
  • 7
0

The single "&" performs a bitwise AND operation, meaning that in the result of A & B with A and B being integers only those bits will be set to 1 where both A and B have a 1.

For example, lets look a the number 16:

16 & (16 - 1) =

00010000 &
00001111 =
00000000

This works for powers of two because any power of two minus one will have all lower bits set, or in other words n bits can express n different values including zero, therefore (2^n)-1 is the highest value that can be expressed in n bits when they're all set.

I hope this helps.

Powers of three are a bit more problematic as our computers don't use ternary numbers. Basically a power of three is any ternary number that only has one digit different from zero and where that digit is a "1" just like in any other number system. From the top of my head, I can't come up with anything more elegant than repeatedly doing modulo 3 until you reach one as a division result (in which case you'd have a power of three) or a nonzero modulo result (which would mean it's not a power of three). Maybe this can help as well: http://www.tutorialspoint.com/computer_logical_organization/number_system_conversion.htm

Michael Langowski
  • 348
  • 2
  • 10