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

Consider the equation $x \& (-x)$ which enables us to find the largest power of 2 that divides $x$. One can prove this relatively easily from the definitions:
\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 = \langle x 1 0^r \rangle$ for some arbitrary $r$, we then find that $a \& (-a) = 2^r = \langle 1 0^r \rangle$, which is precisely what we need to subtract from $a$ to remove the rightmost/trailing $1$. However, I don't find this insightful. So I'm going to spend some time dwelling on $2$-adics, to find a more intuitive way to think about this.

#### § 2-adics and negative numbers

In the 2-adic system, we have that:
\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$, we start with the "lower" number $-4$ and then add $1$ to it, giving us:
$-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)$ for powers of 2:

If we now think strictly about powers of 2, we know that, for example, $8 = \langle \dots 0 0 1 0 0 \rangle$ while $-8 = \langle \dots 1 1 1 0 0 \rangle$. Hence, $x \& (-x) = \langle 0 0 1 0 0 \rangle$. This will hold for any power of 2, so our claim that $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.