6
$\begingroup$

I'm pretty confused so I hope I don't mix up the different terms here.

  1. The two's complement representation of decimal 0 is simply 000

  2. The two's complement of 000 is 111

    • I imagine that complementing a number is equivalent to flipping bits in binary

  3. The nine's complement of 000 is 999

    • This is what confuses me. Are two's complement and nine's complement similar (except for the base change obviously)?
    • If they are, then I'd expect the nine's complement of 000 to be 888 because 8 is the biggest digit in radix 9 and therefore the complement operation would assign the highest digit (8) to the lowest value input (0) [I imagine a folding from the center]

Obviously this is totally wrong but I'm not sure which part I've misunderstood.

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
32
$\begingroup$

You are very confused due what is simply poor terminology, to be honest. Both your statements 2 and 3 are false due to the same misunderstanding.

For each base $b$ there are two mainstream variants of the 'complement', the radix complement and the diminished radix complement.

The two most common bases in computer science are base $2$ and base $10$. Confusingly, the definitions usually used are:

  • one's complement: the diminished radix complement of base $2$
  • two's complement: the radix complement of base $2$
  • nine's complement: the diminished radix complement of base $10$ (not $9$!)
  • ten's complement: the radix complement of base $10$.
Improve this answer
$\endgroup$
9
  • $\begingroup$ oh wow. So there is no term for complement in radix-9 then? $\endgroup$
    – sprajagopal
    Commented Feb 2, 2021 at 20:50
  • 5
    $\begingroup$ @sprajagopal Are you sure you're working in base $9$ and not that whoever you're communicating with refers to nine's complement as in my third definition? $\endgroup$
    – orlp
    Commented Feb 2, 2021 at 20:52
  • 2
    $\begingroup$ @sprajagopal As you just did, ideally with an exact definition. It's really not a common thing at all. $\endgroup$
    – orlp
    Commented Feb 2, 2021 at 20:55
  • 3
    $\begingroup$ @sprajagopal Technically, the correct names for the concepts here are ones' complement and nines' complement, but two's complement and ten's complement. So in a sense, what you are referring to should indeed be called nine's complement, but the placement of the apostrophe is too subtle to differentiate names with. $\endgroup$
    – L. F.
    Commented Feb 3, 2021 at 9:29
  • 1
    $\begingroup$ @Orlp At the very least Knuth has an - imho - perfectly logical argument for the apostrophe positioning (haven't looked up the Wiki, but there's a discussion about this in TAoCP) which I don't think exists for the apostrophe positioning you're listing here. That lot's of people ignore it, is what makes it "technically correct" and not simply "correct" ;-) (And given that wikipedia also seems to be using the terminology that probably does make it widely accepted no?) $\endgroup$
    – Voo
    Commented Feb 4, 2021 at 8:54
12
$\begingroup$

The two's complement of 000 is 000. It is formed by complementing all bits and adding 1 to the result. The one's complement of 000 is indeed 111, but it is not used in computing.

The ten's complement of 000 is 000. It is formed by complementing all digits and adding 1 to the result. The nine's complement of 000 is indeed 999.

I suggest thoroughly reading the Wikipedia article on Two's complement.

What is behind two's complement?

The goal of two's complement is to come up with a negation operation $N(x)$ so that $x - y = x + N(y)$. The idea is that if all integers have width $w$, then all computation is implicitly done modulo $2^w$, and so $x - y = x + 2^w - y$. Now $2^w - y = (2^w-1-y)+1$. The binary expansion of $2^w-1$ consists of $w$ many $1$s, and so $2^w-1-y$ is the same as complementing $y$. That's why we compute the two's complement by complementing all bits and adding $1$.

Ten's complement works in the same way: $x - y = x + 10^w - y$, and $10^w - y = (10^w-1-y)+1$. Now $10^w-1$ consists of $w$ many $9$'s, and so $10^w-1-y$ corresponds to complementing all digits. Therefore ten's complement is formed by complementing all digits and adding $1$.

Improve this answer
$\endgroup$
4
  • 5
    $\begingroup$ ones complement is used in computing, just not used for arithmetic (any more) in C (and languages with C like expressions) the one's complement operator is ~ $\endgroup$
    – Jasen
    Commented Feb 3, 2021 at 10:41
  • 1
    $\begingroup$ @Jasen: C doesn't promise that -x computes the two's complement of x. It promises that x + (-x) == 0 when there is no overflow. If the underlying hardware uses one's complement or sign-magnitude for integer arithmetic (which is rare if not unheard of these days), then C will use that instead of trying to force everything into a format which the architecture was not designed to support. This means that it is not strictly portable to try and mix bitwise operations with signed integers, unless you reason very carefully about how they are required to behave. For example, ~0 may trap. $\endgroup$
    – Kevin
    Commented Feb 3, 2021 at 20:14
  • $\begingroup$ @Kevin: Fortunately, 2's complement uses the same binary operations as unsigned, so -(unsigned)x == 0U - x, which is guaranteed to be the same as ~(unsigned)x+1U. (With overflow being well-defined to wrap). (for future readers, see also How to prove that the C statement -x, ~x+1, and ~(x-1) yield the same results? and en.wikipedia.org/wiki/Two%27s_complement. Those identities are handy sometimes, but they're not always easier than subtraction, and not necessarily how CPU actually do them. For example, x86's neg sets FLAGS like SUB for 0-x $\endgroup$
    – Peter Cordes
    Commented Feb 3, 2021 at 21:22
  • $\begingroup$ (I'm assuming x was int, and that unsigned is at least as wide as int; C integer promotion rules can be tricky but signed integer conversion to unsigned by modulo-reduction into the value-range is well-defined.) $\endgroup$
    – Peter Cordes
    Commented Feb 3, 2021 at 21:25
1
$\begingroup$

The position of the apostrophe matters.

If the number is used in the singular possessive form, as with "two's complement", one forms the complement by subtracting from the value one would get if one multiplied the base by what would, in unsigned form, be the place value of the most significant digit. So to take an eight-bit two's-complement of a number, because the most significant bit of an unsigned 8-bit number would be 128, one takes the quantity (two times 128) and subtracts the number from it.

If the number is used in the plural possessive form, as with "ones' complement" or "nines' complement", one subtracts from the value one would get if one replaced all of the digits with the indicated value (which should be one smaller than the base).

Thus, twos'-complement form (as distinct from two's-complement form) would be a means of representing base 3 values where an 8-bit negative number would be formed by subtracting the positive value from 22222222.

Although it's not uncommon for people to write "one's complement" when they really mean "ones' complement", or "twos' complement" when they mean "two's complement", putting the apostrophe in the write place and recognizing its distinction will make clear the distinction between the two general kinds of complement.

Improve this answer
$\endgroup$
2
  • $\begingroup$ hi, coult you add an example for nine's vs nines' complement? $\endgroup$
    – sprajagopal
    Commented Feb 5, 2021 at 5:51
  • $\begingroup$ The value -1 in nines' complement would be 9998 (subtract 0001 from 9999), but in nine's complement it would be 8888 (subtract 0001 from 9x1000). $\endgroup$
    – supercat
    Commented Feb 5, 2021 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.