Which complement does C use internally?

Question

Everything I look up just tells me how to do complement operations/calculations in C.

I want to know what representation does C use internally and how does it handle with overflow.

Answer 1

C allows 3 representation for signed integers (https://port70.net/~nsz/c/c11/n1570.html#6.2.6.2p2):

• the corresponding value with sign bit 0 is negated (sign and magnitude);
• the sign bit has the value -(2M) (two's complement);
• the sign bit has the value -(2M- 1) (ones' complement).

Two's complement is most common.

Unsigned overflow wraps around the maximum value for the unsigned.

Signed overflow causes undefined behavior. I.e., it is assumed not to happen, and if you do make it happen, no guarantees can be made about your program's behavior.

Overflow in signed atomics is an exception: it is well defined and two's complement is mandated there: https://port70.net/~nsz/c/c11/n1570.html#7.17.7.5p3.

Answer 2

Whether C uses a one's complement, two's complement, or sign/magnitude representation for negative integers is implementation defined. That is, each compiler gets to choose, typically based on the processor it's generating code for.

So when you write

x = -x

the compiler might generate code equivalent to

x = ~x;            /* one's complement */

or

x = ~x + 1;        /* two's complement */

or

x ^= 0x80000000;   /* sign/magnitude, assuming 32 bits */

Most of the time you don't have to worry about this, of course. (Also most of the time — these days it's a safe bet to say all of the time — you're working on a machine that uses two's complement, as it's the overwhelming favorite.)

Since it's implementation defined, the documentation is supposed to tell you. But I suppose you could always determine it empirically with a scrap of code:

#include <stdio.h>
#include <limits.h>

int main()
{
    int x = 1;
    int negativex = -x;
    if(negativex == ~x)
         printf("one's complement\n");
    else if(negativex == ~x + 1)
         printf("two's complement\n");
    else if(negativex == (x ^ (1 << (sizeof(x) * CHAR_BIT - 1))))
         printf("sign/magnitude\n");
    else
         printf("what the heck kind of machine are you on??\n");
}

You asked about overflow. For unsigned integers, overflow is defined as "wrapping around" in the obvious way (that is, it's performed modulo 2^N, where N is the number of bits). But for signed integers, overflow is formally undefined: theoretically there can be machines where signed integer overflow generates an error, more or less like dividing by 0.

(On ordinary two's complement machines, of course, signed integer arithmetic quietly wraps around in the obvious way also, since the whole point of two's complement is that wraparound overflow makes it work.)

---

Addendum: Although the C Standards so far have, as mentioned, allowed for all three possibilities, two's complement is such the overwhelming favorite these days that, from what I hear, the next revision of the C Standard is going to require/guarantee it.

Answer 3

In short, we can say that the 2s complement in C is defined as the sum of the one's complement in C and one.

The 2s complement in C is generated from the 1s complement in C. As we know that the 1s complement of a binary number is created by transforming bit 1 to 0 and 0 to 1; the 2s complement of a binary number is generated by adding one to the 1s complement of a binary number.