Is one's complement a real-world issue, or just a historical one?

Question

Another question asked about determining odd/evenness in C, and the idiomatic (x & 1) approach was correctly flagged as broken for one's complement-based systems, which the C standard allows for.

Do systems really exist in the 'real world' outside of computer museums? I've been coding since the 1970's and I'm pretty sure I've never met such a beast.

Is anyone actually developing or testing code for such a system? And, if not, should we worry about such things or should we put them into Room 101 along with paper tape and punch cards...?

Homicide

I know this question is old, but anyone reading it should be aware that (x & 1U) is valid (note the U) for determining even/oddness even on ones-complement or sign/magnitude implementations. – Leigha

@R. Are you sure?: In 32-bit 1's comp, -1 is represented as 0xFFFFFFFE, so (0xFFFFFFFE & 0x00000001) = 0x00000000 = false. – Homicide

@Roddy: Casting a negative signed integer is required to compute (MAX_INT+1- (-value)) on all systems. For systems which use two's-complement math, the result of the computation will have the same bit representation as the original signed integer, and many compilers will thus simply reinterpret the value without generating any code to operate on it. On systems with one's-complement or signed-magnitude computation, however, the compiler would have to generate code for the typecast to ensure defined behavior. – Citation

@Supercat - Interesting, thanks! re: (MAX_INT+1- (-value)) - do you have a source for that? Is it only in C99 standard? – Homicide

@Roddy: The C standard has for years--quite possibly since the beginning--specifed that if an out-of-range value is assigned to or cast to an unsigned integer type, the value will be the result of adding or subtracting (max_for_that_type+1) until it is within range. That is just as much a part of the standard as is the behavior of e.g. casting an "int" to a "float". Note that someInt = (int)someFloat is very different from someInt = ((int)&someFloat); the former will convert the value, while the latter will simply reinterpret the same bit pattern. – Citation

Wikipedia's article on signed number representations mentions that "the Unisys ClearPath Dorado series mainframes use ones' complement". – Simulate

Answer 1

This all comes down to knowing your roots.
Yes, this is technically an old technique and I would probably do what other people suggested in that question and use the modulo (%) operator to determine odd or even. But understanding what a 1s complement (or 2s complement) is always a good thing to know. Whether or not you ever use them, your CPU is dealing with those things all of the time. So it can never hurt to understand the concept. Now, modern systems make it so you generally never have to worry about things like that so it has become a topic for Programming 101 courses in a way. But you have to remember that some people actually would still use this in the "real world"... for example, contrary to popular belief there are people who still use assembly! Not many, but until CPUs can understand raw C# and Java, someone is going to still have to understand this stuff.

And heck, you never know when you might find your self doing something where you actually need to perform binary math and that 1s complement could come in handy.

Jamajamaal

Thanks. Agree fully that you need to have learnt it, but you shouldn't worry about it - like 6-bit bytes, and how core memory works. BTW, it's "complement", not "compliment". One's compliment could be "that's a nice sign bit you're wearing today". – Homicide

I do a lot of interviewing of software engineers, using Steve Yegge's Five Areas (steve.yegge.googlepages.com/…), and you better believe that one of the areas is Bits and Bytes. If you want to be a good SDE, you must understand binary number systems, and ones and twos complement is part of that. I would hope that any decent Computer Science course covers this in the Computer organisation class(es). – Kuehl

@Roddy: 6-bit bytes are actually not allowed in C or C++: the minimum amount of bits in a byte (which C / C++ define as sizeof(char)) is 8. – Cellar

@DavidStone actually sizeof(char) is defined to be 1. What you want to refer to is CHAR_BIT instead. – Matronymic

@Ruslan: Sorry, what I wrote was ambiguous. I was trying to say that C and C++ define a byte as sizeof(char), and the minimum number of bits in that is 8. – Cellar

Answer 2

I work in the telemetry field and we have some of our customers have old analog-to-digital converters that still use 1's complement. I just had to write code the other day to convert from 1's complement to 2's complement in order to compensate.

So yes, it's still out there (but you're not going to run into it very often).

Cochrane

Signed-magnitude, offset-binary, and one's-complement exist for I/O, but in practice are almost always converted by code to either offset-binary or two's-complement as soon as they are read in. – Citation

Could someone with the relevant experience please give some brand names, URLs, or search keywords that might help to answer the OP's question? This answer helps change my search keywords from "modern ones' complement platform" to "modern ones' complement a2d converter" but I'm sure it's possible to be more explicit. – Lipid

Am I correct that this answer is not talking about a C/C++ platform where int natively uses ones'-complement representation in memory, but is merely talking about a wire format (for talking to some peripheral device) which specifies that negative numbers in some/all fields must be encoded in ones'-complement? If so, this is similar in spirit to the RFC 791 example above. – Lipid

@Lipid I think this is different from the RFC 971 example. The 1's complement number from an ADC would represent a digitized bipolar (positive and negative) signal. This ADC could then be used as an input directly into a 1's complement machine, which in turn could be processed in C/C++; but I'm not aware of any such examples. There is some mention that major vendors like Analog Devices once made these types of ADCs, but even their reference materials suggest those are rare (cf. analog.com/media/en/training-seminars/design-handbooks/…) – Xenophanes

…Such an ADC would also probably be old enough that it wouldn't be using any kind of packet or serial communication interface; instead the bits of the digitized sample would appear on pins of the IC ("parallel"). – Xenophanes

Answer 3

I decided to find one. The Unisys ClearPath systems have an ANSI C compiler (yes they call it "American National Standard C" for which even the PDF documentation was last updated in 2013. The documentation is available online;

There the signed types are all using one's complement representation, with the following properties:

Type                 | Bits | Range
---------------------+------+-----------------
signed char          |   9  |  -2⁸+1 ...  2⁸-1
signed short         |  18  | -2¹⁷+1 ... 2¹⁷-1
signed int           |  36  | -2³⁵+1 ... 2³⁵-1
signed long int      |  36  | -2³⁵+1 ... 2³⁵-1
signed long long int |  72  | -2⁷¹+1 ... 2⁷¹-1

Remarkably, it also by default supports non-conforming unsigned int and unsigned long, which range from 0 ... 2³⁶ - 2, but can be changed to 0 ... 2³⁶ - 1 with a pragma.

Faceless

FYI, "ANSI C" is a common way to refer to the first C standard (C89/C90). In other words, ANSI C == C89. – Delusive

Out of curiosity, how does it represent signed long long int? Does it use a "straight" binary representation, or does it do something interesting? If the system could support a 71-bit signed value with a straight binary representation, it should have no trouble supporting a conforming 70-bit unsigned type, but it doesn't. That makes me wonder if it might use something other than a straight binary representation (which is allowable for signed types, but not unsigned ones). – Citation

Answer 4

RFC 791 p.14 defines the IP header checksum as:

The checksum field is the 16 bit one's complement of the one's complement sum of all 16 bit words in the header. For purposes of computing the checksum, the value of the checksum field is zero.

So one's complement is still heavily used in the real world, in every single IP packet that is sent. :)

Kuehl

Hmm, well... I was referring to one's complement as a means of representing negative integers, rather as a means of bitwise inversion, but you probably knew that. +1 for effort :-) – Homicide

A fun fact about the ones'-complement checksum is that if one reads pairs of bytes in the source data using 16-bit words and stores the two-byte checksum likewise, the same code will work for big-endian and little-endian architectures. – Citation

Answer 5

The CDC Cyber 18 I used back in the '80 was a 1s complement machine, but that's nearly 30 years ago, and I haven't seen one since (however, that was also the last time I worked on a non-PC)

Beeson

Answer 6

I've never encountered a one's complement system, and I've been coding as long as you have.

But I did encounter a 9's complement system -- the machine language of a HP-41c calculator. I'll admit that this can be considered obsolete, and I don't think they ever had a C compiler for those.

Keewatin

Answer 7

We got off our last 1960's Honeyboxen sometime last year, which made it our oldest machine on site. It was two's complement. This isn't to say knowing or being aware of one's complement is a bad thing. Just, You will probably never run into one's complement issues today, no matter how much computer archeology they have you do at work.

The issues you are more likely to run into on the integer side are endian issues (I'm looking at you PDP). Also, you'll run into more "real world" (i.e. today) issues with floating point formats than you will integer formats.

Lilybel

I was on a site a few weeks ago that still had a few honeyboxen running! I was pretty shocked to see the machine powered up. – Wheen

Answer 8

Funny thing, people asked that same question on comp.std.c in 1993, and nobody could point to a one's complement machine that had been used back then.

So yes, I think we can confidently say that one's complement belongs to a dark corner of our history, practically dead, and is not a concern anymore.

Capital

The article linked raises a question to which no one responds ("Are there still any ones-complement machines out there that the Standard wants to support? Which one(s)? ...") but given that the thread was on a different topic, I would not consider it an exhaustive survey. – Beep

@JosiahYoder: you can't provide evidence that something isn't used. The fact that no-one can point to a specific relevant architecture, not on that thread on comp.std.c nor in this question on SO, is the best evidence you can get. In case you don't know, comp.std.c is a mailing list used for discussing C-standard evolution, including by the people on the standard committee, and was a much more important communication channel back in those days. – Capital

Answer 9

Is one's complement a real-world issue, or just a historical one?

Yes, it still used. Its even used in modern Intel processors. From Intel® 64 and IA-32 Architectures Software Developer’s Manual 2A, page 3-8:

3.1.1.8 Description Section

Each instruction is then described by number of information sections. The “Description” section describes the purpose of the instructions and required operands in more detail.

Summary of terms that may be used in the description section:
* Legacy SSE: Refers to SSE, SSE2, SSE3, SSSE3, SSE4, AESNI, PCLMULQDQ and any future instruction sets referencing XMM registers and encoded without a VEX prefix.
* VEX.vvvv. The VEX bitfield specifying a source or destination register (in 1’s complement form).
* rm_field: shorthand for the ModR/M r/m field and any REX.B
* reg_field: shorthand for the ModR/M reg field and any REX.R

Scend

Does compiled code ever actually contain a VEX bitfield encoded in 1's complement? – Beep

@JosiahYoder of course, whenever a VEX-encoded instruction is used, it has some fields inverted. Similarly with EVEX prefix. I believe this was done to avoid clashes with 32-bit-mode instructions, which have been removed from native 64-bit mode, but must be still working in 32-bit mode along with all the SIMD extensions. – Matronymic

@Matronymic I'm not familiar enough with Intel's assembly language to know if VEX or EVEX instructions are common or not. Are VEX instructions common? When you say "I believe this was done..." are you referring to the use of one's complement instead of two's complement? I'm also very unfamiliar with 32- vs. 64- bit mode (other than guessing that's a key difference between Program Files and Program Files (x86)), so I'm lost on how this relates to one's complement. – Beep

@JosiahYoder if the target CPU supports AVX, then e.g. GCC will emit VEX-encoded instructions even if they can be encoded without VEX prefix (e.g. most of SSE,SSE2,... instructions). As the compilers become more capable of auto-vectorization, these instructions become more and more common in compilers' output. As for "I believe this was done...", I was referring to the inversion as it is, not compared to 2s complement. Anyway, it's actually nothing you'd come across while writing normal high-level applications — it's just a peculiarity of how instructions of certain class are encoded. – Matronymic

See my follow-on question: – Beep

As Ruslan comments here, and as hoodaticus comments at my follow-on question, 1's complement is not storing negative integers here. So "1's complement" here is really just a synonym for "bitwise not" or "bitwise negation". – Beep

@JosiahYoder - What do you think 1's compliment is? It inverts the bits. OP asked for a place where 1's compliment was used, and that's what this answer provides. – Scend

@Scend - Sorry for the downvote. I don't use them often. But although 1's complement is inversion of bits, it's also a number system for representing positive and negative numbers with both a +0 and -0 and a variety of other quirks compared to 2's complement. Although the docs use the term 1's complement here, they don't mean 1's complement in this broader sense. – Beep

@JosiahYoder - I'd be delighted to hear your theory regarding how Intel's SSE and arithmetic units use the 1's compliment representation in micro-ops. I'm guessing Intel uses 1's compliment representation to fuse some of the micro-ops to reduce latency (i.e., it does not have to be calculated as a separate op in the ALU), but I won't speculate any further. I'd also suggest reporting the erratum to Intel so they can revise their manual. – Scend

"Systems that use one's complement" are those which represent data in one's complement representation and do arithmetic operations on those. The example brought here is of a negating bitfields in statically encoded op-codes. It does not do arithmetic on those values. – Capital

@ybungalobill - I cited the question I answered. It does not ask for systems. He asked about application of 1's compliment in practice (the "real world"). As far as I know, CRC and CRC32C codes use it too. – Scend

First, please read the OP, it clearly asks about systems (i.e. architectures) in the context of the C language, not about applications. Second, CRC does not interpret the bit patterns as negative numbers at all, it's instead another algorithmic use of bitwise NOT, not one's complement as a negative number representation, which the OP was asking about. – Capital

@ybungalobill - I answered the titular question about real world applications of 1's compliment. I even cited it so there was no mistake about what was being answered. I've learned to do that because of folks on Stack Overflow will take contrarian position just to argue. Only on Stack Overflow would we find people who would claim 1's Compliment is not Negation. q.v. – Scend