29

Many early computers use ones' complement to represent some kind of signed integer. Examples include the PDP-1, the CDC-6600, and many other popular computers.

The C standard is obviously written with ones' complement machine in mind; for example, it specifies that a signed integer may hold values −32767 to +32767.

But I find that modern day examples of computers that use ones' complement rather hard to come across. I think it's safe to assume that anything you've got that runs a computer program and has signed integers of some kind uses two's complement. So what is the reason for the decline in popularity for ones complement architectures?

Improve this question
16
  • 3
    The C Standard definition also permits sign/magnitude representation; I don't know which (if any) popular systems use(d) that.
    – Toby Speight
    Commented Jul 25, 2018 at 17:17
  • 5
    The fact that you can have a positive or negative zero would lead to no end of confusion. I remember doing this as a student - I had to write out the bit pattern before I figured it out.
    – cup
    Commented Jul 25, 2018 at 20:28
  • 11
    Because all too often one's complement turns into one's evil twin?
    – Tommy
    Commented Jul 25, 2018 at 20:53
  • 4
    @Ray all I wrote was “IEEE 754 uses sign/magnitude”. I wasn’t suggesting anything about whether ones’ or two’s complements would be appropriate.
    – Stephen Kitt
    Commented Jul 25, 2018 at 22:39
  • 18
    "The C standard is obviously written with one's complement machine in mind; for example, it specifies that a signed integer may hold values -32767 to +32767." In some respects, yes it was written with 1s complement in mind. However, not specifically. In particular, the C standard was written to be as implementation agnostic as possible. The above range allows for 2s complement, 1s complement and sign/magnitude.
    – dgnuff
    Commented Jul 25, 2018 at 23:24

6 Answers 6

Reset to default
21

Two's complement is generally simpler to implement in hardware than ones' complement, except for one thing: if one wants a "live" readout of register values using one set of lights for positive numbers and one set for negative numbers (blanking whichever set isn't appropriate) that can be accommodated very cheaply and easy with ones'-complement using one small transistor per bulb and a pair of large transistors to act as master enables for the positive and negative lights. If the states of every register exist as continuously-accessible signals, adding a live readout that shows things in signed format is nice and easy. If a system were to use two's-complement, the values displayed for negative numbers would be off by one, and a significant amount of extra circuitry would be needed for each register's readout to correct it.

In the days when computers had register readouts, using ones'-complement could make the registers easier to read. Two's-complement integer math is better in just about every other way, however.

Incidentally, ones'-complement would make sense with floating-point math if treats 0.1111111111111.... with an unending string of ones as equivalent to 1.00000000. Viewed in that light, the sign bit controls the state not just of all otherwise-unspecified bits to the left of the number, but also the state of bits to the right. ~0 would thus equal ....11111111.0 + 0.11111111....., i.e. -1+1, i.e. zero. Two's-complement representations are asymmetric, but with integer math the asymmetry is consistently one unit. In floating-point math, the two's-complement asymmetry would vary with scale, which is a bit more awkward. Symmetry is more useful with floating point than with integer math, and thus ones'-complement would be advantageous there compared with two's-complement. Sign magnitude also works (and is what many systems actually use) but ones'-complement could work essentially as well.

Improve this answer
7
  • The CDC6600 (and presumably the 7600, which was designed to be at least mostly backwards compatible, however I haven't found any documentation on its data formats in a brief search) used one's complement floating point (and integers too, but it was designed primarily as a floating point machine for handling scientific computation, so the integer support was mostly an afterthought, I suspect). By the time he designed the Cray-1, Cray had switched to two's complement & sign-magnitude, however.
    – Jules
    Commented Jul 25, 2018 at 23:43
  • One's complement is not that complicated to implement. 2's complement adder has both carry-in and carry-out, loop them and viola, 1's complement adder is here. Probably this easiness of implementation and easiness of negation were two factors seducing machine architects to select 1's complement.
    – lvd
    Commented Jul 26, 2018 at 16:09
  • 2
    @lvd: A two's-complement adder can process bits or small clumps of bits sequentially, retiring each bit or clump before progressing to the next. Many early machines had ALUs that were smaller than the word size, and so being able to handle bits sequentially was useful. Having to make a second clenaup pass through the bits after discovering the value of a carry flag may be possible, but I wouldn't call it "easy".
    – supercat
    Commented Jul 26, 2018 at 16:26
  • The majority of 'big' machines of 60ies were not using serial architecture. The only examples I can remember are miniaturized PDP-8 variant and probably earliest tube computers where every logic gate took cubic decimeters.
    – lvd
    Commented Jul 26, 2018 at 16:33
  • @lvd: There may be efficient ways of designing an ALU which is the exact size of the intended operands, but operating on things that are larger or smaller will create additional complications. If one wants to multiply a pair of two's-complement 8-bit values, for example, one can promote to a larger type, do the multiply, and then discard the upper bits of the result. That won't work in ones'-complement, however.
    – supercat
    Commented Jul 26, 2018 at 16:43
46

I imagine representations other than two’s complement (ones’ complement, sign/magnitude...) declined in popularity because two’s complement is simpler to implement; in particular:

  • addition, subtraction, and multiplication of two signed input values of length n can use the same implementation as the unsigned variants, modulo 2n;
  • zero only has one representation, with all-zero bits, which means testing for equality with zero is straightforward (which has knock-on effects on implementations of equality testing etc. since the latter can be implemented using subtraction, which also works for ordering values).

Ones’ complement systems still exist, e.g. the UNIVAC 1100/2200 series, but as you mention they are rare (and existent probably only for historical reasons).

Improve this answer
9
  • 2
    This begs the question then; if twos-compliment is easier, why didn't the early machines use it?
    – Maury Markowitz
    Commented Jul 27, 2018 at 1:26
  • 1
    @MauryMarkowitz: The earliest machines did. The real question should be why machines stopped using two's-complement for awhile before getting back to it.
    – supercat
    Commented Jul 27, 2018 at 6:29
  • 1
    The caveat for the multiply in this answer is that it refers to the product modulo 2^n or in other words, the lower order n bits of a product which are the same for signed or unsigned multiply. In most cases, such as IBM 360 series, X86 series, 68000 series, ... , there are multiply instructions that produce a product of 2n bits, and in these cases, there is a difference between signed and unsigned multiply.
    – rcgldr
    Commented Oct 13, 2018 at 23:42
  • @MauryMarkowitz - this was more of a case of which machine for the early computers. The CDC 3000 and 6000 series (1960's) used one's complement while the IBM 360 series (1960's) used two's complement.
    – rcgldr
    Commented Oct 13, 2018 at 23:45
  • 2
    @kasperd - I deleted my prior comment and added a new one about multiply modulo 2^n. My impression is that most processors that produce n bit products have instructions to either produce the lower n bits or the upper n bits of a product, and the upper n bits will be different for signed versus unsigned.
    – rcgldr
    Commented Oct 13, 2018 at 23:48
17

But I find that modern day examples of computers that use ones complement rather hard to come across.

I can only think of the Unisys Clearpath here - and even they are Itaniums at hardware level by now.

The C standard is obviously written with one's complement machine in mind; for example, it specifies that a signed integer may hold values -32767 to +32767.

Jup, that way either system of signed integer handling (within 16 bits) will conform.

So what is the reason for the decline in popularity for ones' complement architectures?

It was never really popular in the first place. Even with early computers the large majority did use two's complement due the much simpler handling.

While it is true that a ones' complement implementation can save circuitry due the fact that a subtraction is just an addition with the subtrahend being negated (*1,2), it also adds complexity to (micro) program design and adds pitfalls (*3).

Ones' complement offers advantages in multi-word multiplication and division (*4), as well as for certain mathematical tasks (nearing zero from either side). But it adds complexity to hardware and/or software as every operation crossing zero needs an adjustment.

To a certain degree it's in use today almost everywhere, as the IEEE 754 Floating Point standard is based around signed values including signed zero. So with a positive spin it can be said that modern CPUs use both: The core CPU's handling (read integer) is two's complement, while associated FPUs use the advantages of ones' complement.

*1 - That's why the Pascaline uses nines' complement

*2 - But only if it's not negative zero and so on.

*3 - Like the need to always know if a comparison is meant to be numeric and integer so a correction for +/- 0 is to be applied.

*4 - As no additional step for sign calculations is needed.

Improve this answer
20
  • 16
    IEEE floating point is sign-magnitude not ones complement.
    – Peter Green
    Commented Jul 25, 2018 at 17:31
  • 4
    Yes both sign magnitude and ones complement can represent negative zero.
    – Peter Green
    Commented Jul 25, 2018 at 18:14
  • 4
    How does ones'-complement math offer advantages for multi-word multiplication and division? I see nothing but downside for it from an ease-of-computation standpoint.
    – supercat
    Commented Jul 25, 2018 at 22:52
  • 6
    @Raffzahn Are you sure your answer isn't potentially confusing sign-magnitude and one's-complement together just because both can represent -0? Using a single-octet example, the former would be 0x81 for -1 while the latter would be 0xFE, and IEEE-347 floating point is like the former, isn't it?
    – mtraceur
    Commented Jul 25, 2018 at 23:37
  • 3
    @Raffzahn: Two's-complement signed and unsigned multiplication both work identically when the source operands are padded to the same size as the result. I'm not sure what advantage I see for ones'-complement there. As for division, I'm also not quite sure what you're getting at. Using four-bit one's-complement math, -6 would be 1001, 2 would be 0010, and -3 would be 1100. How does 1001/0010 yield 1100, and how would 1001/1100 yield 0010?
    – supercat
    Commented Jul 26, 2018 at 0:34
6

Not quite an answer but an observation.

While ones' complement machines are now almost extinct, ones' complement computations are still here, and in large scales.

Every IPv4 packet header has a checksum, that is calculated exactly as ones' complement sum of 16bit words of the header contents.

Same with TCP and (optionally) UDP packets, where the whole packet is checksummed in the same way.

Improve this answer
2
  • 9
    Computation of the IPv4-style checksum is often best done by computing the sum with a longer type and then reducing that mod 65535 using shifts and masking operations. An advantage of the 16-bit ones'-complement checksum is that swapping the byte order of the source data will swap the byte order of the sum, so the process as a whole byte-order agnostic.
    – supercat
    Commented Jul 26, 2018 at 22:31
  • yes, it is still a way two's complement machines emulate ones' complement calculations. And byte-order independence appears due to carry-around basics of the ones' complement addition. Nice example of that could be found in linux kernel sources.
    – lvd
    Commented Jul 27, 2018 at 8:54
4

One's complement requires different operations for signed integers than for unsigned integers. With two's complement, ADD and SUB are the same for both number types, except for overflow flags, so typically, a CPU sets both an unsigned overflow and a signed overflow flag for each ADD or SUB and this is easier than making 2 kinds of ADD and 2 kinds of SUB. This is closely related to modulo arithmetic : two's complement is a modulo 2^N just like unsigned integers, just with different labels (e.g. in mod 256, the number after 127 is called -128 instead of 128), whereas one's complement doesn't follow the rules of modulo.

MUL often also is practically the same for two's complement and unsigned, if it doesn't give the answer in a field bigger than that of the operands ; otherwise you need to have a signed version. DIV always needs a separate signed version.

Improve this answer
2

The C standard is obviously written with ones' complement machine in mind; for example, it specifies that a signed integer may hold values -32767 to +32767

No, that would be the minimum set of values for a signed 16 bit integer. 2's complement is a superset of this. In fact, C11 explicitly allows for both 1 and 2's complement integers (section 6.2.6.2).

But I find that modern day examples of computers that use ones' complement rather hard to come across. I think it's safe to assume that anything you've got that runs a computer program and has signed integers of some kind uses two's complement. So what is the reason for the decline in popularity for ones complement architectures?

With 2's complement, the processor does not need to know whether it is dealing with a signed number or an unsigned number. Take, for example, the 6502. The bit pattern 1111 1100 can be viewed as either -4 or 252 but when you add it to another number, the CPU does not care whether it is signed or not. It can use the same circuitry and the answer comes out right by just doing an unsigned add. e.g.

0000 00010 + 1111 1100 = 1111 1110 = -2 or 254 depending on signed or unsigned

You just need an extra few gates to get the signed overflow as well as the unsigned carry. I think this is the main reason almost everybody uses 2's complement nowadays.

Compare with floating point representations. Floating point numbers are always signed, so the advantage of being able to treat signed and unsigned numbers the same is negated (ahem). There are other technical reasons for using 1's complement aswell, but you'll find that the floating point format that everybody uses nowadays (IEEE754) uses a 1's complement mantissa. T

Improve this answer
5
  • 1
    IEEE754 doesn't use a 1's complement mantissa
    – phuclv
    Commented Aug 9, 2020 at 5:48
  • @phuclv Yes it does. For example, the most significant bit of a double precision number is the sign, the next 11 bits are the exponent and the last 52 bits are the mantissa (with an implied 1 at the beginning, giving 53 bits). If you look at the representation of, say 5 and -5, you'll find that they differ only in the sign bit e.g. 0x4014000000000000 and 0xc014000000000000.
    – JeremyP
    Commented Aug 10, 2020 at 7:42
  • 1
    That's called signed-magnitude. If it's 1's complement then 5 is 0101 and -5 is 1010. In sign magnitude it's 0101 vs 1101
    – phuclv
    Commented Aug 10, 2020 at 9:18
  • @phuclv oops, yes you are right.
    – JeremyP
    Commented Aug 12, 2020 at 7:22
  • "No, that would be the minimum set of values for a signed 16 bit integer. 2's complement is a superset of this" true, but that's exactly the proof why C was written with ones complement in mind. By setting the minimums the way the are, 1's complement is sufficient for C and that's what 'written with 1's complement in ming' means.
    – Raffzahn
    Commented Mar 5, 2022 at 4:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .