3 ms·
An alternative, more arithmetic, argument: - 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)
by pbsd 2y ago
An alternative, more arithmetic, argument:
- 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.
- Droobfest 2y agoThis immediately reads like gobbledygook to me, while the parent is easy to follow. 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.
- schoen 2y agoIt might be nicer with exponents rendered as superscripts, because it could make it more apparent how the exponents are being used.
- chx 2y ago> -x is 2^n - 2^b * k 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.
- bonzini 2y agoThe point of two's complement is that it's the same as modulo-2^n arithmetic. In two's complement -x is defined such that x + -x = 0 (mod 2^n); and because x + ~x = 2^n - 1 (mod 2^n), then -x = ~x + 1. Therefore x & -x works only in two's complement, and it's fair to assume it as the parent comment did.