By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
431,934 Members | 1,677 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 431,934 IT Pros & Developers. It's quick & easy.

signed integer overflow

P: n/a
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
Nov 15 '05 #1
Share this Question
Share on Google+
27 Replies


P: n/a
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
Nov 15 '05 #2

P: n/a
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
Nov 15 '05 #3

P: n/a
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
es*****@acm-dot-org.invalid
Nov 15 '05 #4

P: n/a
REH

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

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.

Nov 15 '05 #5

P: n/a
REH

"Eric Sosman" <es*****@acm-dot-org.invalid> wrote in message
news:cP********************@comcast.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
Nov 15 '05 #6

P: n/a
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
Nov 15 '05 #7

P: n/a
REH wrote:
"CBFalconer" <cb********@yahoo.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.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

Nov 15 '05 #8

P: n/a
REH

"CBFalconer" <cb********@yahoo.com> wrote in message
news:42***************@yahoo.com...
REH wrote:
"CBFalconer" <cb********@yahoo.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
Nov 15 '05 #9

P: n/a
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/

Nov 15 '05 #10

P: n/a
REH

<we******@gmail.com> wrote in message
news:11**********************@g43g2000cwa.googlegr oups.com...
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.


Well, efficiency is relative, but I am currently only concerned with it
being correct and standard compliant. For unsigned multiplication, I am
currently do something like (ignoring 0 for the example):

a = b * c;
if (c != a / b)
overflow();

I'm still deciding how to do signed multiplication, but I leaning towards
doing it as unsigned and fixing the sign afterwards. I would treat the
condition MIN_INT < -MAX_INT as a special case.

thanks,

REH


Nov 15 '05 #11

P: n/a
In article <oE*****************@twister.nyroc.rr.com>,
"REH" <me@you.com> wrote:
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.


C99 only allows 1's comp, 2's comp and sign/magnitude.

An unsigned integer type has N value bits and can represent numbers from
0 to 2^n - 1. A signed integer type has M value bits with M <= N and one
sign bit. It can represent positive numbers from 0 to 2^M - 1. The range
of negative values depends on whether the implementation uses 2's comp
(-2^M to -1) or 1's comp or sign/magnitude (-2^M + 1 to -1).

To be hundred percent portable, you must realise that M = N is possible.
An implementation could use 32 bit 2's complement int (31 bit + sign
bit) and 31 bit unsigned int (31 bit + padding bit). That will obviously
give you more problems. (You can't have 16 bit signed and 15 bit
unsigned int, or 32 bit signed and 31 bit unsigned long, because
unsigned int and unsigned long must have at least 16 and 32 bits).
Nov 15 '05 #12

P: n/a
REH wrote:

<snip over flow prevention in integer arithmetic>
a = b * c;
if (c != a / b)
overflow();

I'm still deciding how to do signed multiplication, but I leaning towards
doing it as unsigned and fixing the sign afterwards. I would treat the
condition MIN_INT < -MAX_INT as a special case.


Do you actually need the full range, or would it be good enough and
simpler to assume MIN_INT==-MAX_INT and potentially flag negative
overflow early?
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.
Nov 15 '05 #13

P: n/a
REH

"Flash Gordon" <sp**@flash-gordon.me.uk> wrote in message
news:2p************@brenda.flash-gordon.me.uk...
REH wrote:

<snip over flow prevention in integer arithmetic>
a = b * c;
if (c != a / b)
overflow();

I'm still deciding how to do signed multiplication, but I leaning towards
doing it as unsigned and fixing the sign afterwards. I would treat the
condition MIN_INT < -MAX_INT as a special case.


Do you actually need the full range, or would it be good enough and
simpler to assume MIN_INT==-MAX_INT and potentially flag negative overflow
early?
--


Hi Flash. Yes, I want to allow the full scale of any numerical type
(though, I am I only concentrating on integral types for now).

REH
Nov 15 '05 #14

P: n/a
REH wrote:
"CBFalconer" <cb********@yahoo.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.


Yes it is. But the information you need is there in <limits.h>.
You will find div(), ldiv(), and lldiv useful. Of course the
proper way to do it is for the actual object code to trap
overflows, which is ridiculously easy on the x86 at least, and most
grown up computer architectures, including the DS9000. On the x86
it only involves an INTO instruction. The standard only says that
the overflow action is implementation defined.

--
"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
Nov 15 '05 #15

P: n/a
In article <42***************@yahoo.com>,
CBFalconer <cb********@worldnet.att.net> wrote:
Of course the
proper way to do it is for the actual object code to trap
overflows, which is ridiculously easy on the x86 at least, and most
grown up computer architectures, including the DS9000.


I thought it was the other way around -- that on the DS9000,
arithmetic overflow triggered a Bengal Programmer Trap.
--
Ceci, ce n'est pas une idée.
Nov 15 '05 #16

P: n/a
REH

"CBFalconer" <cb********@yahoo.com> wrote in message
news:42***************@yahoo.com...
REH wrote:
"CBFalconer" <cb********@yahoo.com> wrote in message

Yes it is. But the information you need is there in <limits.h>.
You will find div(), ldiv(), and lldiv useful. Of course the
proper way to do it is for the actual object code to trap
overflows, which is ridiculously easy on the x86 at least, and most
grown up computer architectures, including the DS9000. On the x86
it only involves an INTO instruction. The standard only says that
the overflow action is implementation defined.


Yes, but I am trying to do it without resorting to assembly language because
my code must run on various platforms and processors. So, I am trying to
avoid causing a trap condition or undefined behavior. Of course, now that I
know the possible formats is quite limited, and not open-ended as I had
feared, it's not that bad. Well, not that bad yet. In the future, I want
to expand the code to handle floating points. Which, I believe, could get
messy...

Thanks,

REH
Nov 15 '05 #17

P: n/a
REH wrote:
<we******@gmail.com> wrote in message
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.


Well, efficiency is relative, [...]


Well if you are willing to perform divisions, then indeed it most
certainly is!
[...] but I am currently only concerned with it
being correct and standard compliant. For unsigned multiplication, I am
currently do something like (ignoring 0 for the example):

a = b * c;
if (c != a / b)
overflow();
That's fine except for when b is zero. How about:

if (0 != b && a/b != c) overflow ();

If you want to skip the cost of the division in many cases, then:

#define HALF_WAY (1 << (sizeof (unsigned)+1)/2)
if ((b|c) >= HALF_WAY &&
((b >= HALF_WAY && c >= HALF_WAY) || (0 != b && a/b != c)))
overflow ();

And of course you can go further by simulating the multiply as 4
smaller multiplies and then checking the high multiply then the sum of
the other 3 for overflow.

All this for what can be done in basically 1 to 3 more instructions in
most assembly languages.
I'm still deciding how to do signed multiplication, but I leaning towards
doing it as unsigned and fixing the sign afterwards.
Probably best.
[...] I would treat the condition MIN_INT < -MAX_INT as a special case.


Right, you have no choice.

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

Nov 15 '05 #18

P: n/a
REH wrote:

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?


First question: I can't think of any 100% safe way to
test whether a data object holds a trap representation --
because if it does, simply trying to look at it may cause
the trap. (You could inspect the bytes as an array of
unsigned char and compare them to known trap representations,
but that begs the question.)

Second question: Ordinary arithmetic will never produce
a trap representation from valid operands unless something
like overflow or division by zero occurs.

As a practical matter, you can probably rely on integers
using two's complement with no trap representations. Other
schemes are allowed by the Standard and have been used in
real computers, but those designs have become as rare as the
ivory-billed woodpecker, if not the dodo. If you can write
your code without relying on such an assumption, fine -- but
you probably needn't bend over backwards to cater to what is
nowadays an awfully remote possibility. (Besides, where are
you going to find test systems of all six architectural flavors,
five exceedingly rare if they exist at all?) Go ahead and
assume asymmetrical two's complement, and insert

#include <limits.h>
#if INT_MIN + INT_MAX != -1
/* Not asymmetrical two's complement */
#error "This short-sighted code can't cope!"
#endif

.... so the code will kick up a ruckus instead of delivering
wrong answers if someone ever tries it on an exotic machine.

(I hope you realize the risk I'm taking to offer practical
advice: I'm likely to lose my Pedant's License over this breach
of orthodoxy! "Cardinal Fang, fetch ... the Comfy Chair!")

--
Eric Sosman
es*****@acm-dot-org.invalid
Nov 15 '05 #19

P: n/a
Eric Sosman wrote:
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 would be "minus two-to-the-(N-1)th" surely. Two's complement 100 in
our three-bit model is -4.
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.

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Nov 15 '05 #20

P: n/a
REH

<we******@gmail.com> wrote in message
news:11**********************@f14g2000cwb.googlegr oups.com...
REH wrote:
Well, efficiency is relative, [...]
Well if you are willing to perform divisions, then indeed it most
certainly is!


My point was under many circumstances, that won't matter. People spend way
to much time worrying about speed before it is even an issue. If, for
example, a real-time system can meet all of its scheduled dead-lines with
the required amount of reserved processor time, then what does it matter if
it takes twice as long as it could without the checks? Or, take a
command-line tool executed from the shell. Whether it takes 1ms or 100ms,
it is still "instantaneous" to the user.
[...] but I am currently only concerned with it
being correct and standard compliant. For unsigned multiplication, I am
currently do something like (ignoring 0 for the example):

a = b * c;
if (c != a / b)
overflow();
That's fine except for when b is zero.

Yes, reread what I wrote above.
How about:

if (0 != b && a/b != c) overflow ();

If you want to skip the cost of the division in many cases, then:

#define HALF_WAY (1 << (sizeof (unsigned)+1)/2)
if ((b|c) >= HALF_WAY &&
((b >= HALF_WAY && c >= HALF_WAY) || (0 != b && a/b != c)))
overflow ();

And of course you can go further by simulating the multiply as 4
smaller multiplies and then checking the high multiply then the sum of
the other 3 for overflow.

All this for what can be done in basically 1 to 3 more instructions in
most assembly languages.

I prefer simpler, easy to read code. I worry about speed when its an issue.
I don't plan to use this code in generating an FFT. For such code, with a
lot going on in tight loops, it would probably matter. In many other types
of code, I doubt you would notice any difference.

REH
Nov 15 '05 #21

P: n/a
"REH" <me@you.com> writes:
"CBFalconer" <cb********@yahoo.com> wrote in message
news:42***************@yahoo.com...
REH wrote:
"CBFalconer" <cb********@yahoo.com> wrote in message

Yes it is. But the information you need is there in <limits.h>.
You will find div(), ldiv(), and lldiv useful. Of course the
proper way to do it is for the actual object code to trap
overflows, which is ridiculously easy on the x86 at least, and most
grown up computer architectures, including the DS9000. On the x86
it only involves an INTO instruction. The standard only says that
the overflow action is implementation defined.


Yes, but I am trying to do it without resorting to assembly language because
my code must run on various platforms and processors. So, I am trying to
avoid causing a trap condition or undefined behavior. Of course, now that I
know the possible formats is quite limited, and not open-ended as I had
feared, it's not that bad. Well, not that bad yet. In the future, I want
to expand the code to handle floating points. Which, I believe, could get
messy...


If speed isn't too much of a concern, you might consider using an
arbitrary-precision arithmetic package, perhaps GNU MP.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 15 '05 #22

P: n/a
On Sat, 13 Aug 2005 20:09:35 +0000, CBFalconer wrote:
REH wrote:
"CBFalconer" <cb********@yahoo.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.


This seems overly complex, (testing overflow on a+b) how about:

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

or
overflow = (a >= 0) ? b > MAX_INT-a : b < MIN_INT-a;
For testing overflow of a-b that changes to:

if (b >= 0) {
if (a < MIN_INT + b) overflow();
} else {
if (a > MAX_INT + b) overflow();
}

These do work when MIN_INT < -MAX_INT.

Testing for multiplication oveflow is certainly trickier to do fully on
signed values with the possibility of MIN_INT < -MAX_INT, and MAX_UINT ==
MAX_INT. Any code that might calculate MIN_INT/-1 needs to be looked at
carefully.

Lawrence

Nov 15 '05 #23

P: n/a
cs
On Sat, 13 Aug 2005 14:41:24 GMT, "REH" <me@you.com> wrote:
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.

is it just for unsigned? or for signed too?
;int over()
over:
mov eax, 0
adc eax, 0
ret

y=a+b;
if(over()) overflow();

or
if( (y=a+b), over()) overflow();
if( (z=a-b), over()) overflow();
Nov 15 '05 #24

P: n/a
"cs" <n@ss.g> wrote in message
news:h5********************************@4ax.com...
....
is it just for unsigned? or for signed too?
;int over()
over:
mov eax, 0
adc eax, 0
ret

y=a+b;
if(over()) overflow();

or
if( (y=a+b), over()) overflow();
if( (z=a-b), over()) overflow();


It's for unsigned only. You need to check the OVerflow flag instead of CarrY
when adding/subtracting signed integers on x86. And it's trickier when one
operand is signed but the other isn't.

Alex
Nov 15 '05 #25

P: n/a
"Eric Sosman" <es*****@acm-dot-org.invalid> wrote in message
news:5N*****************************************@c omcast.com...
....
As a practical matter, you can probably rely on integers
using two's complement with no trap representations. Other
schemes are allowed by the Standard and have been used in
real computers, but those designs have become as rare as the
ivory-billed woodpecker, if not the dodo.
Quite right. There's no reason to implement signed numbers as 1's complement
or sign+magnitude. The same full adder circuit will deliver the correct sum
(or difference, if properly wired for subtraction) for both unsigned and 2's
complement signed numbers. The only thing I can think of where the 1's
complement or sign+magnitude scheme would be employed (both these schemes
are practically equivalent in their inefficiency, though 1's complement is
somewhat closer to 2's complement) is when this stuff is already implemented
in some floating point unit like one IEEE-754-compliant (whose floating
point types have the sign+magnitude representation) and integer math is
derived from it for free (well, except for slowness). But that's usually
something stupid to do. The thing is, integer signed
addition/subtraction/comparison/negation/magnitude and multiplication
procedures are all very simple. Even multiplication of signed 2's complement
numbers can be done directly using the Booth's algorithm, which is very
efficient in hardware and with one extra bit in operands (this bit is
normally hidden in hardware) it can produce products for unsigned*unsigned,
signed*signed, and unsigned*signed forms of the MUL (or whatever)
instruction.
(Besides, where are
you going to find test systems of all six architectural flavors,
five exceedingly rare if they exist at all?) Go ahead and
assume asymmetrical two's complement, and insert


I've never seen 1's complemented and sign+module implementations myself.
Their time has gone.

Btw, regarding the padding bits... Do I correctly understand that the
padding bits must not be between sign bit and the others making up the
magnitude/value, i.e. MSB->PPPSVVV<-LSB?

Alex
Nov 15 '05 #26

P: n/a
"Alexei A. Frounze" wrote:
.... snip ...
I've never seen 1's complemented and sign+module implementations
myself. Their time has gone.


You see sign-magnitude all the time in the floating point package.

--
"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
Nov 15 '05 #27

P: n/a
"CBFalconer" <cb********@yahoo.com> wrote in message
news:43***************@yahoo.com...
"Alexei A. Frounze" wrote:
I've never seen 1's complemented and sign+module implementations
myself. Their time has gone.


You see sign-magnitude all the time in the floating point package.


There -- yes, but not in integers.

Alex
Nov 15 '05 #28

This discussion thread is closed

Replies have been disabled for this discussion.