Velocity Reviews > Integer Overflow

# Integer Overflow

Tagore
Guest
Posts: n/a

 02-04-2009
I want to make a function that takes two integers and checks whether
their sum overflows or not. I have made following function for this
purpose.
void CheckOverflow(int a, int b)
{
int c=a+b;
if((a>0)&&(b>0)&&(c<0))
printf("Overflow");
else
if((a<0)&&(b<0)&&(c>0))
printf("Overflow");
else
printf("Not Overflow");
}

It is working correctly on my compiler.
Please check the function. Is it reliable?

Peter Nilsson
Guest
Posts: n/a

 02-04-2009
Tagore <(E-Mail Removed)> wrote:
> I want to make a function that takes two integers
> and checks whether their sum overflows or not.
> I have made following function for this purpose.
>
> void CheckOverflow(int a, int b)
> {
> * * * *int c=a+b;

Once overflow happens, all bets are off. You need
to check overflow _without_ generating the overflow.

> * * * *if((a>0)&&(b>0)&&(c<0))
> * * * * * * * printf("Overflow");
> * * * *else
> * * * * * * * if((a<0)&&(b<0)&&(c>0))
> * * * * * * * * * * printf("Overflow");
> * * * * * * * else
> * * * * * * * * * * printf("Not Overflow");
> }
>
> It is working correctly on my compiler.

That's unlucky.

> Please check the function. Is it reliable?

No. Try something like...

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

void CheckOverflow(int a, int b)
{
if ( (a < 0 && b < INT_MIN - a)
|| (a >= 0 && b > INT_MAX - a) )
puts("Overflow");
else
puts("Not Overflow");
}

--
Peter

user923005
Guest
Posts: n/a

 02-05-2009
On Feb 4, 3:38*pm, Peter Nilsson <(E-Mail Removed)> wrote:
> Tagore <(E-Mail Removed)> wrote:
> > I want to make a function that takes two integers
> > and checks whether their sum overflows or not.
> > I have made following function for this purpose.

>
> > void CheckOverflow(int a, int b)
> > {
> > * * * *int c=a+b;

>
> Once overflow happens, all bets are off. You need
> to check overflow _without_ generating the overflow.
>
> > * * * *if((a>0)&&(b>0)&&(c<0))
> > * * * * * * * printf("Overflow");
> > * * * *else
> > * * * * * * * if((a<0)&&(b<0)&&(c>0))
> > * * * * * * * * * * printf("Overflow");
> > * * * * * * * else
> > * * * * * * * * * * printf("Not Overflow");
> > }

>
> > It is working correctly on my compiler.

>
> That's unlucky.
>
> > Please check the function. Is it reliable?

>
> No. Try something like...
>
> * #include <stdio.h>
> * #include <limits.h>
>
> * void CheckOverflow(int a, int b)
> * {
> * * if ( * *(a < *0 && b < INT_MIN - a)
> * * * * *|| (a >= 0 && b > INT_MAX - a) )
> * * * puts("Overflow");
> * * else
> * * * puts("Not Overflow");
> * }
>
> --
> Peter

If we are concerned about integer overflow, why not just choose a
bigger type (e.g. long long).
If long long can overflow, then we can use checks similar to those in
your routine or choose an arbitary precision type.
It seems to me that we have to carefully examine the sign of both
operands so that edge cases (e.g. magnitude of LLONG_MIN can be larger
than LLONG_MAX) and also the operation being performed (+,-,*,/,
>>,<<).

jameskuyper
Guest
Posts: n/a

 02-05-2009
Tagore wrote:
> I want to make a function that takes two integers and checks whether
> their sum overflows or not. I have made following function for this
> purpose.
> void CheckOverflow(int a, int b)
> {
> int c=a+b;
> if((a>0)&&(b>0)&&(c<0))
> printf("Overflow");
> else
> if((a<0)&&(b<0)&&(c>0))
> printf("Overflow");
> else
> printf("Not Overflow");
> }
>
> It is working correctly on my compiler.
> Please check the function. Is it reliable?

Not portably. Your function relies upon the assumption that the
program will continue to execute after the overflow, and makes some
assumptions about what result will be stored in the variable 'c' as a
result. The C standard doesn't say result will be stored in 'c'. It
doesn't even guarantee that your program will continue executing after
the overflow. It just says the behavior of your entire program is
undefined. As a result, it's not even guaranteed that the line prior
to "c=a+b" will be executed. As soon as it becomes inevitable that "c=a
+b" would be executed if the other parts of the program work properly,
the other parts of the program are no longer required to work
CheckOverflow(x,y), then the compiler is allowed to assume that x and
y will never be given values which will cause 'c' to overflow, and to
make optimizations based upon that assumption; optimizations that will
cause your program to malfunction BEFORE the call to CheckOverflow, if
that assumption is violated. That's what it means when the C standard
says "the behavior is undefined".

You could use a larger int type, as user923005 suggested. However, the
C standard doesn't give you any guarantee that there is any type
larger than int. On some machines, using 'int' expressions for this
purpose will be faster than converting to a larger type. In any event,
understanding how to do this without relying upon a larger type will
allow you to do the same thing for intmax_t or long double, if you
need to.

Hint: no matter what values a and b have, a/2 + b/2 cannot overflow.
That hint should point you in the right direction, but you'll have to
think about the boundary cases carefully. The relevant code should use
a%2, b%2, INT_MAX, and INT_MIN in various places.

Richard Tobin
Guest
Posts: n/a

 02-05-2009
In article <(E-Mail Removed)>,
Tagore <(E-Mail Removed)> wrote:
>I want to make a function that takes two integers and checks whether
>their sum overflows or not. I have made following function for this
>purpose.

As others have explained, you can't rely on int overflow doing
anything in particular. If the values are non-negative, you can
convert them to the corresponding unsigned type, and see if the sum is
too big. If they're both negative, you can negate them and do the
same (but bear in mind that for 2s complement the boundary case is
different for negative and positive). If one's positive and the
other's negative, they can't overflow.

-- Richard
--
Please remember to mention me / in tapes you leave behind.

geo
Guest
Posts: n/a

 02-05-2009
On Feb 4, 6:27*pm, Tagore <(E-Mail Removed)> wrote:
> I want to make a function that takes two integers and checks whether
> their sum overflows or not. I have made following function for this
> purpose.
> void CheckOverflow(int a, int b)
> {
> * * * *int c=a+b;
> * * * *if((a>0)&&(b>0)&&(c<0))
> * * * * * * * printf("Overflow");
> * * * *else
> * * * * * * * if((a<0)&&(b<0)&&(c>0))
> * * * * * * * * * * printf("Overflow");
> * * * * * * * else
> * * * * * * * * * * printf("Not Overflow");
>
> }
>
> It is working correctly on my compiler.
> Please check the function. Is it reliable?

Assuming the overwhelmingly most common
2's complement arithmetic, with
signed int and unsigned int types,
C makes it easy to get the overflow bit,
via casts and the true=1, false=0 convention:

overflow=( (unsigned int) (a+b) < (unsigned int) a );

Some will argue that you can always get the trailing bit of
the next longer integer type, e.g., long to long long,
but with long long you are probably dealing with the
longest integer type and yet the cast device will still work:

( (unsigned long long) (a+b) < (unsigned long long) a );

George Marsaglia

Ben Bacarisse
Guest
Posts: n/a

 02-05-2009
geo <(E-Mail Removed)> writes:

> On Feb 4, 6:27Â*pm, Tagore <(E-Mail Removed)> wrote:
>> I want to make a function that takes two integers and checks whether
>> their sum overflows or not. I have made following function for this
>> purpose.
>> void CheckOverflow(int a, int b)
>> {
>> Â* Â* Â* Â*int c=a+b;
>> Â* Â* Â* Â*if((a>0)&&(b>0)&&(c<0))
>> Â* Â* Â* Â* Â* Â* Â* printf("Overflow");
>> Â* Â* Â* Â*else
>> Â* Â* Â* Â* Â* Â* Â* if((a<0)&&(b<0)&&(c>0))
>> Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* printf("Overflow");
>> Â* Â* Â* Â* Â* Â* Â* else
>> Â* Â* Â* Â* Â* Â* Â* Â* Â* Â* printf("Not Overflow");
>>
>> }
>>
>> It is working correctly on my compiler.
>> Please check the function. Is it reliable?

>
> Assuming the overwhelmingly most common
> 2's complement arithmetic, with
> signed int and unsigned int types,
> C makes it easy to get the overflow bit,
> via casts and the true=1, false=0 convention:
>
> overflow=( (unsigned int) (a+b) < (unsigned int) a );

I am a bit baffled by this. Surely the problem case is when a and b
are signed ints as in the OP's question? You seem to agree (why
mention 2's complement otherwise) but I don't see how this test
helps.

--
Ben.

Peter Nilsson
Guest
Posts: n/a

 02-05-2009
geo <(E-Mail Removed)> wrote:
> Tagore <(E-Mail Removed)> wrote:
> > I want to make a function that takes two integers and
> > checks whether their sum overflows or not. I have made
> > following function for this purpose.
> > void CheckOverflow(int a, int b)

<snip>
>
> Assuming the overwhelmingly most common
> 2's complement arithmetic, with
> signed int and unsigned int types,

2's complement is a representation, not an arithmetic.
It does not apply to unsigned integer types. [You're
not the first to be confused by it though.]

> C makes it easy *to get the overflow bit,
> via casts and the true=1, false=0 convention:
>
> overflow=( (unsigned int) (a+b) *< (unsigned int) a );

You haven't avoided the overflow for signed integers.
Even if we allow for the usual silent overflow on 2c
machines, your test will still fail 50% of the time
[e.g. 1 + (-1) is apparently an overflow!]

Perhaps you're thinking of the generic wrap around test
for unsigned types (of rank of unsigned int or higher)...

overflow = (a + b) < a;

--
Peter

Richard Tobin
Guest
Posts: n/a

 02-06-2009
In article <(E-Mail Removed)>,
Peter Nilsson <(E-Mail Removed)> wrote:

>2's complement is a representation, not an arithmetic.
>It does not apply to unsigned integer types.

True, but it has a special relationship to the plain unsigned binary
representation, in that it uses exactly the same algorithms (for
addition and subtraction). If you do unsigned arithmetic and "forget"
that the results might be negative, you get 2s complement.

-- Richard
--
Please remember to mention me / in tapes you leave behind.

CBFalconer
Guest
Posts: n/a

 02-07-2009
Richard Tobin wrote:
> Peter Nilsson <(E-Mail Removed)> wrote:
>
>> 2's complement is a representation, not an arithmetic.
>> It does not apply to unsigned integer types.

>
> True, but it has a special relationship to the plain unsigned
> binary representation, in that it uses exactly the same algorithms
> (for addition and subtraction). If you do unsigned arithmetic and
> "forget" that the results might be negative, you get 2s complement.

However, this is C, and if you do unsigned arithmetic you cannot
get a negative result. To get a negative value you need signed
operands, and the promotion rules will normally convert a single
signed operand into unsigned (to agree with the other operand).

All that means is that you are always open to the uncontrolled
behaviour of overflowing integers, unless the system has
appropriate provisions. If you test operands before operating, you
have to ensure that the tests cannot involve any overflows.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>