§ 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=⟨x10r⟩−a=¬a+1=x01r+1=x‾10ra&(−a)=a&(¬a+1)=(x10r)&(x‾10r)=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=⟨x10r⟩a = \langle x 1 0^r \rangle for some arbitrary rr, we then find that a&(−a)=2r=⟨10r⟩a \& (-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=…1111−2=−1+−1=…1111+…1111=…1110−4=−2+−2=…1110+…1110=…1100−8=−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=⟨…00100⟩8 = \langle \dots 0 0 1 0 0 \rangle while −8=⟨…11100⟩-8 = \langle \dots 1 1 1 0 0 \rangle. Hence, x&(−x)=⟨00100⟩x \& (-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.