Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > signed integer overflow

Reply
Thread Tools

signed integer overflow

 
 
REH
Guest
Posts: n/a
 
      08-13-2005
I asked this on c.l.c++, but they suggested you folks may be better able to
answer.

Basically, I am trying to write code to detect overflows in signed integer
math. I am trying to make it as efficient as possible without resorting to
assembly language, and without causing undefined behavior. That, of course,
means catching the overflow before it happens.

What I asked was (stripping any relevance to C++):

If the range of an integer type is not symmetrical around zero
(i.e., 2's comp.), is it safe to assume that the extra value(s) is one
the negative side?

The reason is I am currently thinking it may be easiest to do the math as
unsigned, check for overflow, and then fixup the sign. I would handle the
fact that the range may not be symmetrical around zero as a corner case.

What I learned from the folks on the C++ group:

1) C and C++ Standards are equivalent on the treatment of signed/unsigned
values. I had thought (mistakenly, I guess) that they differed slightly.

2) That the Standard (should that always be capitalized?), C++ at least,
allows only three formats: 1's comp., 2's comp., and sign/magnitude. I
didn't realize this and thought that any format was allowed, and I was
worried about my code working correctly on some weird format I've never
heard of. If that is true, then my only "corner case" is with the maximum
(in magnitude) negative value in 2's complement.

I had thought this was a problem that had been beaten to death in both
languages, but I could find nothing on the web. Well, that's not true. The
stuff I did find always assumed that signed overflow was well behaved and
worked as unsigned.

Not relevant here, but I am attempting to write a class template that
behaves like Ada's ranged types (and subtypes). That is, for example, if X
+ Y overflows or strays out of its assigned range, it will throw an
exception.

Thanks,

REH


 
Reply With Quote
 
 
 
 
Richard Heathfield
Guest
Posts: n/a
 
      08-13-2005
REH wrote:

> If the range of an integer type is not symmetrical around zero
> (i.e., 2's comp.), is it safe to assume that the extra value(s) is one
> the negative side?


Yes. The Standard makes it clear that signed integer types are made up of a
sign bit, at least a certain number of value bits (15 for short int and
int, and 31 for long), and at least zero padding bits. Because the
representation of non-negative values of signed integer types is the same
as for unsigned integer types, it is easy to see that there can be at most
only one "extra" value, and that value must be negative because the sign
bit will have to be set in order to get the extra bit combination. Think of
(heretical!) three-bit ints, with the first of them being the sign bit:

Bit pattern Unsigned value Signed value
000 0 0
001 1 1
010 2 2
011 3 3

All remaining values must have the high bit set, and thus must be negative
in a signed type (irrespective of whether it's ones' complement, two's
complement, or sign-and-mag).

> What I learned from the folks on the C++ group:
>
> 1) C and C++ Standards are equivalent on the treatment of signed/unsigned
> values. I had thought (mistakenly, I guess) that they differed slightly.


No, they're equivalent TTBOMKAB.

>
> 2) That the Standard (should that always be capitalized?), C++ at least,
> allows only three formats: 1's comp., 2's comp., and sign/magnitude.


It's the same for C.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
mail: rjh at above domain
 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      08-13-2005
REH wrote:
>

.... snip ...
>
> If the range of an integer type is not symmetrical around zero
> (i.e., 2's comp.), is it safe to assume that the extra value(s)
> is one the negative side?
>
> The reason is I am currently thinking it may be easiest to do the
> math as unsigned, check for overflow, and then fixup the sign. I
> would handle the fact that the range may not be symmetrical around
> zero as a corner case.


No need to guess. For any integer type, the limiting values are
available in <limits.h>.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson


 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      08-13-2005
Richard Heathfield wrote:
> [...] Think of
> (heretical!) three-bit ints, with the first of them being the sign bit:
>
> Bit pattern Unsigned value Signed value
> 000 0 0
> 001 1 1
> 010 2 2
> 011 3 3
>
> All remaining values must have the high bit set, and thus must be negative
> in a signed type (irrespective of whether it's ones' complement, two's
> complement, or sign-and-mag).


100 could be zero, which is not negative:

if (minus_zero < 0 || minus_zero > 0 || minus_zero != 0) {
puts("This isn't C!");
puts("(Or else minus zero is a trap representation,\n"
"and you're only seeing this as a consequence\n"
"of undefined behavKUHYTDjn;lkUy97609i]*&^%$");
}

Although the example is flawed, the O.P.'s supposition is
correct: If the set of values is not symmetrical about zero,
the "extra" value must be negative:

- Signed magnitude: The "extra" encoding is 10...0, which
is either "minus zero" or a trap representation. Even if
"minus zero" is allowed, its value is zero so the range
is symmetrical.

- Ones' complement: The "extra" encoding is 11...1, which
is either "minus zero" or a trap. As before, the range is
symmetrical.

- Two's complement: The "extra" encoding is 10...0, which
is either minus two-to-the-Nth or a trap. If it's a trap
the range is symmetrical; otherwise, the range is
asymmetrical and the "extra" value is negative.

That covers all the representations permitted by the Standard,
and the only case in which the range is asymmetrical has more
negative than positive values.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
REH
Guest
Posts: n/a
 
      08-13-2005

"CBFalconer" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
>
> No need to guess. For any integer type, the limiting values are
> available in <limits.h>.
>

Thanks, CB, but just knowing the limits does not make it trivial to
determine whether a given arithmetic operation will overflow.



 
Reply With Quote
 
REH
Guest
Posts: n/a
 
      08-13-2005

"Eric Sosman" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Although the example is flawed, the O.P.'s supposition is
> correct: If the set of values is not symmetrical about zero,
> the "extra" value must be negative:
>
> - Signed magnitude: The "extra" encoding is 10...0, which
> is either "minus zero" or a trap representation. Even if
> "minus zero" is allowed, its value is zero so the range
> is symmetrical.
>
> - Ones' complement: The "extra" encoding is 11...1, which
> is either "minus zero" or a trap. As before, the range is
> symmetrical.
>
> - Two's complement: The "extra" encoding is 10...0, which
> is either minus two-to-the-Nth or a trap. If it's a trap
> the range is symmetrical; otherwise, the range is
> asymmetrical and the "extra" value is negative.
>
> That covers all the representations permitted by the Standard,
> and the only case in which the range is asymmetrical has more
> negative than positive values.
>

Thank you Eric. Yours and Richard's posts were very helpful. Is there a
simple test to determine whether the minus zero or trap is used? Or, is
that unnecessary to know as long as the values do not overflow?

REH


 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      08-13-2005
Eric Sosman wrote:

> Richard Heathfield wrote:
>>
>> All remaining values must have the high bit set, and thus must be
>> negative in a signed type (irrespective of whether it's ones' complement,
>> two's complement, or sign-and-mag).

>
> 100 could be zero, which is not negative:


Oh, pooh.

Thank you for the correction!

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
mail: rjh at above domain
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      08-13-2005
REH wrote:
> "CBFalconer" <(E-Mail Removed)> wrote in message
>>
>> No need to guess. For any integer type, the limiting values are
>> available in <limits.h>.

>
> Thanks, CB, but just knowing the limits does not make it trivial to
> determine whether a given arithmetic operation will overflow.


Yes it does. A preliminary calculation with one operand and the
limit will yield the maximum value for the other operand, so you
can avoid an overflow with a single comparison.

if (a > 0) {
if (b > 0)
if (a > (MAX_INT - b)) overflow();
}
else if (a < 0) {
if (b < 0)
if (a < (MIN_INT - b)) overflow();
}
etc.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

 
Reply With Quote
 
REH
Guest
Posts: n/a
 
      08-13-2005

"CBFalconer" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> REH wrote:
>> "CBFalconer" <(E-Mail Removed)> wrote in message
>>>

> Yes it does. A preliminary calculation with one operand and the
> limit will yield the maximum value for the other operand, so you
> can avoid an overflow with a single comparison.
>
> if (a > 0) {
> if (b > 0)
> if (a > (MAX_INT - b)) overflow();
> }
> else if (a < 0) {
> if (b < 0)
> if (a < (MIN_INT - b)) overflow();
> }
> etc.


You are assuming just simple addition and subtraction. It is more complex
for other operations.

REH


 
Reply With Quote
 
websnarf@gmail.com
Guest
Posts: n/a
 
      08-13-2005
REH wrote:
> You are assuming just simple addition and subtraction. It is more complex
> for other operations.


Indeed it is. Testing for multiplication overflow cannot really be
done efficiently in C, except for lower sized integers.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

 
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
Can negating a non-negative signed integer value ever overflow? Alex Fraser C Programming 8 03-08-2006 05:41 PM
signed integer overflow REH C++ 2 08-13-2005 02:17 PM
conversion of signed integer to unsigned integer junky_fellow@yahoo.co.in C Programming 14 06-18-2005 02:29 PM
Signed Adder without overflow Nemesis VHDL 4 05-25-2005 07:31 PM
overflow with signed and unsigned values Zaki VHDL 2 06-30-2004 02:35 PM



Advertisments