[hadjian]

Had the two‘s complement journey a couple of month ago:

http://www.hadjian.com/articles/20221229_twos_complement.htm...

If you can answer why two‘s complement has an apostrophe and ones complement doesn’t, you understood it ;-)

[nayuki]

I think this is the reason: When you negate a number in two's complement, you take (a single) two to the power of the bit width and then subtract the number. For example, negating 0011b (4 bits) means taking 10000b and subtracting 0011b, giving you 1101b.

When you negate a number in ones' complement, you take as many ones (plural) as the bit width and then subtract the number. For example, negating 0011b (4 bits) means taking 1111b and subtracting 0011b, giving you 1100b.

[hadjian]

Yes, that’s basically the algorithm, but it took me a while to understand why it works.

The subtraction from base^n is the radix complement, the subtraction from base^n-1 is the diminished radix complement.

Example base 9: with a fixed number width of say four, e.g. 4781, you take the radix complement by subtracting from 9^4, which is 10000 in base 9. But to take the complement, you again need subtractions with nasty borrows. But you wanted to reuse your adder and not have a subtractor to take the complement.

So you observe, that the formula is the same as 10000-1-4781+1 (subtract one and add it back). Subtracting the one gives you 8888. this solves your problem, because every digit is the highest one in its base, so you will never have to borrow. This is the diminished radix complement, to which you add one to get back to the radix complement.

Back to base 2: you take the diminished radix complement to avoid borrows (which is conveniently just a bit flip in base 2) and add one to arrive at the radix complement. Thus the familiar algorithm: „flip all bits and add one for two‘s complement“.

I hope I did a better job explaining it in my post linked above.