- x is 2^b*k for some odd k < 2^(n-b)
- -x is 2^n - 2^b*k = 2^b*(2^(n-b)-k)
- k is odd by definition, and (2^(n-b)-k) + k = 0 (mod 2^(n-b)). This means that the LSB must be 1 in both operands, which results in a carry out, and in the following ith bits we have that the sum is 0 mod 2^i if and only if the ith bits of (2^(n-b)-k) and k are distinct. Thus x & -x = 2^b.
I’m not trying to dunk on you, but I can’t help to note that the denseness of math is too much for an idiot like me.
Erm no. -x is - 2^b * k and it's the "Two's complement" notation which is 2^n - 2 * b * k
This is because the way we generate the "Two's complement" number. Given A in binary representation, let's call A1 the number you get by flipping every bit in A also called one's complement. Observe how every bit in A+A1 is 1 because if the bit was 0 in A then the bit is 1 in A1 and vica versa. So then that's 2^N-1. Two's complement is created by adding 1 to A1 so then A + A1 is 2^N or A1 = 2^N-A. But you do need to prove this before you can use it.
Therefore x & -x works only in two's complement, and it's fair to assume it as the parent comment did.