Why is `x - y <= x` true, when x=0x80000000, y = 1(32-bit complement)?

Question

I want to know if x - y overflows.

Below is my code.

#include <stdio.h>

/* Determine whether arguments can be subtracted without overflow */
int tsub_ok(int x, int y)
{
    return (y <= 0 && x - y >= x) || (y >= 0 && x - y <= x);
}

int main()
{
    printf("0x80000000 - 1 : %d\n", tsub_ok(0x80000000, 1));
}

Why can't I get the result I expect?

Answer 1

You can't check for overflow of signed integers by performing the offending operation and seeing if the result wraps around.

First, the value 0x80000000 passed to the function is outside the range of a 32 bit int. So it undergoes an implementation defined conversion. On most systems that use 2's compliment, this will result in the value with that representation which is -2147483648 which also happens to be the value of INT_MIN.

Then you attempt to execute x - y which results in signed integer overflow which triggers undefined behavior, giving you an unexpected result.

The proper way to handle this is to perform some algebra to ensure the overflow does not happen.

If x and y have the same sign then subtracting won't overflow.

If the signs differ and x is positive, one might naively try this:

INT_MAX >= x - y

But this could overflow. Instead change it to the mathematically equivalent:

INT_MAX + y >= x

Because y is negative, INT_MAX + y doesn't overflow.

A similar check can be done when x is negative with INT_MIN. The full check:

if (x>=0 && y>=0) {
    return 1;
} else if (x<=0 && y<=0) {
    return 1;
} else if (x>=0 && INT_MAX + y >= x) {
    return 1;
} else if (x<0 && INT_MIN + y <= x) {
    return 1;
} else {
    return 0;
}

Answer 2

Yes, x - y overflows.

We assume int and unsigned int are 32 bits in the C implementation you are using, as indicated in the title, and that two’s complement is used for int. Then the range of values for int is −2³¹ to +2³¹−1.

In tsub_ok(0x80000000, 1), the constant 0x80000000 has the value 2³¹, and its type is unsigned int since it will not fit in an int. Then this value is passed to tsub_ok. Since the first parameter of tsub_ok has type int, the value is converted to int.

By C 2018 6.3.1.3 3, the conversion is implementation-defined. Many C implementations “wrap” the value modulo 2³². Assuming your C implementation does this, the result of converting 2³¹ to int is −2³¹.

Then, inside the function, x - y is −2³¹ − 1, and the result of that overflows the int type. The C standard does not define the behavior of the program when signed integer overflow occurs, and so any test that relies on comparing x - y when it may overflow is not supported by the C standard.

Answer 3

Here an int is 32 bits. This means it has a total range of 2^32 possible values. Converting this to hex, that's a max of 0xFFFFFFFF(when unsigned), but not signed. A signed int will have a max hex value of 0x7FFFFFFF. Thus, you cannot store 0x80000000 in an int here and have everything work.

Answer 4

In computer programming, signed and unsigned numbers are represented only as sequences of bits. Bit 31 is the sign bit for a 32-bit signed int, hence the highest 32-bit int you can store is 0x7FFFFFFF, hence the overflow with 0x80000000 as signed int.
Remember, a signed int is an integer that can be both positive and negative. This is as opposed to an unsigned int, which can only be used to hold a positive integer. What you are trying to do is, you are trying a signed int variable hold an unsigned value - which causes the overflow.

For more info check Signed number representations or refer any beginner level digital number systems and programming book.