I had this in part of the code. Could anyone explain how i & (i ^ (i - 1)) could be reduced to i & (-i)?
Asked
Active
Viewed 955 times
1
JASON
- 7,371
- 9
- 27
- 40
-
Because of [two's complement](http://en.wikipedia.org/wiki/Two's_complement). – Blorgbeard Jul 16 '14 at 05:20
-
Is it? Let `i = 1`. Then `i ^ (i-1) = 1 ^ (1-1) = 1 ^ 0 = 1` and this does not equal to `-i = -1` – Kousha Jul 16 '14 at 05:20
-
2What's your language? Does `^` mean "to the power of" (`2 ^ 3 = 2 * 2 * 2 = 8`) or "xor" (`2 ^ 3 = 10b ^ 11b = 01b = 1`)? – sisve Jul 16 '14 at 05:21
-
@Kousha hum, you're right. Retracted. – Blorgbeard Jul 16 '14 at 05:22
1 Answers
4
i ^ (i - 1) makes all bits after the last 1 bit of i becomes 1.
For example if i has a binary representation as abc...de10...0 then i - 1 will be abc...de01...1 in binary (See Why does (x-1) toggle all the bits from the rightmost set bit of x?). The part before the last 1 bit is not changed when subtracting 1 from i, so xoring with each other returns 0 in that part, while the remaining will be 1 because of the difference in i and i - 1. After that i & (i ^ (i - 1)) will get the last 1 bit of i
-i will inverse all bits up to the last 1 bit of i because in two's complement -i == ~i + 1, and i & (-i) results the same like the above
For example:
20 = 0001 0100
19 = 0001 0011
20 ^ 19 = 0000 0111 = 7
20 & 7 = 0000 0100
-20 = 1110 1100
20 & -20 = 0000 0100
See also
phuclv
- 37,963
- 15
- 156
- 475