Explain x & (-x)

Problem

What

x & (-x) returns the rightmost 1 in binary representation of x.

-x is the two’s complement of x. -x will be equal to one’s complement of x plus 1.

Therefore (-x) will have all the bits flipped that are on the left of the rightmost 1 in x. So x & (-x) will return rightmost 1.

x = 10 = 0b1010
(-x) = -10 = 0b0110
x & (-x) = 0b1010 & 0110 = 0010

Applications

[Single Number 3 - All elements except two occur twice](single-number-3-all-elements-except-two-occur-twice)