When does -n = n (for n != 0)?

By 0x7df, Fri 12 November 2021, modified Fri 12 November 2021, in category Misc

When does \(-n = n\) (for \(n \ne 0\))?

You would expect the following C code to fail:

#include <stdio.h>
#include <assert.h>

void main()
{
    int n = 8;
    assert(n == -n);
    printf("Success\n");
}

and it does, for values of n other than zero.

However, there's another case where it doesn't fail:

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

void main()
{
    int n = INT_MIN;
    assert(n == -n);
    printf("Success\n");
}

where INT_MIN is the (machine-dependent) minimum representable integer.

Why is this?

Two's complement number representation

It's a consequence of using the two's complement system for representing signed integers.

Negative numbers aren't intrinsically represented in binary, so doing so is a matter of convention. The very simplest system (the signed magnitude representation) would be to use the most significant bit to represent sign; for example in this three-bit system the 0-- words represent positive numbers and the 1-- ones represent negative numbers:

Binary Unsigned Signed
000 0 0
001 1 1
010 2 2
011 3 3
100 4 -0
101 5 -1
110 6 -2
111 7 -3

Or, each negative number could be represented by taking the complement of the positive number (switching each bit):

Binary Unsigned Signed
000 0 0
001 1 1
010 2 2
011 3 3
100 4 -3
101 5 -2
110 6 -1
111 7 -0

This is the one's complement system.

Both of these systems have two zeros - a positive one and a negative one - and the range of numbers that can be represented is one less as a result. More importantly though, addition and multiplication are made more complicated by the fact that four cases need to be considered expicitly.

The two's complement system resolves this problem by making addition and multiplication the same whatever the sign of the operands. (It also makes them essentially the same for signed integers as for unsigned integers.)

Two's complement representation looks like this:

Binary Unsigned Signed
000 0 0
001 1 1
010 2 2
011 3 3
100 4 -4
101 5 -3
110 6 -2
111 7 -1

(The negative values represented are one less than in the one's complement system.)

Now, to add \(n\) to a number, just move down the list \(n\) places, wrapping around whenever you get to the bottom, and vice versa for subtraction. This will always work, with the only non-obvious behaviour being when you get to maximum representable value (3 here), and find that adding to this flips you to the the minimum value (-4) and then up from there - i.e. overflow.

E.g. in real life:

// Signed case
printf("%d\n", INT_MAX + 1);   // Prints '-2147483648'
printf("%d\n", INT_MIN);       // Prints '-2147483648' (for comparison)

// Unsigned case
printf("%u\n", UINT_MAX + 1u); // Prints '0' (there is no UINT_MIN of course)

But this also means you can get back to where you started from; e.g. back in the three-bit system, adding 8 to -4 gets you round the loop once so that you land back on -4. In general, \(-n + R \rightarrow -n\) where \(R\) is the range (max - min + 1).

Similar things happen with multiplication, so:

printf("%d\n", INT_MIN*-1);

and, as in the original question:

printf("%d\n", -INT_MIN);

both give back INT_MIN (in the former case the GNU compiler warns you).

Put another way: to find the two's complement representation of a negative number, you can find the one's complement of it (i.e. flip all the bits), and then add 1.

E.g. to find -3, start with 3 (011), flip the bits (100), and add 1 (101), which we can see from the table above represents -3.

If we start with INT_MIN (-4 in the 3-bit system, represented by 100), running the steps in the opposite direction, we subtract 1 (011, which is the representation of 3), the flip the bits, giving 100 (which is -4 again).

Comments

Add comment