algorithmmath

How to prove that "i & (i - 1) == 0" means "i is the power of 2"


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.


Solution

  • Technically, the statement is not correct, in case of i is a signed int it should be

    i & (i - 1) == 0 if and only if i is a power of 2 or 0

    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