### -synx-'s blog

By -synx-, history, 5 years ago,

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?

• +1

 » 5 years ago, # |   +6 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 = aWe 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 1If we apply one-complement to i we get ac0bc, and adding 1 we get ac1bNow, i &  - i = a1b & ac1b = z1b where z is a sequence of zeros with the same length as ai - (i &  - i) = a1b - z1b = aSo, i - (i &  - i) = i & (i - 1) = a, (that is, turn off the LSB).Hope this helps :)
•  » » 5 years ago, # ^ |   +3 Thanks, sure it helps. :)