Consider the equation which enables us to find the largest power of 2 that divides . One can prove this relatively easily from the definitions:
That is, if we state that for some arbitrary , we then find that , which is precisely what we need to subtract from to remove the rightmost/trailing . However, I don't find this insightful. So I'm going to spend some time dwelling on -adics, to find a more intuitive way to think about this.
§ 2-adics and negative numbers
In the 2-adic system, we have that:
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 , we start with the "lower" number and then add to it, giving us:
Which once again agrees with the 2's complement definition.
§ for powers of 2:
If we now think strictly about powers of 2, we know that, for example, while . Hence, . This will hold for any power of 2, so our claim that 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 ~= b0000000Now, 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= 255If 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= -1So, the advantage is that our operations don't care about whether the number is signed/unsigned.