3 ms·
Or briefly, copied from my StackOverflow answer[1]: v 000...00010100 ~v 111...11101011 (not used directly, all bits opposite) -v 111...11101100 (-
by o11c 2y ago
Or briefly, copied from my StackOverflow answer[1]:
v 000...00010100
~v 111...11101011 (not used directly, all bits opposite)
-v 111...11101100 (-v == ~v + 1; this causes all low 1 bits to overflow and carry)
v&-v 000...00000100 (has a single 1 bit, from the carry)
The linked article is wrong in only mentioning 2 signed integer representations. Old versions of C allowed 3 representations for integers, floats use one of those (sign-magnitude, also used widedly by bignum libraries) and one other (offset binary), and base negative-2 is also possible in theory (not sure if practical for anything), for a total of 5.
[1]: https://stackoverflow.com/a/63552117/1405588 https://stackoverflow.com/a/63552117/1405588
- arun-mani-j 2y agoI tried to explain only one's complement and two's complement because they were only relevant to the explanation. TIL we have 5 such representations! :)
- unconed 2y agoI find this a pretty confusing explanation because the actual mechanism is buried in the middle and you can't understand the first diagram without it. The goal is to produce the number `0...010...0` with the same number of trailing zeroes as x. If you flip all the bits in x, then `...10...0` turns into `...01...1`. Adding one cascades the tail into `...10...0`. You can do this entirely in unsigned math and you don't need to drag two's complement into it. The fact that it corresponds to `x & -x` is a curiosity, and then you have to explain why it works for e.g. negative numbers, where it counts trailing ones instead but still produces a positive. There are plenty of other tricks like this, e.g. `x & (x - 1) == 0` tells you if a (non-zero) x is a power of two, but it doesn't work for negatives.
- lifthrasiir 2y agoAnd then we have a zig-zag bijection for too many serialization formats.
- IshKebab 2y agoWhy too many? It's a neat trick.