Two's complement: why the name "two"?

Question

I know unsigned, two's complement, ones' complement, sign magnitude, and the difference between these. But what I'm curious about is:

1. Why is it called two's (or ones') complement? Is there a more general N's complement?
2. In which way did these geniuses deduce such a natural way to represent negative numbers?

Answer 1

From Donald Knuth's "The Art of Computer Programming" (Volume 2, 3rd edition, pages 203-204):

A two's complement number is complemented with respect to a single power of 2, while a ones' complement number is complemented with respect to a long sequence of 1s.

As an example, we take the four-bit number 0110, decimal 6, and calculate the binary representation of its negative value, -6. We'll use both methods: two's and ones' complement.

Two's complement

We use "a single power of 2", namely 2⁴ (1 0000), to get the two's complement of our example number 0110:

  1 0000
-   0110
--------
    1010

The "two" in "two's complement" refers to the base of the number (2⁴) from which we subtract our positive number.

See also Wikipedia's Two's complement.

Ones' complement

The "long sequence of 1s" is four ones in our example since our input number 0110 has four bits:

    1111
-   0110
--------
    1001

The "ones" in "ones' complement" refers to the digits of the number (1111) from which we subtract our positive number.

---

I've created this page if you want to play around with different ways of representing negative numbers in binary.

Answer 2

Two's complement came about when someone realized that 'going negative' by subtracting 1 from 0 and letting the bits rollunder actually made signed arithmetic simpler because no special checks have to be done to check if the number is negative or not. Other solutions give you a discontinuity between -1 and 0. The only oddity with two's complement is that you get one more negative number in your range than you have positive numbers. But, then, other solutions give you strange things like +0 and -0.

According to Wikipedia, the name itself comes from mathematics and is based on ways of making subtraction simpler when you have limited number places. The system is actually a "radix complement" and since binary is base two, this becomes "two's complement". And it turns out that "ones' complement" is named for the "diminished radix complement", which is the radix minus one (in binary, that's a number consisting entirely of ones). If you look at this for decimal, the meanings behind the names make more sense.

Method of Complements (Wikipedia)

Answer 3

I've been doing a lot of reading on this lately. I could be wrong, but I think I've got it...

The basic idea of a complement is straightforward: it's the remaining difference between one digit and another digit. For example, in our regular decimal notation, where we only have ten digits ranging from 0 to 9, we know that the difference between 9 and 3 is 6, so we can say that "the nines' complement of 3 is 6".

From there on out, there's something that I find gets easily confused, with very little help online: how we choose to use these complements to achieve subtraction or negative value representation is up to us! There are multiple methods, with two majorly accepted methods that both work, but with different pros and cons. The whole point of the complements is to be used in these methods, but "nine's complement" itself is not a subtraction or negative sign representation method, it's just the difference between nine and another digit.

The old-style "nines' complement" way of flipping a decimal number (nines' complement can also be called the "diminished radix complement" in the context of decimal, because we needed to find a complicated fancy way to say it's one less than ten) to perform addition of a negative value worked fine, but it gave two different values for 0 (+0 and -0), which was an expensive waste of memory on computing machines, and it also required additional tools and steps for carrying values, which added time or resource.

Later, someone realized that if you took the nines' complement and added 1 afterwards, and then dropped any carrying values beyond the most significant digit, you could also achieve negative value representation or subtraction, while only having one 0 value, and not needing to perform any carry-over at the end. (The only downside was that your distribution of values was uneven across negative and positive numbers.) Because the operation involved taking nines' complement and adding one to it, we called it "ten's complement" as a kind of shorthand. Notice the different placement of the apostrophe in the name. We have two different calculations that use the same name. The method "ten's complement" is not the same as "tens' complement". The former uses the second method I mentioned, while the latter uses the first (older) method I mentioned.

Then, to make the names simpler later, we said, "Hey, we call it ten's complement and it flips a base 10 number (decimal representation), so when we're using it we should just call it the "radix complement". And when we use nines' complement in base 10 we should just call it the "diminished radix complement". Again, this is confusing because we're reversing the way it actually happened in our terminology... ten's complement was actually named because it was "nines' complement plus one", but now we're calling it "ten's complement diminished" basically.

And then the same thing applies with ones' complement and two's complement for binary.

Answer 4

In the decimal numbering system, the radix is ten:

• radix complement is called as ten's complement
• diminished radix complement is called as nines' complement

In the binary numbering system, the radix is two:

• radix complement is called as two's complement
• diminished radix complement is called as ones' complement

Source: https://en.wikipedia.org/wiki/Method_of_complements

Answer 5

You can do the same thing in other bases. With decimal, you would have 9's complement, where each digit X is replaced by 9-X, and the 10's complement of a number is the 9's complement plus one. You can then subtract by adding the 10's complement, assuming a fixed number of digits.

An example - in a 4 digit system, given the subtraction

 0846
-0573
=0273

First find the 9's complement of 573, which is 9-0 9-5 9-7 9-3 or 9426
the 10's complement of 573 is 9426+1, or 9427
Now add the 10's complement and throw away anything that carries out of 4 digits

   0846
  +9427      .. 10's complement of 573
= 10273      .. toss the 'overflow' digit
=  0273      .. same answer

Obviously that's a simple example. But the analogy carries. Interestingly the most-negative value in 4-digit 10's complement? 5000!

As for the etymology, I'd speculate that the term 1's complement is a complement in the same sense as a complementary angle from geometry is 90 degrees minus the angle - i.e., it's the part left over when you subtract the given from some standard value. Not sure how "2's" complement makes sense, though.