Ones-complement arithmetic: it lives!

Most hackers know how the twos-complement representation of binary numbers works, and are at least aware that there was an older representation called “ones-complement” in which you negated a binary number by inverting each bit.

This came up on the NTPsec development list recently, with a question about whether we might ever have to port to a non-twos-complement machine. To my utter, gob-smacked astonishment, it turns out ones-complement systems still exist – though, thankfully, not as an issue for us.

I thought I could just mumble something about the CDC 6600 and be done, but if you google “one’s-complement machines” you’ll find that Unisys still ships a series of machines with the brand “Clear-Path Dorado” (latest variant introduced 2015) that are emulations of their old 1100-series mainframes running over Intel Xeon hardware – and these have one’s-complement arithmetic.

This isn’t a practical port blocker for NTPsec, as NTP will never run over the batch OS on these things – it’s about as POSIX-compatible as the Bhagavad-Gita. It’s just weird and interesting that ones-complement machines survive in any form at all.

And a bit personal for me. My father was a programmer at Univac in the 1950s and early ’60s. He was proud of his work. My very first interaction with a computer ever was getting to play a very primitive videogame on the oscilloscope-based video console of a Univac 1108. This was in 1968. I was 11 years old, and my game machine cost $8M and took up the entire ground floor of an office building in Rome, Italy.

Other than the 1100, the ones-complement machines Wikipedia mentions (LINC, PDP-1, and CDC6600) are indeed all long dead. There was a ones-complement “CDC Cyber” series as late as 1989, but again this was never going to implement POSIX.

About other competitors to twos-complement there is less to say. Some of them are still used in floating-point representations, but I can find no evidence that sign-magnitude or excess-k notation have been used for integers since the IBM 7090 in 1959.

There’s a comp.lang.std.c article from 1993 that argues in some technical detail that that a C compiler is not practical on ones-complement hardware because too many C idioms have twos-complement assumptions baked in. The same argument would apply to sign-magnitude and excess-k.

UPDATE: It seems that Unisys is the graveyard of forgotten binary formats. I have a report that its Clear-Path Libra machines, emulating an ancient Burroughs stack machine architecture, use sign-magnitude representation of integers.

41 thoughts on “Ones-complement arithmetic: it lives!

  1. Twos-complement is one of those ideas that seems so obvious that it’s hard to believe anything else existed. It makes circuitry and APUs easy (they don’t need to care about the sign of a number; addition and subtraction just works), it’s easy for humans to understand, it just seems to make sense.

    It’s also interesting to me that they’re emulating ones-complement on x86 hardware, which is natively twos-complement.

  2. Way back in the ’70s I was a computer tech in the U.S. Navy. This involved both software work (in hand-assembled machine code) and hardware diagnosis and repair. I worked on several Univac computers that were 1s complement: CP642A, CP642B, 1218, and 1230. When I went through the technician school in ’71 and ’72, the ONLY binary arithmetic we were taught was 1s complement. When I started building a series of hobby computers in the late ’70s (8080, Z80, RCA 1802, 6502, and 6800 based), the whole idea of 2s complement math was new and mysterious to me. I can still remember my shock when I noodled out how it could work without a dedicated sign bit! I wrote a floating point “math pak” for those Univac machines, and then later another for Tarbell Basic on Z80s, and it was notably easier on the latter, despite being just 8 bit computers (vs. 30 bits for the Univac math pak I wrote)…

    • >I worked on several Univac computers that were 1s complement: CP642A, CP642B, 1218, and 1230.

      I believe those were all AN/UYK variants. That architecture was based on the 1108, the same machine ancestral to the Dorado ClearPath.

  3. Guess I’ve led a sheltered life. I’ve never encountered 1s complement in the wild and would have had to search how it even works. The whole things sounds … weird.

  4. In a comment on the TEHOK 1.10 thread, I had speculated tongue-in-cheek on the possibility of a machine with each word consisting of an infinite number of bits on either side of the radix point, which would be both one’s and two’s complement by virtue of the aforementioned word structure.

    How well would C deal with such a machine? Does int have to be represented by a hardware integer type? Does float have to actually be floating point (as opposed to infinite precision fixed point)? Would anything in the standard choke on a < < b where b is transfinite? (There shouldn't be a space between the two <s, but I just discovered that the browser I'm using wedges reproducibly when I type the character sequence that's supposed to be there).

    Of course, such a machine isn't actually constructible, but you could write a virtual machine that could use bignums and data structures representing infinite values to weakly emulate it.

  5. > I believe those were all AN/UYK variants.

    Under the Joint Electronics Type Designation System, just about any general purpose computer at the time would have been given the designation AN/UYK-#; as the designation expands to General Utility (U) / Data Processing (Y) / Computing (K). (As a side note, the AN/ prefix just refers to an older name for the nomenclature, the Joint Army-Navy Nomenclature System). Nowadays, this nomenclature is used to name larger systems, and the individual computers included in the system are not designated directly.

    • >Under the Joint Electronics Type Designation System, just about any general purpose computer at the time would have been given the designation AN/UYK-#;

      Right, and for some years after 1970 (at least until ’84) every shipboard computer so designated was built by Sperry Univac. My father’s end-of-career job was running Univac’s worldwide tech-support operation, which is how I know about this.

  6. Were the Cray processors one’s-complement? They are descendants of the 6600, and I can just see Seymour Cray sticking with it. They most definitely had a Unix on them.

    • >Were the Cray processors one’s-complement?

      Nope.

      2s-complement, with 72-bit words. And about one-sixth the FLOPS of the smartphone in your pocket.

  7. > I can find no evidence that sign-magnitude or excess-k notation have been used for integers since the IBM 7090 in 1959.

    Excess-K (K = 127) is used in video encodings to encode the U and V coefficients of YUV data. They have a perfectly good 8-bit signed integer in there, but it’s not 2’s-complement.

    • >Excess-K (K = 127) is used in video encodings to encode the U and V coefficients of YUV data. They have a perfectly good 8-bit signed integer in there, but it’s not 2’s-complement.

      I should have said “used in a computer’s instruction set”. Ones-complement has some survivals in A-to-D converters, oddly enough (seen on Stack Overflow).

  8. Sign-magnitude and excess-k (also known as offset-binary or excess code) survive to this day in IEEE 754 floating point format:

    * sign-magnitude for the whole number
    * excess code for the exponent

    • >Sign-magnitude and excess-k (also known as offset-binary or excess code) survive to this day in IEEE 754 floating point format:

      I know. That’s why I specified “I can find no evidence that sign-magnitude or excess-k notation have been used for integers

  9. The Unisys ClearPath Libra range still uses sign-magnitude integer representation. This is the old Burroughs MCP mainframe range.

    • >The Unisys ClearPath Libra range still uses sign-magnitude integer representation. This is the old Burroughs MCP mainframe range.

      Can you be more specific about the hardware models? MCP is, if I recall correctly, the OS.

  10. In my university days, one of our professors tongue-in-cheekly proved to us that the Universe runs as two’s complement.

    Assume an infinitely wide integer register, represented as an infinite sum: ?{x?2?|n??}. Set all bits to one, call the resulting number S = 1 + 2 + 4 + 8 + ….

    Multiply that by two: 2 S = 2 + 4 + 8 + 16 + …. Observe that this is the same infinite sum but without its 1 term: 2 S = -1 + 1 + 2 + 4 + 8 + … = -1 + S.

    Now we have an equation: 2 S = S – 1. Solving for S, we get S = -1, which is what we would expect on a two’s complement machine.

    • >In my university days, one of our professors tongue-in-cheekly proved to us that the Universe runs as two’s complement.

      Heh. I wondered who would bring up that “proof” first. Estimated high odds it would be one of the regulars here.

  11. The current product line would seem to consist of the ClearPath Libra 4300, 6300 and 8300 series servers. These emulate (with Intel Xeon) the old Burroughs Large Systems (B5000 through to B7800?) that were later called A-Series (A3 through A15?) and then became ClearPath. ClearPath because half of them support the Univac 1100/2200 ISA and half of them support the Burroughs A-Series ISA — quite clear, right?

    I must confess that I am relying on the Unisys marketing claims about perpetual object code/ISA compatibility since I have not worked on MCP for 20+ years. Perhaps there is another follower of your blog that still works for Unisys who can chime in with more current information?

    I should also point out for historical accuracy that there were three architecturally completely different Burroughs computer ranges: small systems, medium systems and large systems. The OS for all of these systems was called MCP but they were all completely different. Nowadays only the large system descendants remain so MCP defaults to that range.

    Finally: yes, MCP does stand for Master Control Program.

    • >These emulate (with Intel Xeon) the old Burroughs Large Systems (B5000 through to B7800?)

      Probably not the B5000 – Wikipedia says that’s dead and given the timing I believe it. The later stack-oriented machines (which IIRC were without the tagging and instruction polymorphism of the 5000) seem like more plausible candidates.

  12. @Yuri:
    > In my university days, one of our professors tongue-in-cheekly proved to us that the Universe runs as two’s complement.

    That’s the the first half of what I was getting at with my earlier comment on an infinite word width machine. Moving forward from there:

    The sum 1/2 + 1/4 + 1/8 + … converges to 1.

    So, in binary
    …1111.0000… == -1
    …0000.1111… == 1
    Therefore …1111.0000… + …0000.1111… == …1111.1111… == 0

    Which is exactly what we’d expect from a one’s complement machine. Furthermore, if we take
    …000101.000… == 5 and flip every bit we get:

    …111010.111… == …111010.000… + …0000.1111… == -6 + 1 == -5. So flipping all the bits reverses sign, also like one’s complement.

    So the universe is both one’s and two’s complement.

  13. @Jon: Brilliant. So integer arithmetic is two’s complement, and fixed-point arithmetic is ones’ complement.

  14. Wikipedia — who’d have thought! Yes, you are correct. In fact there were major architectural changes between the B5000 and the B6000/B7000 and smaller changes at about the time of the introduction of the A-Series.

    The tags actually became bigger and bigger over time. A “pseudo-tag” with the B5000, 3-bits with the B6000, and 4-bits with the A-Series (I think Wikipedia is wrong saying 4-bit tags were only introduced with ClearPath). The main instruction set changes were to allow addressing of larger main memories otherwise the spirit of the B5000 lived on in later models.

    Another interesting factoid that belongs in your “Things Every Hacker Once Knew” thread is that at the time of the B5000(48bit)/IBM7090(36-bit)/CDC6000(60-bit)/Sperry1100(36-bit) everyone used 6-bit characters in strings. With the advent of the IBM S/360 the world moved (temporarily) to 8-bit EBCDIC and everyone except Burroughs had a problem. IBM obviously moved to 32-bit words and the B6000 moved to 6 8-bit characters per word instead of the 8 6-bit characters of the B5000.

    Finally there is one other integer representation you missed out on namely BCD. Certainly IBM, Burroughs and NCR had long lasting and important business computers that represented numbers as strings of 4-bit decimal digits which mapped nicely onto what was the most important commercial language of the time – COBOL. I think we can safely say that those systems are now extinct.

  15. “Right, and for some years after 1970 (at least until ’84) every shipboard computer so designated was built by Sperry Univac. My father’s end-of-career job was running Univac’s worldwide tech-support operation, which is how I know about this.”

    My parents (both programmers) worked for Sperry-Univac in the 70s and early 80s (and then Tektronix).

    My mom has lots of stories (with no incriminating detail, though I suspect it’s all declassified long since) of doing support at Navy installations.

    Small world, innit?

  16. @Yuri:
    > @Jon: Brilliant. So integer arithmetic is two’s complement, and fixed-point arithmetic is ones’ complement

    Well, fixed point is both at infinite precision, as it includes integer arithmetic as a subset.

  17. Chuck: BCD isn’t dead at all. It’s still a native format on IBM mainframes descended from the 360, where it’s called “packed decimal”, with native instructions that handle operands in that form.

  18. > Heh. I wondered who would bring up that “proof” first. Estimated high odds it would be one of the regulars here.

    Hey, no need for the scare quotes, the proof is perfectly valid in the 2-adic number system!

  19. @Jay Maynard There’s an article by Bob Bemer that mentions that one of the reasons that the EBCDIC digits are of the form F0..F9 is to make doing arithmetic in unpacked decimal easier.

    The Intel x86 has a minimalistic set of instructions for working with unpacked BCD as well. Though rather than directly working with it, they simply “adjust” the ax register so that a preceding/following binary instruction will work properly (there’s also a separate carry flag). A close reading of the descriptions will reveal that these only provide useful results with bytes of the form 00..09, despite the “ASCII” in the mnemonic names. The instructions are disabled in 64-bit mode.

  20. It occurs to me that he was probably talking about ASCII, and simply pointing out 3 as an example of *any* value below 8, which does not cause the addition of two digit characters to carry into the next byte. I misinterpreted it because the mechanism wasn’t discussed, and there is no reason that 3 is special, whereas it’s possible that F might have been special (being all-bits-one).

  21. The Z80 also supported BCD. Probably the 8080 and 8085, also. This was not supported in the 8086 or 8088, though.

  22. @Random832, I don’t recall finding the BCD instructions in the x86 series, do you know the mnemonic?

  23. Some bignum algorithms (including RSA and some flavors of Fast Fourier Transform) represent integers using the Chinese Remainder Theorem, though that’s not direct hardware support.

    I’ve seen proposals for building such machines, but as far as I know none have ever actually been built (but who knows what lurks in the bowels of Fort Meade? :-).

  24. @Random832, I don’t recall finding the BCD instructions in the x86 series, do you know the mnemonic?

    The first one alphabetically is AAA. Unpacked BCD numbers are referred to as “ASCII” for some reason, though the representation the instructions work correctly with requires the high four bits to be zero. Easy enough to convert with AND 0F0Fh and OR 3030h, though.

  25. > The first one alphabetically is AAA.

    Which is why I even knew they existed: AAA is not only the first x86 BCD instruction alphabetically, but the first x86 instruction alphabetically, period.

  26. It is amazing how these instructions just suddenly appeared in my copy of the 8086 manual. The DAA instruction is also there. The Z80 only had the single DAA instruction, for use after either addition or subtraction. The 8086 also has DAS for use after subtraction. I’ll be.

  27. I wonder if any NPUs run ones complement. After all, specialist networking hardware generally has to have 16-bit ones complement arithmetic capabilities, to calculate Internet checksums.

    Incidentally, the reason why those use ones rather than twos complement, is so that they’re endian-insensitive: each octet carries into the other. Also, by handling the carry carefully, you can ensure that any zero checksum (except for summing a row of zeroes) comes out as negative zero (all ones), meaning that all zeroes can be used to indicate “not checksummed” — it will never be a real checksum, because every IP, UDP and TCP header contains at least one set bit.

    And of course negating the checksum before filling it in, so that a correctly checksummed packet has a checksum of zero, turns out to be really useful for encapsulation…

    The Internet checksum is a marvel of good design.

  28. >the ax register

    mangling Terry Pratchett:

    “This is the ax register of my ancestors.

    My great-grandfather replaced the handle. My father replaced the data.

    But this is still the ax register of my ancestors.”

  29. *Current* C Compiler manual for Unisys ClearPath Libra servers (MCP 18.0) confirms use of 40-bit sign-magnitude packed within a 48-bit word “int” representations: http://public.support.unisys.com/aseries/docs/ClearPath-MCP-18.0/86002268-207.pdf

    There are also unusual per-underlying-type pointer-representations (count number of bytes, or number of words, or number of double-words, depending on the pointed-to type)!

    From elsewhere, it seems that the still-current Unisys ClearPath Dorado servers use one’s-complement “int” representation, rather than sign-magnitude.

    I suppose the good news is that no currently-supported Unisys machines use alternate excess-k “int” representations.

    Summary for extreme portability in C: use arithmetic operations (instead of bitwise ones) for arithmetic operations, and don’t presume *anything* about data-pointer representations, especially not that they have a single unified format/interpretation (but hey, we already got used to that with the Intel segmented 16-bit architecture back in the day).

  30. Interestingly enough, Unisys provide POSIX interface for the current ClearPath Libra servers (yes, including the brand new 2017 models), to go with the Libra C compilers’ sign-magnitude “int” implementation.

    So perhaps there is a slight chance you might, at some point, be faced with porting to a non-2s-complement machine after all.

Leave a Reply

Your email address will not be published. Required fields are marked *