Question about unsigned integer wrap
Tom Torfs
The standard says the following about unsigned integer types:
A computation involving unsigned operands can never overflow, because a
result that cannot be represented by the resulting unsigned integer type
is reduced modulo the number that is one greater than the largest value
that can be represented by the resulting unsigned integer type.
However, someone is claiming that something like unsigned x = 0; x--; is
not guaranteed to wrap back to UINT_MAX, in other words he interprets this
paragraph as only handling overflow for too large values.
I disagree (correct me if I'm wrong) but am having some trouble pointing
him to a phrase in the standard or an official interpretation that makes
this clear. Any suggestions ?
greetings,
Tom
tomt...@village.uunet.be
Paul Jarc
> The standard says the following about unsigned integer types:
>
> A computation involving unsigned operands can never overflow, because a
> result that cannot be represented by the resulting unsigned integer type
> is reduced modulo the number that is one greater than the largest value
> that can be represented by the resulting unsigned integer type.
>
> However, someone is claiming that something like unsigned x = 0; x--; is
> not guaranteed to wrap back to UINT_MAX, in other words he interprets this
> paragraph as only handling overflow for too large values.
While the standard does use "underflow" as distinct from "overflow",
reduction modulo n happens, according to the above text, for all
unrepresentable values. Reduction is not defined by the standard, so
the mathematical definition applies, and by that definition, the
operation affects negative numbers as well as those greater than the
modulus.
I'm not aware of any wording in the standard that would make this
clearer, but I haven't looked much.
paul
Barry Margolin
Tom Torfs <tomt...@village.uunet.be> wrote:
>Hello All!
>
>The standard says the following about unsigned integer types:
>
> A computation involving unsigned operands can never overflow, because a
> result that cannot be represented by the resulting unsigned integer type
>
> is reduced modulo the number that is one greater than the largest value
>
> that can be represented by the resulting unsigned integer type.
>
>However, someone is claiming that something like unsigned x = 0; x--; is
>not guaranteed to wrap back to UINT_MAX, in other words he interprets this
>paragraph as only handling overflow for too large values.
>
>him to a phrase in the standard or an official interpretation that makes
>this clear. Any suggestions ?
The clause that contains "can never overflow" should not be taken to be an
exhaustive list of the consequences of the requirement that results be
reduced modulo the largest value. There are many things that are true
because of that requirement, and the standard just happens to mention one
of them explicitly, but that doesn't mean that the rest aren't true.
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Clive D.W. Feather
>Hello All!
>
>The standard says the following about unsigned integer types:
>
> A computation involving unsigned operands can never overflow, because a
> result that cannot be represented by the resulting unsigned integer type
> is reduced modulo the number that is one greater than the largest value
> that can be represented by the resulting unsigned integer type.
>
>However, someone is claiming that something like unsigned x = 0; x--; is
>not guaranteed to wrap back to UINT_MAX, in other words he interprets this
>paragraph as only handling overflow for too large values.
>
>I disagree (correct me if I'm wrong) but am having some trouble pointing
>him to a phrase in the standard or an official interpretation that makes
>this clear. Any suggestions ?
What's wrong with the above text:
* -1 is not representable in unsigned int;
* therefore -1 is reduced modulo UINT_MAX+1 ...
* to get the value (1 + (UINT_MAX+1)-1) = UINT_MAX.
"reduced modulo" is not the same as "decreased by subtracting".
--
Clive D.W. Feather | Internet Expert | Work: <cl...@demon.net>
Tel: +44 20 8371 1138 | Demon Internet Ltd. | Home: <cl...@davros.org>
Fax: +44 20 8371 1037 | | Web: <http://www.davros.org>
Written on my laptop; please observe the Reply-To address
Richard Heathfield
<19966...@f516.n292.z2.fidonet.org>...
> Hello All!
>
> The standard says the following about unsigned integer types:
>
> A computation involving unsigned operands can never overflow, because
a
> result that cannot be represented by the resulting unsigned integer
type
>
> is reduced modulo the number that is one greater than the largest
value
>
> that can be represented by the resulting unsigned integer type.
>
> However, someone is claiming that something like unsigned x = 0; x--; is
> not guaranteed to wrap back to UINT_MAX, in other words he interprets
this
> paragraph as only handling overflow for too large values.
>
> I disagree (correct me if I'm wrong) but am having some trouble pointing
> him to a phrase in the standard or an official interpretation that makes
> this clear. Any suggestions ?
>
> Tom
> tomt...@village.uunet.be
>
>
Sorry, I don't have the old standard but here's a snippage from C9X (N869).
Maybe it will help - it's in the "Conversions" section:
6.3.1.3 Signed and unsigned integers
[#1] When a value with integer type is converted to another
integer type other than _Bool, if the value can be
represented by the new type, it is unchanged.
[#2] Otherwise, if the new type is unsigned, the value is
converted by repeatedly adding or subtracting one more than
the maximum value that can be represented in the new type
until the value is in the range of the new type.
Here's my (rather optimistic) reasoning:
unsigned int x = 0;
x--;
equates to
unsigned int x = 0;
x = x - 1U; /* Okay, so I'm flying a kite here... :-) */
The expression x - 1U would have to undergo conversion in order to be
stored in x, as it would not otherwise 'fit'. Thus, #2 (above) takes
effect; note the phrase "repeatedly /adding/ or subtracting" (my
'italics').
Two problems with this:
a) it's rather a subjective interpretation.
b) it's from C9X.
I hope you can discount b) by finding a parallel phrase in the old
standard; as for a), well... you decide.
HTH
--
Richard Heathfield
The bug stops here.
Morris M. Keesan
>Hello All!
>
>The standard says the following about unsigned integer types:
>
> A computation involving unsigned operands can never overflow, because a
> result that cannot be represented by the resulting unsigned integer type
>
> is reduced modulo the number that is one greater than the largest value
>
> that can be represented by the resulting unsigned integer type.
>
>However, someone is claiming that something like unsigned x = 0; x--; is
>not guaranteed to wrap back to UINT_MAX, in other words he interprets this
>paragraph as only handling overflow for too large values.
>
>I disagree (correct me if I'm wrong) but am having some trouble pointing
>him to a phrase in the standard or an official interpretation that makes
>this clear. Any suggestions ?
This almost does it;
Second paragraph of 6.2.1.2:
"When a signed integer is converted to an unsigned integer with equal
or greater size, if the value .. is nonnegative, its value is
unchanged. Otherwise ... the value is converted to unsigned by
adding to it one greater than the largest number that can be
represented in the unsigned integer type."
First, you have to convince yourself that there's an intermediate result
which is ((int)-1). It's clear from the above that either
x = -1;
or
x = 0; x = x - 1;
results in (x == UINT_MAX), but at first glance I'm not sure I've
convinced myself that "x--" has the same guarantees, because as a
unary operator "--" doesn't cause "the usual arithmetic conversions".
--
Morris M. Keesan -- kee...@world.std.com -- http://world.std.com/~keesan/
Mathew Hendry
Keesan) wrote:
>Tom Torfs <tomt...@village.uunet.be> wrote:
>> A computation involving unsigned operands can never overflow, because a
>> result that cannot be represented by the resulting unsigned integer type
>> is reduced modulo the number that is one greater than the largest value
>> that can be represented by the resulting unsigned integer type.
>>
>>However, someone is claiming that something like unsigned x = 0; x--; is
>>not guaranteed to wrap back to UINT_MAX, in other words he interprets this
>>paragraph as only handling overflow for too large values.
>>
>>I disagree (correct me if I'm wrong) but am having some trouble pointing
>>him to a phrase in the standard or an official interpretation that makes
>>this clear. Any suggestions ?
>
>...
>
>which is ((int)-1). It's clear from the above that either
> x = -1;
>or
> x = 0; x = x - 1;
>results in (x == UINT_MAX), but at first glance I'm not sure I've
>convinced myself that "x--" has the same guarantees, because as a
>unary operator "--" doesn't cause "the usual arithmetic conversions".
Conversions don't need to occur for the above clause to apply.
-- Mat.
Peter Seebach
Tom Torfs <tomt...@village.uunet.be> wrote:
>The standard says the following about unsigned integer types:
> A computation involving unsigned operands can never overflow, because a
> result that cannot be represented by the resulting unsigned integer type
> is reduced modulo the number that is one greater than the largest value
> that can be represented by the resulting unsigned integer type.
>However, someone is claiming that something like unsigned x = 0; x--; is
>not guaranteed to wrap back to UINT_MAX, in other words he interprets this
>paragraph as only handling overflow for too large values.
He's wrong. I'm pretty sure "reduced" means "shoved back into range" in this
context. :)
>I disagree (correct me if I'm wrong) but am having some trouble pointing
>him to a phrase in the standard or an official interpretation that makes
>this clear. Any suggestions ?
Just point at him and laugh until he goes away. It's easier than arguing
points.
-s
--
Copyright 1999, All rights reserved. Peter Seebach / se...@plethora.net
C/Unix wizard, Pro-commerce radical, Spam fighter. Boycott Spamazon!
Will work for interesting hardware. http://www.plethora.net/~seebs/
Visit my new ISP <URL:http://www.plethora.net/> --- More Net, Less Spam!