I saw a buggy code in C which was used to check whether addition results in overflow or not. It works fine with char, but gives incorrect answer when arguments are int and I couldn't figure why .
Here's the code with short arguments.
short add_ok( short x, short y ){
short sum = x+y;
return (sum-x==y) && (sum-y==x);
}
This version works fine, problem arise when you change arguments to int ( you can check it with INT_MAX )
Can you see what's wrong in here ?
Because in 2s complement, the integers can be arranged into a circle (in the sense of modulo arithmetic). Adding y and then subtracting y always gets you back where you started (undefined behaviour notwithstanding).
int as R.. correctly states.
sum-x becomes (x+y)-x ?In your code, the addition does not overflow unless int is the same size as short. Due to default promotions, x+y is performed on the values of x and y promoted to int, and then the result is truncated to short in an implementation-defined manner.
Why not do simply: return x+y<=SHRT_MAX && x+y>=SHRT_MIN;
In C programming language, signed integers when converted to smaller signed integers, say char (for the sake of simplicity), are of implementation-defined manner. Even though many systems and programmers assume wrap-around overflow, it is not a standard. So what is wrap-around overflow?
Wrap-around overflow in Two's complement systems happens such that when a value can no longer be presented in the current type, it warps around the highest or lowest number that can be presented. So what does this mean? Take a look.
In signed char, the highest value that can be presented is 127 and the lowest is -128. Then what happens when we do: "char i = 128", is that the value stored in i becomes -128. Because the value was larger than the signed integral type, it wrapped around the lowest value, and if it was "char i = 129", then i will contain -127. Can you see it? Whenever an end reaches its maximum, it wraps around the other end (sign). Vice versa, if "char i = -129", then i will contain 127, and if it is "char i = -130", it will contain 126, because it reached its maximum and wrapped around the highest value.
(highest) 127, 126, 125, ... , -126, -127, -128 (lowest)
If the value is very large, it keeps wrapping around until it reaches a value that can be represented in its range.
UPDATE: the reason why int doesn't work in oppose to char and short is because that when both numbers are added there is a possibility of overflow (regardless of being int, short, or char, while not forgetting integral promotion), but because "short" and char are with smaller sizes than int and because they are promoted to int in expressions, they are represented again without truncation in this line:
return (sum-x==y) && (sum-y==x);
So any overflow is detected as explained later in detail, but when with int, it is not promoted to anything, so overflow will happen. For instance, if I do INT_MAX+1, then the result is INT_MIN, and if I tested for overflow by INT_MIN-1 == INT_MAX, the the result is TRUE! This is because "short" and char get promoted to int, evaluated, and then get truncated (overflowed). However, int get overflowed first and then evaluated, because they are not promoted to a larger size.
Think of char type without promotion, and try to make overflows and check them using the illustration above. You will find it that adding or subtracting values that cause the overflow returns you to where you were. However, this is not what happens in C, because char and "short" are promoted to int, thus overflow is detected, which is not true in int, because it is note promoted to a larger size.
END OF UPDATE
For your question, I checked your code in MinGW and Ubuntu 12.04, seems to work fine. I found later that the code works actually in systems where short is smaller than int, and when values don't exceed int range. This line:
return (sum-x==y) && (sum-y==x);
is true, because "sum-x" and "y" are evaluated as (int) so no wrap-around happens to, where it happened in the previous line (when assigned):
short sum = x+y;
Here is a test. If I entered 32767 for the first and 2 for the second, then when:
short sum = x+y;
sum will contain -32767, because of the wrap-around. However, when:
return (sum-x==y) && (sum-y==x);
"sum-x" (-32767 - 32767) will only be equal to y (2) (then buggy) if wrap-round occurs, but because of integral promotion, it never happen that way and "sum-x" value becomes -65534 which is not equal to y, which then leads to a correct detection.
Here is the code I used:
#include <stdio.h>
short add_ok( short x, short y ){
short sum = x+y;
return (sum-x==y) && (sum-y==x);
}
int main(void) {
short i, ii;
scanf("%hd %hd", &i, &ii);
getchar();
printf("%hd", add_ok(i, ii));
return 0;
}
You need to provide the architecture you are working on, and what are the experimental values you tested, because not everyone faces what you say, and because of the implementation-defined nature of your question.
The compiler probably just replaces all calls to this expression with 1 because it's true in every case. The optimizing routine will perform copy propagation on sum and get
return (y==y) && (x==x);
and then:
return 1
It's true in every case because signed integer overflow is undefined behavior- hence, the compiler is free to guarantee that x+y-y == x and y+x-x == y.
If this was an unsigned operation it would fail similarly- since overflow is just performed as a modulo operation it is fairly easy to prove that
x+y mod SHRT_MAX - y mod SHRT_MAX == x
and similarly for the reverse case.
sum+x with x+y ? also what do you mean by "undefined behavior" ?
SHRT_MAX - x <= yor something like that.intyou can check it with both arguments set asINT_MAX. Withchar, as @R.. says, it doesn't overflow .