If we know beforehand that i
must be something like 10...0
, it's not hard to imagine.
But how to mathematically prove that i & (i - 1) == 0
is sufficient to say i is the power of 2, at lease for positive integer?
You can find some explanations of this expression in How to check if a number is a power of 2 But I don't think an explanation is congruent with a mathematical proof.
Technically, the statement is not correct, in case of i
is a signed int
it should be
i & (i - 1) == 0
if and only ifi
is a power of2
or0
The proof is easy:
If i
is power of 2
, then it can be represented as 1000...000
(binary)
and we have
1000...000 - i is a power of 2
0111...111 - i - 1
----------
0000...000 = 0
If i
is 0
then we have
0 - i = 0
111...111 -1 (2 complement)
---------
0
If i
is not a power of 2
or 0
then it has at least two bits set, let's take leftmost and rightmost of them:
i = 1?..?10...0
^ ^ rightmost 1
leftmost 1
and we have the leftmost bit ever set:
1?..?10...0 - i
1?..?01...1 - i - 1
-----------
1?..?00...0 > 0