What Values of Variables x and y Will Produce Incorrect Results When Testing for Overflow After Subtraction of x-y in the Following Program?

Question

The problem I have is concerning practice problem (2.32 - pg.94) from Computer Systems: A Programmers Perspective third edition by Randal Bryant and David O'Hallaron.

The problem is as follows:

You are assigned the task of writing code for a function tsub_ok, with arguments x and y, that will return 1 if computing x-y does not cause overflow. For what values of x and y will this function give incorrect results?

The authors say that the function will give "correct values, except when y is TMin," but when I experiment with the value TMin for y it seems to work fine.

The tsub_ok function is as follows:

/* Determine whether arguments can be subtracted without overflow */

int tsub_ok(int x, int y)
{
    return tadd_ok(x, -y);
}

The tadd_ok function is as follows:

/* Determine whether arguments can be added without overflow */

int tadd_ok(int x, int y) 
{
     int sum = x+y;
     int neg_over = x < 0 && y < 0 && sum >= 0;
     int pos_over = x >= 0 && y >= 0 && sum < 0;
     return !neg_over && !pos_over;
}

Continuing on with the solution explained by the authors in regards to the functions, "we will have -y in the tsub_ok function in the tadd_ok function call also equal to TMin. So, the call to function tadd_ok will indicate overflow when x is negative and no overflow when x is nonnegative. In fact, the opposite is true: tsub_ok(x, TMin) should yield 0 when x is negative and 1 when it is nonnegative."

I tested these functions with a value of TMin for y, and negative and nonnegative values for x. The functions seem to work correctly for these values. The tadd_ok function indicates negative overflow when x is negative with the tsub_ok function returning 0. The tadd_ok function indicates no overflow when x is nonnegative with the tsub_ok function returning 1. Therefore, the functions seem to be working as intended even with TMin for y and negative and nonnegative values for x. So, I am confused how the results are incorrect.

Any help will be much appreciated thank you all in advance.

Answer 1

Consider the case when int is 32-bit two’s complement, int arithmetic is defined to wrap modulo 2³², and tsub_ok is called with tsub_ok(-2147483648, -2147483648).

Then tsub_ok calls tadd_ok(-2147483648, - -2147483648). - -2147483648 wraps (2,147,483,648 is not representable in int; the maximum representable value is 2,147,483,647) to −2,147,483,648. So tadd_ok is effectively called with tadd_ok(-2147483648, -2147483648).

Then tadd_ok computes sum = -2147483648 + -2147483648, which wraps and sets sum to 0.

Then, in int neg_over = x < 0 && y < 0 && sum >= 0;, x is less than zero, y is less than zero, and sum is greater than or equal to 0, so neg_over is set to 1.

Then return !neg_over && !pos_over; causes tadd_ok to return 0, and tsub_ok returns 0 too.

However, this is an incorrect result. Subtracting −2,147,483,648 from −2,147,483,648 yields 0 with no overflow. A correctly working tsub_ok would return 1, to indicate the subtraction is okay.

Therefore tsub_ok is defective.

Answer 2

2's complement range for int will have a larger negative than positive, so if it is 32 bits the valid range for any int will be [-2147483648, 2147483647].

When taking the negative of the max negative value (TMin), it will have no equivalent positive value to represent and will rollover to being the exact same value started with (i.e. -TMin will still result in -2147483648 instead of 2147483648). So when you pass -Tmin into tadd_ok, the incorrect check will be used because pos_over will never be high since y < 0, and neg_over will be used when x<0 - this is the incorrect behavior described.

y=TMin, x < 0 should result in sum > 0 and no rollover (neg_over=false, pos_over=false) however since -Tmin==Tmin, it incorrectly results in neg_over=true

y=Tmin, x > 0 should result in sum > 0 but rollover causes that to fail, so pos_over should be true. Since -Tmin==Tmin, it incorrectly results in pos_over=false