two's complement, why the name "two"_问答_开发者

i know unsigned,two's complement, ones' complem开发者_JAVA百科ent and sign magnitude, and the difference between these, but what i'm curious about is:

why it's called two's(or ones') complement, so is there a more generalize N's complement?
in which way did these genius deduce such a natural way to represent negative numbers?

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 "one's complement" is named for the "diminished radix complement", which is the radix minus one. If you look at this for decimal, the meanings behind the names makes more sense.

Method of Complements (Wikipedia)

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.

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

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.