§ p-adics, 2's complement, intuition for bit fiddling

Consider the equation x&(x)x \& (-x) which enables us to find the largest power of 2 that divides xx. One can prove this relatively easily from the definitions:
a=x10ra=¬a+1=x01r+1=x10ra&(a)=a&(¬a+1)=(x10r)&(x10r)=0α10r=2r \begin{aligned} &a = \langle x 1 0^r \rangle \\ &-a = \lnot a + 1 = x01^r + 1 = \overline{x}10^r \\ &a \& (-a) = a \& (\lnot a + 1) = (x 10^r) \& (\overline{x}10^r) = 0^{|\alpha|}10^r = 2^r \end{aligned}
That is, if we state that a=x10ra = \langle x 1 0^r \rangle for some arbitrary rr, we then find that a&(a)=2r=10ra \& (-a) = 2^r = \langle 1 0^r \rangle, which is precisely what we need to subtract from aa to remove the rightmost/trailing 11. However, I don't find this insightful. So I'm going to spend some time dwelling on 22-adics, to find a more intuitive way to think about this.

§ 2-adics and negative numbers

In the 2-adic system, we have that:
1=11112=1+1=1111+1111=11104=2+2=1110+1110=11008=2+2=1100+1100=1000 \begin{aligned} &-1 = \dots 1 1 1 1 \\ &-2 = -1 + -1 = \dots 1 1 1 1 + \dots 1 1 1 1 = \dots 1 1 1 0 \\ &-4 = -2 + -2 = \dots 1 1 1 0 + \dots 1 1 1 0 = \dots 1 1 0 0 \\ &-8 = -2 + -2 = \dots 1 1 0 0 + \dots 1 1 0 0 = \dots 1 0 0 0 \\ \end{aligned}
Of course, these agree with the 2's complement representation, because the 2's complement representation simply truncates the 2-adic representation. At any rate, the point of interest is that if we now want to know how to write 3-3, we start with the "lower" number 4-4 and then add 11 to it, giving us:
3=4+1=1100+0001=1101 -3 = -4 + 1 = \dots 1 1 0 0 + \dots 0 0 0 1 = \dots 1 1 0 1
Which once again agrees with the 2's complement definition.

§ x&(x)x \& (-x) for powers of 2:

If we now think strictly about powers of 2, we know that, for example, 8=001008 = \langle \dots 0 0 1 0 0 \rangle while 8=11100-8 = \langle \dots 1 1 1 0 0 \rangle. Hence, x&(x)=00100x \& (-x) = \langle 0 0 1 0 0 \rangle. This will hold for any power of 2, so our claim that x&(x)x \& (-x) gives us the location of the LSB will work for any power of 2.

§ Alternative explanation for 2's complement

Start with the fact that we choose a single representation for zero:
0 ~= b0000000
Now, when we subtract 1, ask "are we in signed world or unsigned world"? If in signed world, we want the answer to be -1. If in unsigned world we want the answer to be 255.
0 - 1 
= b0000000 - b00000001
= b11111111 
=unsigned= 255
If we wanted to interpret the answer as signed, then we are free to do so. This automatically tell us that
0 - 1
=unsigned= b11111111
=signed= -1
So, the advantage is that our operations don't care about whether the number is signed/unsigned.