While working on a problem on Hackerank I saw this code in the code that was given to us:
(num&num-1)==0 and my question is why does this tell me whether or not the variable num is a power of 2?
I noticed the code works perfectly. What I believe is happening is the bitwise & operator is used to convert the variable num to binary and then 1 is subtracted from it and I also believe the 1 is being converted to binary? I am not quite sure exactly what is happening but with numbers like 8 the result is always equal to 0 and with numbers like 9 it isn't. Can someone explain what is happening under the hood that makes this code work?
If a power of two is translated into binary representation, it contains exactly one 1 and 0s on the remaining position, e.g. (in 8-bit representation):
2^4 = 0001 0000
Subtracting one from such a number sets the 1-bit to zero, and all bits behind it to one:
2^4 - 1 = 0000 1111
That means, for powers of two, that there is no bit set in both cases, and x & (x - 1) is zero.
If a number other than a power of two is translated into binary representation, it contains at least two 1s, e.g. (in 8-bit representation):
12 = 0000 1100
Subtracting one from this number sets the least significant 1 to 0, and all 0s behind it to 1s:
12 - 1 = 0000 1011
But since this number contains at least two bits, there is still at least one bit that hasn't been modified. So, in x & (x - 1), at least one bit is set, and the number is not equal to zero.
This doesn't work in one case, though, as it will detect 0 as a power of two (since 0 & -1 == 0 is true).