Hacker News new | past | comments | ask | show | jobs | submit login

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




I 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! :)


I 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.


And then we have a zig-zag bijection for too many serialization formats.


Why too many? It's a neat trick.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: