Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

-synx-'s blog

Proving this Bitwise Property
By -synx-, history, 10 years ago, In English

How can we prove that
i - (i& - i) = i&(i - 1)
mathematically?
Obviously, we can realise that i&(i - 1) unsets the LSB, and (i& - i) gives the LSB (subtracting which, also unsets the LSB). Is there a more concrete backing?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

First, the integer i can be expressed in binary as a1b where

a =  sequence of 0's and 1's.

1 =  the LSB (least-significant bit)

b =  sequence of 0's (possibly empty)

Then i - 1 can be expressed as a0bc where bc is the complement of b (a sequence of 1's, possibly empty)

Following this binary representation i & (i - 1) = a1b & a0bc = a

We can apply the same principle to represent i - (i& - i):

 - i = ac1b, why? Because  - i is the two-complement of i, that is flipping all the bits (one-complement of i) and adding 1

If we apply one-complement to i we get ac0bc, and adding 1 we get ac1b

Now, i &  - i = a1b & ac1b = z1b where z is a sequence of zeros with the same length as a

i - (i &  - i) = a1b - z1b = a

So, i - (i &  - i) = i & (i - 1) = a, (that is, turn off the LSB).

Hope this helps :)

→ Reply