Why does -INT_MIN = INT_MIN in a signed, two's complement representation?

Question

I still haven't found a reason why the lowest signed negative number doesn't have an equivalent signed positive number? I mean in a 3 digit binary number for simplicity 100 is -4? but we can't have a positive 4 in signed format because we can't. It overflows. So how do we know two's complement 1000 is -4 1000 0000 is -128 and so on? We have no original positive number

Answer 1

We should know how we manage to make x to -x:

1. Flip all bits in x. Like 5 is 0101, and we get 1010 in this step;
2. Add 1 to what we get in last step. This time we get 1010 + 1 = 1011.

And in the real machine, negative ones are always shown in 2's complement format, so 1011 presents -5(which is -8 + 2 + 1 = -5).

Now back to the question, INT_MIN in the real machine is 1 with 31 consecutive 0.

So after the first step, you will get a number which is 0 with 31 consecutive 1 and it is INT_MAX in C language.

In the second step, add 1 to what we get from the last step, and the result is 1 with 31 consecutive 0, which is also INT_MIN.

So INT_MIN = -INT_MIN

Answer 2

Two's complement represents negative numbers by reserving the highest bit as negative. This means you can't use the highest bit as positive anymore.

All the other (lower) bits are positive but no matter how you add them up, the sum can never reach the highest bit because it's seen as negative.

Answer 3

This answer is just a summary.

In N bit 2's complement:

• The negative range is [-2^{N-1}, -1] which has cardinality 2^{N}/2.
• The positive range is [0, 2^{N-1}-1] which again has cardinality 2^{N}/2.

and the overall range [-2^{N-1}, 2^{N-1}-1] must have the cardinality 2^{N}. Performing N bit operations on any number out of this range will cause an overflow.

And notice that when all the number in this signed range is added with a bias 2^{N-1} we get an unsigned range [0, 2^{N-1}].

Answer 4

-INT_MIN is an integer overflow and is undefined behavior in C.

-INT_MIN is guaranteed to be equal to INT_MIN only when signed integer overflows wrap. This can be enabled with gcc for example with -fwrapv option.

Compiler usually take advantage of the fact that integer overflow is undefined behavior in C to perform some optimizations. Relying on signed integer overflows that wrap is unsafe.

A well known example of compiler optimization is the following

#define ABS(x) ((x) > 0 ? (x) : -(x)) 

void foo(int x){  
    if (ABS(x) >= 0) {
        // some code
    }
}

most of the compilers today (gcc, icc) with the optimizations options enabled would optimize out the test relying on the fact that -INT_MIN is undefined behavior.

Answer 5

So how do we know two's complement 1000 is -4 1000 0000 is -128 and so on? We have no original positive number

Your mistake is thinking that we need a two's complement representation of the positive number in order to compute the two's complement representation of the negative number.

The process for finding the two's complement of a negative number is:

Start out with the normal, non-two's complement representation of the absolute value of the number to be represented. So for -4, take the non-two's complement representation of |-4|, 100.

Flip all the bits: 100 -> 011 (or ...11111011 with the ones continuing indefinitely to the left).

Add one: 011 -> 100 (or ...11111100)

Now truncate to the number of bits you're using (this eliminates the carry bit or the infinite string of 1s). As a result, 100 is the 3-bit, two's complement representation of -4.

To go the other way, take the two's complement representation (100) flip the bits (011) and add one (100) you now have the non-two's complement representation of |-4|. 1*2^2 + 0*2^1 + 0*2^0 = 4. Therefore we know that representation we started off with, 100, is the 3-bit, two's complement representation of -4.

Answer 6

One way to think about it is that signed, two's complement format works by assigning each bit a power of two, then flipping the sign of the last power of two. Let's look at -4, for example, which is represented as 100. This means that the value is

-1 x 2^2 + 0 x 2^1 + 0 x 2^0

If we want to get the positive version of this value, we'd have to negate it to get

 1 x 2^2 - 0 x 2^1 - 0 x 2^0

Notice that this value is equal to

 1 x 2^2 + 0 x 2^1 + 0 x 2^0

In other words, the normal binary representation of this value is 100. However, we're in trouble here, because we're using a signed two's complement representation, which means that we have specifically reserved the 4's bit as the sign bit. Consequently, when we try to interpret the bit pattern 100 as a signed, three-bit, two's complement value, it comes back out identically to what we started with. The shortage of bits is what's hurting here.

More generally, given n bits, of which the first is the sign bit in a two's complement representation, trying to compute -1000...00 will give back the same value, because the bit needed to store the large positive value has the special meaning assigned to it.

So why do this at all? The reason for this is that if you have only n bits, you cannot store the values -2^{n - 1} through 2^{n - 1}, because there are 2ⁿ + 1 different numbers here and only 2^n different bit patterns. Excluding the largest positive number thus makes it possible to hold all the different numbers in the bit pattern specified.

But why drop the high value and not the low value? This is in order to preserve binary compatibility with unsigned integers. In an unsigned integer, the values 0 through 2^n-1 - 1 are all encoded using the standard base-two representation. Consequently, for unsigned and signed integers to agree at all, the unsigned integers are designed so that they are bit-for-bit equivalent with the first 2^{n - 1} unsigned integers, which range from 0 to 2^{n - 1} - 1, inclusive. After this, the unsigned values need the most significant bit to encode numbers, but the signed values are using this as the sign bit.

Hope this helps!

Answer 7

The alternative to two's complement has such a property, it's known as one's complement.
In one's complement form, the lowest possible value also has a valid positive form.

---

One's complement works by simply inverting all the bits in the number itself.
For example, we know that 0110 == 6 and in one's complement 1001 == -6. Using one's complement, we have just as many positive numbers as we do negative numbers.

But what about the bit representation 1111? Just by looking at it, we can tell that it's the "negative" form of zero (0000 = 0; 1111 = -0), but such a number doesn't make any sense and is somewhat wasteful.

Instead, we use two's complement, which is similar to one's complement, but after inverting the bits, we add one. So if we know that 0110 = 6, then the one's complement is 1001 and the two's complement is 1001 + 1 == 1010. Using two's complement, we don't have a "negative zero" because it causes an overflow.

A different way of looking at it is "if the highest bit is set, then the number is negative". That means that the positive range is [0 .. 2^(bits - 1)] and the negative range is everything else. There's the same number of positive numbers as there are negative numbers, but because (in this format) zero is considered positive, the negative range gets shifted one to [-1 .. (neg) 2^(bits - 1)].

---

Lets assume we're dealing with a 3-bit signed number in two's complement. That'd give us the following table:

BITS  VALUE
000       0
001       1
010       2
011       3

100      -4
101      -3
110      -2
111      -1

You can see that there's the same quantity of positive numbers as negative numbers, it's just that the negative numbers don't start from 0 like the positive set does.

Answer 8

A. There is an even number of possibilities to n-digit binary number, so we can't represent the same range for positive and negative numbers.

B. We want that every number that begin with 1 will be negative, and every number begin with 0 will be no-negative. (not the opposite, because we want same represent to positive and zero in signed and unsinged. Because of that, 0 is in the half of the positives, so them have one place less.

Answer 9

Because you have to count 0. The integer range [-4,-1] (or, equivalently -4,-3,-2 and -1) contains 4 numbers and the rest of the range [0,3] (or, equivalently 0, 1, 2 and 3) contains 4 numbers, for a total of 8, and 3 digit binary numbers have 2 to the power of 3 (=8) possible combinations.

Think of it this way. Any integer range of the form [-n,+n] necessarily has an odd size (2*n+1 integers). Whatever integer binary representation you use will have a different number of negative and positive numbers because the number of combinations is always even (powers of 2).

Answer 10

The missing digit is 0. In a mathematical sense, 0 is neither positive nor negative. But in a binary sense, since 0 has no negative bit, it's considered positive. In other words, if you wanted -128 to 128, there couldn't be a 0.