Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Integer Overflow

Reply
Thread Tools

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?



 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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 (+,-,*,/,
>>,<<).

 
Reply With Quote
 
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
properly. This sounds paradoxical, but if your code contains the line
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.
 
Reply With Quote
 
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.
 
Reply With Quote
 
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
 
Reply With Quote
 
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.
 
Reply With Quote
 
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
 
Reply With Quote
 
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.
 
Reply With Quote
 
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>
Try the download section.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
integer or long overflow... deancoo C++ 11 03-05-2005 11:13 PM
integer overflow Ashutosh Iddya C Programming 25 04-24-2004 06:16 PM
hhow to detect overflow in integer calculation John Black C++ 1 04-15-2004 05:28 AM
unsigned integer overflow behaviour bartek C++ 3 02-06-2004 09:47 PM
Integer overflow Enrico 'Trippo' Porreca C Programming 9 08-24-2003 10:24 AM



Advertisments