Why Does -Int_Min = Int_Min in a Signed, Two's Complement Representation

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

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!

Why does -INT_MIN == INT_MIN, and how the negative sign operate in bit level?

In common architecture negative values use 2's complement.

This has an immediate outcome: -INT_MIN will be greater (by 1) that INT_MAX. That means the the result value will be undefined(*). And still for common architectures it just happen to be -INT_MIN again.

Just look at what happens for signed bytes (values are lower so easier to handle) MIN is -128 and MAX is 127. In hexa, they are respectively 0x80 and 0x7F. But the representation of 128 as an int value is again 0x80. And when you assign that back to a signed byte type you end with (- (-128)) gives -128...

---

As char has a lower rank than int, the char is promoted to int, the operation gives a result that can be represented as an int and the conversion to a char gives an implementation defined result. But - INT_MIN is an expression that would give a result that cannot be represented as a int value. This is an exceptional condition and the behaviour is explicitely undefined per standard. That being said, common implementation handle everything the same...

Why is absolute value of INT_MIN different from INT MAX?

Most modern systems use two's complement to represent signed integer data types. In this representation, one state in the positive side is used up to represent zero, hence one positive value lesser than the negatives. In fact this is one of the prime advantage this system has over the sign-magnitude system, where zero has two representations, +0 and -0. Since zero has only one representation in two's complement, the other state, now free, is used to represent one more number.

Let's take a small data type, say 4 bits wide, to understand this better. The number of possible states with this toy integer type would be 2⁴ = 16 states. When using two's complement to represent signed numbers, we would have 8 negative and 7 positive numbers and zero; in sign-magnitude system, we'd get two zeros, 7 positive and 7 negative numbers.

Bin    Dec
0000 = 0
0001 = 1
0010 = 2
0011 = 3
0100 = 4
0101 = 5
0110 = 6
0111 = 7
1000 = -8
1001 = -7
1010 = -6
1011 = -5
1100 = -4
1101 = -3
1110 = -2
1111 = -1

I think you are confused since you are imagining that sign-magnitude representation is used for signed numbers; although this is also allowed by the language standards, this system is very less likely to be implemented as two's complement system is significantly a better representation.

As of C++20, only two's complement is allowed for signed integers; source.

Why does this code print two negative numbers?

Changing the sign of Integer.MIN_VALUE produces an overflow; you're seeing the result of that.

lua_numbertointeger - why can we assume INT_MIN has an exact representation as a float?

In 2's complement representation, the minimum value typically has only 1 bit set, as in C's INT_MIN which might be 0x80000000. So it can be exactly represented in a float because it has only one significant bit, and can be normalised without loss of precision.

But INT_MAX which is say 0x7FFFFFFF has 31 significant bits, more than the significand of float has, and so it cannot be exactly represented by a float.

Is negating INT_MIN undefined behaviour?

It depends on the platform. C supports three representations for negative numbers (see section 6.2.6.2 of the C99 standard):

• Two's complement.
• One's complement.
• Sign and magnitude.

With one's complement and sign and magnitude, -INT_MIN is defined (and equal to INT_MAX). With two's complement, it depends on whether the value with sign bit 1 and all value bits zero is a trap representation or a normal value. If it's a normal value, -INT_MIN overflows, resulting in undefined behavior (see section 6.5 of the C99 standard). If it's a trap representation, -INT_MIN equals INT_MAX.

That said, most modern platforms use two's complement without trap representations, so -INT_MIN typically results in undefined behavior.

Ramifications of C++20 requiring two's complement

One of the specific questions considered by the committee was what to do about -INT_MIN, and the results of that poll were:

addition / subtraction / multiplication and -INT_MIN overflow is currently undefined behavior, it should instead be:

4: wrap

6: wrap or trap

5: intermediate values are mathematical integers

14: status quo (remain undefined behavior)

This was explicitly considered and people felt that the best option was keeping it undefined behavior.

To clarify on "intermediate values are mathematical integers", there is a other part of the paper which clarifies that means that (int)a + (int)b > INT_MAX might be true.

---

Note that implementations are free to define specific behavior in these cases if they so choose. I don't know if any of them do.

Why may an overflow occur in the following program?

An overflow may occur because the range of integer representation in two's complement is not symmetric: the magnitude of the smallest negative number that can be represented is the magnitude of the highest positive number that can be represented, plus one. For example, on a 32-bit system the values are -2,147,483,648 and 2,147,483,647. That's why negating -2,147,483,648 would result in an overflow: the result of negation, a positive value 2,147,483,648, cannot be represented in an int of the same size.

Note that the inverse of this problem is not true: negating a positive number would not result in an overflow:

if (i > 0) { i = -i; } // No overflow here

Is INT_MIN * -1 a no-op on x86?

Using gcc 4.8.5, the line y = x * -1; is computed using the following instruction:

neg    %eax

The neg operation flips the bits of the word and then adds 1. For 32 bit 2's complement the result is:

0x80000000 # Start value
0x7FFFFFFF # Flip bits
0x80000000 # Add 1

As you see, the computer is doing exactly what you are telling it to do. This is not a no-op, as neg modifies the AF, CF, OF, PF, SF, and ZF flags. It is just an artifact of the binary representation being used. As others have stated it is simply undefined behavior.

---

Related Topics