Is (x<y)==(-x>-y) true or false?

Question

The problem is from cs:app3e 2.82. I learn that when x = INT_MIN, -x is also -INT_MIN, but

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

int main() {
    int x = INT_MIN, y = -3;
    printf("%d\n", (x < y) == (-x > -y));
    return 0;
}

on my machine(Linux version 6.2.0-34-generic (buildd@bos03-amd64-059) (x86_64-linux-gnu-gcc-11 (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0, GNU ld (GNU Binutils for Ubuntu) 2.38)), this gives output 1. Why does that happen?

I use gcc -o to compile it. I also use gcc -O0 to compile it.

Counterpressure

-INT_MIN is undefined behavior. See: #71081810 – Flange

This question is unclear to me. "I learn that when x = INT_MIN, -x is also -INT_MIN" is not strictly true because of potential UB as described by others. But what were you expecting other than 1 for the result of (x < y) == (-x > -y)? Maybe I need coffee.... – Ousel

"I learn that when x = INT_MIN, -x is also -INT_MIN" --> wrong conclusion. – Oldtimer

You could try -fwrapv to get the behavior you expected, or -fsanitize=undefined to get an explanation. – Anet

Related: Find a value y such (x < y) == (-x > -y) will be false, when x is a signed integer and x=1? (No such value without well-defined integer wrap-around, e.g. from -fwrapv). Semi-related: -x>-y on its own gets optimized differently by GCC for x86-64 vs. AArch64: The Output of the C Program '(-x > -y)' Differs on macOS and Linux - Why and How to Fix It – Letendre

Answer 1

On your platform, like many others (any platform using two's-complement without trap representations, which is most modern platforms), negating INT_MIN is undefined behavior. Compilers are allowed to assume undefined behavior does not occur, and to behave however they like, including in nonsensical ways, should it occur. As a result, gcc's optimizer (which still operates at a minimal level regardless of optimization settings) can exclude the case of INT_MIN from being a possibility when analyzing (x<y)==(-x>-y), and conclude that it is tautological, substituting in 1 without performing any runtime comparisons. And in fact, it doesn't perform any runtime comparisons, it merely loads 1 directly for printing.

Scotty

Answer 2

The actual constants INT_MIN and INT_MAX may be a bit confusing. If we look in the C standard (C17 5.2.4.2.1) it says: INT_MIN -32767 and INT_MAX +32767, meaning these are the utter minimum that must be supported, for a 16 bit int. For simplicity, all examples below will assume 16 bit int (32/64 bit two's complement systems of course use 2^31 - 1 and -2^32 so 2147483647/-2147483648).

Why these values were picked is for historical reasons. In addition to industry standard two's complement, C also supports two exotic signedness formats: one's complement and signed magnitude. In the latter two we have a negative zero and/or trap representation, giving a possible value range of -32767 to 32767.

But the vast majority of all computers use two's complement, and then INT_MIN becomes -32768 on a 16 bit system. This is fine with the standard, since it just says that INT_MIN must be at least -32767. And in two's complement, INT_MAX is still 32767.

Therefore on a two's complement system, we cannot do int x = INT_MIN; x = -x;, since INT_MAX is 32767 and cannot hold the value 32768. We would create an integer overflow, which is undefined behavior - anything can happen, including strange and nonsensical code generation by the compiler.

In the upcoming C23 standard, support for exotic signedness formats will finally get removed from C. And then INT_MIN will likely become -32768 in the standard as well.

Grosswardein

Answer 3

this gives output 1. Why does that happen?

As the other answers already explained, signed overflow is Undefined Behaviour in C, thus the compiler may assume that -x does not overflow if x is signed.

As your question is specifically about gcc: GCC supports command-line option -fwrapv so that signed overflow will wrap-around similar to like unsigned overflow does. With -fwrapv added to the command line options (or -fno-strict-overflow for that matter), your program will print 0 (false).

This option might disable some optimizations and enable others. It's interesting to see the effect on the slightly different program

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

int x = INT_MIN, y = -3;

int main()
{
    printf ("%d\n", (x < y) == (-x > -y));
    return 0;
}

where the values of x and y are no more known at compile-time:

• When compiled with -O2 -fno-wrapv, the compiler replaces (x < y) == (-x > -y) by a literal 1 irrespective of the values of x and y. This is because the expression evaluates to true if no arithmetic overflow occurs, and the compiler may assume that it does not overflow if it overflows. This is consistent with Undefined Behaviour of signed overflow.

• When compiled with -O2 -fwrapv, the compiler cannot evaluate (x < y) == (-x > -y) at compile-time, and it generates code to evaluate the expression at run-time. For the specific values supplied for x and y, the result is false.

You might also have a look at diagnostic options like -Wstrict-overflow or -Woverflow. And of course -Wall.

Merchandising