signed integer overflow

[REH]

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

[Richard Heathfield]

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

[CBFalconer]

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.c om, 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

[Eric Sosman]

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;l kUy97609i]*&^%$");
}

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
es*****@acm-dot-org.invalid

[REH]

"CBFalconer " <cb********@yah oo.com> wrote in message
news:42******** ******@yahoo.co m...

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.

[REH]

"Eric Sosman" <es*****@acm-dot-org.invalid> wrote in message
news:cP******** ************@co mcast.com...

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

[Richard Heathfield]

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

[CBFalconer]

REH wrote:

"CBFalconer " <cb********@yah oo.com> 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.c om, 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

[REH]

"CBFalconer " <cb********@yah oo.com> wrote in message
news:42******** *******@yahoo.c om...

REH wrote:

"CBFalconer " <cb********@yah oo.com> 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

[websnarf]

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/