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

UINT_MAX == INT_MAX possible?

P: n/a
Hey,

Is it correct that number of value bits in int and unsigned
int representation may be the same? If it is so, then INT_MIN
may be -(INT_MAX+1) (in mathematical sense), i.e. abs(INT_MIN)
is not representable in int or unsigned int. Or is it guaranteed
that magnitude of any int value fits in unsigned int?

Yevgen
Mar 13 '07 #1
Share this Question
Share on Google+
24 Replies


P: n/a
Yevgen Muntyan said:
Hey,

Is it correct that number of value bits in int and unsigned
int representation may be the same?
Both int and unsigned int are guaranteed to take the same amount of
storage. In the signed type, one of the bits is reserved as a sign bit.
Thus, if you don't count sign as a value bit, signed int has one value
bit fewer than unsigned int.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Mar 13 '07 #2

P: n/a
Richard Heathfield wrote:
Yevgen Muntyan said:
>Hey,

Is it correct that number of value bits in int and unsigned
int representation may be the same?

Both int and unsigned int are guaranteed to take the same amount of
storage. In the signed type, one of the bits is reserved as a sign bit.
Thus, if you don't count sign as a value bit, signed int has one value
bit fewer than unsigned int.
This is only true if number of padding bits is the same in int and
unsigned. Is it always the case?

Yevgen
Mar 13 '07 #3

P: n/a
Yevgen Muntyan <mu****************@tamu.eduwrites:
Richard Heathfield wrote:
>Yevgen Muntyan said:
>>Is it correct that number of value bits in int and unsigned
int representation may be the same?
Both int and unsigned int are guaranteed to take the same amount of
storage. In the signed type, one of the bits is reserved as a sign
bit. Thus, if you don't count sign as a value bit, signed int has
one value bit fewer than unsigned int.

This is only true if number of padding bits is the same in int and
unsigned. Is it always the case?
It needn't be.

Consider a CPU that supports signed but not unsigned arithmetic. It's
not very realistic, but it's possible. Assume an N-bit word size.
Then int might have N-1 value bits and 1 sign bit, and unsigned int
might have the same layout, but treating the sign bit as a padding
bit. This gives us UINT_MAX == INT_MAX.

This can't happen for signed char vs. unsigned char, because unsigned
char is specifically forbidden to have padding bits.

--
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."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 13 '07 #4

P: n/a
Keith Thompson wrote:
Yevgen Muntyan <mu****************@tamu.eduwrites:
>Richard Heathfield wrote:
>>Yevgen Muntyan said:
Is it correct that number of value bits in int and unsigned
int representation may be the same?
Both int and unsigned int are guaranteed to take the same amount of
storage. In the signed type, one of the bits is reserved as a sign
bit. Thus, if you don't count sign as a value bit, signed int has
one value bit fewer than unsigned int.
This is only true if number of padding bits is the same in int and
unsigned. Is it always the case?

It needn't be.

Consider a CPU that supports signed but not unsigned arithmetic. It's
not very realistic, but it's possible. Assume an N-bit word size.
Then int might have N-1 value bits and 1 sign bit, and unsigned int
might have the same layout, but treating the sign bit as a padding
bit. This gives us UINT_MAX == INT_MAX.
Yep (and we can add same amount of padding bits into int and unsigned
for the same effect, and it's be the only possible case when
UINT_MAX == INT_MAX). Question is: doesn't the standard explicitly
disallow it? And the second question, if UINT_MAX == INT_MAX is
possible, is it forbidden to have two's complement arithmetic then
(so that -INT_MIN is not representable in unsigned).
If it's not forbidden, then signed type overflow checking needs to
special-case INT_MIN multipliers (in addition to fancy replacement
for ABS macro).

Yevgen
Mar 13 '07 #5

P: n/a
Yevgen Muntyan <mu****************@tamu.eduwrites:
Keith Thompson wrote:
[...]
>Consider a CPU that supports signed but not unsigned arithmetic.
It's
not very realistic, but it's possible. Assume an N-bit word size.
Then int might have N-1 value bits and 1 sign bit, and unsigned int
might have the same layout, but treating the sign bit as a padding
bit. This gives us UINT_MAX == INT_MAX.

Yep (and we can add same amount of padding bits into int and unsigned
for the same effect, and it's be the only possible case when
UINT_MAX == INT_MAX). Question is: doesn't the standard explicitly
disallow it?
I don't believe so. (If it does, someone will quote chapter and verse
shortly.)

And the second question, if UINT_MAX == INT_MAX is
possible, is it forbidden to have two's complement arithmetic then
(so that -INT_MIN is not representable in unsigned).
No, it's not forbidden; there's no specific requirement for -INT_MIN
to be representable in unsigned.
If it's not forbidden, then signed type overflow checking needs to
special-case INT_MIN multipliers (in addition to fancy replacement
for ABS macro).
Why would any special-case checking be needed? Signed overflow
invokes undefined behavior; no checking of any kind is required.

Consider an existing implementation with 32-bit int, INT_MIN ==
-2**31, INT_MAX == 2**31-1, UINT_MAX == 2**32-1 (i.e., a very typical
32-bit two's-complement system). (I'm using "**" as a shorthand for
exponentiation.)

Now modify the implementation in *only* the following ways:

Change UINT_MAX (in <limits.h>) to 2**31-1, equal to INT_MAX.

Document that unsigned int has a single padding bit, and that any
unsigned int representation in which that padding bit is set is a
trap representation.

and leave *everything else* as it is. Arithmetic, logical, and
bitwise operations will yield exactly the same representations as they
did before (and the same values in cases other than the new trap
representations). The only difference is that some cases that were
well-defined are now undefined behavior.

The new implementation is still conforming. It's perverse, in that it
fails to define behaviors that it could perfectly well define, and it
could break some non-portable code that *assumes* unsigned int has no
padding bits, but I don't believe it would violate the standard in any
way.

--
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."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 13 '07 #6

P: n/a
Keith Thompson wrote:
Yevgen Muntyan <mu****************@tamu.eduwrites:
And the second question, if UINT_MAX == INT_MAX is
possible, is it forbidden to have two's complement arithmetic then
(so that -INT_MIN is not representable in unsigned).

No, it's not forbidden; there's no specific requirement for -INT_MIN
to be representable in unsigned.
If it's not forbidden, then signed type overflow checking needs to
special-case INT_MIN multipliers (in addition to fancy replacement
for ABS macro).

Why would any special-case checking be needed? Signed overflow
invokes undefined behavior; no checking of any kind is required.
Extra checking may be required in user code if undefined behaviour is
to be avoided.

Mar 13 '07 #7

P: n/a
Keith Thompson wrote:
Yevgen Muntyan <mu****************@tamu.eduwrites:
>Keith Thompson wrote:
[...]
>>Consider a CPU that supports signed but not unsigned arithmetic.
It's
not very realistic, but it's possible. Assume an N-bit word size.
Then int might have N-1 value bits and 1 sign bit, and unsigned int
might have the same layout, but treating the sign bit as a padding
bit. This gives us UINT_MAX == INT_MAX.
Yep (and we can add same amount of padding bits into int and unsigned
for the same effect, and it's be the only possible case when
UINT_MAX == INT_MAX). Question is: doesn't the standard explicitly
disallow it?

I don't believe so. (If it does, someone will quote chapter and verse
shortly.)

> And the second question, if UINT_MAX == INT_MAX is
possible, is it forbidden to have two's complement arithmetic then
(so that -INT_MIN is not representable in unsigned).

No, it's not forbidden; there's no specific requirement for -INT_MIN
to be representable in unsigned.
>If it's not forbidden, then signed type overflow checking needs to
special-case INT_MIN multipliers (in addition to fancy replacement
for ABS macro).

Why would any special-case checking be needed?
"Overflow checking" meant "checking if x*y is not representable
in int for int x and y", I missed word "multiplication".
Signed overflow
invokes undefined behavior; no checking of any kind is required.

Consider an existing implementation with 32-bit int, INT_MIN ==
-2**31, INT_MAX == 2**31-1, UINT_MAX == 2**32-1 (i.e., a very typical
32-bit two's-complement system). (I'm using "**" as a shorthand for
exponentiation.)

Now modify the implementation in *only* the following ways:

Change UINT_MAX (in <limits.h>) to 2**31-1, equal to INT_MAX.

Document that unsigned int has a single padding bit, and that any
unsigned int representation in which that padding bit is set is a
trap representation.

and leave *everything else* as it is. Arithmetic, logical, and
bitwise operations will yield exactly the same representations as they
did before (and the same values in cases other than the new trap
representations). The only difference is that some cases that were
well-defined are now undefined behavior.

The new implementation is still conforming.
Well, this is the question, if it's true. If standard doesn't explicitly
say it's not, then yes it's conforming. Say, take a usual implementation
and add a padding bit to char types. All the arithmetic operations will
work as before, but it wouldn't be conforming because it would violate
the standard which says there are no padding bits in char (you said so
at least).

Yevgen
Mar 13 '07 #8

P: n/a
Yevgen Muntyan <mu****************@tamu.eduwrites:
Keith Thompson wrote:
[...]
>Consider an existing implementation with 32-bit int, INT_MIN ==
-2**31, INT_MAX == 2**31-1, UINT_MAX == 2**32-1 (i.e., a very typical
32-bit two's-complement system). (I'm using "**" as a shorthand for
exponentiation.)
Now modify the implementation in *only* the following ways:
Change UINT_MAX (in <limits.h>) to 2**31-1, equal to INT_MAX.
Document that unsigned int has a single padding bit, and that any
unsigned int representation in which that padding bit is set is a
trap representation.
and leave *everything else* as it is. Arithmetic, logical, and
bitwise operations will yield exactly the same representations as they
did before (and the same values in cases other than the new trap
representations). The only difference is that some cases that were
well-defined are now undefined behavior.
The new implementation is still conforming.

Well, this is the question, if it's true. If standard doesn't explicitly
say it's not, then yes it's conforming. Say, take a usual implementation
and add a padding bit to char types. All the arithmetic operations will
work as before, but it wouldn't be conforming because it would violate
the standard which says there are no padding bits in char (you said so
at least).
To be clear, I said that there are no padding bits in unsigned char.
I don't recall what the standard says about padding bits in signed
char (or plain char if it happens to be signed).

--
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."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 13 '07 #9

P: n/a
Yevgen Muntyan wrote:
Keith Thompson wrote:
>Yevgen Muntyan <mu****************@tamu.eduwrites:
>>Keith Thompson wrote:
....
>The new implementation is still conforming.

Well, this is the question, if it's true. If standard doesn't explicitly
say it's not, then yes it's conforming. Say, take a usual implementation
and add a padding bit to char types. All the arithmetic operations will
work as before, but it wouldn't be conforming because it would violate
the standard which says there are no padding bits in char (you said so
at least).
"char" above should read "unsigned char".

Yevgen

Mar 13 '07 #10

P: n/a
Yevgen Muntyan wrote:
>
Hey,

Is it correct that number of value bits in int and unsigned
int representation may be the same?
Yes.
If it is so, then INT_MIN
may be -(INT_MAX+1) (in mathematical sense), i.e. abs(INT_MIN)
is not representable in int or unsigned int.
Correct. That's the tricky part when implementing itoa.
Or is it guaranteed
that magnitude of any int value fits in unsigned int?
No.
(-INT_MIN) is not guaranteed to be within the range of any integer type.

This is the guarantee:
INT_MAX is guaranteed to be less than or equal to UINT_MAX.

It is perfectly allowable to have CHAR_BIT equal to 16,
and sizeof(int) equal to 2,
with type int having 15 padding bits
and type unsigned having 16 padding bits.
All that would yield
UINT_MAX equal to 0xffff
INT_MAX equal to 0xffff.

--
pete
Mar 13 '07 #11

P: n/a
Yevgen Muntyan <muntyan.removet...@tamu.eduwrote:
Is it correct that number of value bits in int and unsigned
int representation may be the same?
Yes, 6.2.6.2p2 makes it rather obvious. It also allows
UINT_MAX 2 * INT_MAX + 1.
If it is so, then INT_MIN may be -(INT_MAX+1) (in mathematical
sense),
Yes, but although that too follows from 6.2.6.2p2 (in C99), it
has nothing to do with the number of value bits in an unsigned
int. Rather, it has to do with the possible value of the sign
bit in two's complement representation.
i.e. abs(INT_MIN) is not representable in int or unsigned int.
Why does this disturb you? The negation of INT_MIN is generally
not representable as an int, although it's surprising the number
of people who think it is (and that it necessarily produces
INT_MIN.)
Or is it guaranteed that magnitude of any int value fits in
unsigned int?
Nope, only INT_MIN is a (possible) exception.

That said, there is at least one regular in comp.std.c (not
a committee member) who believes the standard allows odd ranges
for signed int, e.g. -33000..64000, in which case -INT_MAX
overflows. There are a number of areas where the standard
defines C in terms of 'overriding' paragraphs, however the
'precedence' of paragraphs isn't always as obvious as it
should be.

Of course, the standard is a balance between formal rigorous
definition and Plain English.

--
Peter

Mar 13 '07 #12

P: n/a
Peter Nilsson wrote:
Yevgen Muntyan <muntyan.removet...@tamu.eduwrote:
>Is it correct that number of value bits in int and unsigned
int representation may be the same?

Yes, 6.2.6.2p2 makes it rather obvious. It also allows
UINT_MAX 2 * INT_MAX + 1.
Obvious? It's obvious that UINT_MAX >= INT_MAX, and seems
sensible that UINT_MAX may be any greater than INT_MAX.
But it's not obvious that UINT_MAX may be equal to INT_MAX.
It's obvious only after you have read whole standard and
made sure nowhere standard doesn't say UINT_MAX INT_MAX.
For instance, UCHAR_MAX is always greater than SCHAR_MAX.
>If it is so, then INT_MIN may be -(INT_MAX+1) (in mathematical
sense),

Yes, but although that too follows from 6.2.6.2p2 (in C99),
Yes.
it
has nothing to do with the number of value bits in an unsigned
int.
Yes it does. If number of value bits in unsigned int is greater
than number of value bits in int, then unsigned can represent
magnitude of any int value, regardless of representation choice.
Rather, it has to do with the possible value of the sign
bit in two's complement representation.
If it's zero, then we have non-negative number which is
the same in unsigned type. Of course non-zero sign bit
is the interesting case.
>i.e. abs(INT_MIN) is not representable in int or unsigned int.

Why does this disturb you? The negation of INT_MIN is generally
not representable as an int, although it's surprising the number
of people who think it is (and that it necessarily produces
INT_MIN.)
Not as an int, but as an unsigned int. To me it's weird,
it means there may not be an ABS() macro or function (which would
get you the absolute value).
>Or is it guaranteed that magnitude of any int value fits in
unsigned int?

Nope, only INT_MIN is a (possible) exception.

That said, there is at least one regular in comp.std.c (not
a committee member) who believes the standard allows odd ranges
for signed int, e.g. -33000..64000, in which case -INT_MAX
overflows.
Doesn't 6.2.6.2 say it's impossible? There are N value bits,
positive range is [1..2^N-1]; negative range depends on
representation, but there is still not much choice, it's
either [-(2^N-1)..-1] or [-2^N..-1].
There are a number of areas where the standard
defines C in terms of 'overriding' paragraphs, however the
'precedence' of paragraphs isn't always as obvious as it
should be.
If something contradicts something, then it's a bug. But
if one place complements another one (like with unsigned char),
then it's just hard-to-read-it-all issue. And hence my question.

Best regards,
Yevgen
Mar 13 '07 #13

P: n/a
pete wrote:
Yevgen Muntyan wrote:
>Hey,

Is it correct that number of value bits in int and unsigned
int representation may be the same?

Yes.
>If it is so, then INT_MIN
may be -(INT_MAX+1) (in mathematical sense), i.e. abs(INT_MIN)
is not representable in int or unsigned int.

Correct. That's the tricky part when implementing itoa.
I looked at glibc, it implements atoi using strtol, and implements
that assuming -LONG_MIN fits into unsigned long (actually it seems
it's assuming LONG_MIN is -LONG_MAX - 1). I may be wrong,
but it seems sensible that implementations do not try to use
portable code.

Best regards,
Yevgen
Mar 13 '07 #14

P: n/a
Yevgen Muntyan <mu****************@tamu.eduwrites:
pete wrote:
>Yevgen Muntyan wrote:
>>Hey,

Is it correct that number of value bits in int and unsigned
int representation may be the same?
Yes.
>>If it is so, then INT_MIN
may be -(INT_MAX+1) (in mathematical sense), i.e. abs(INT_MIN)
is not representable in int or unsigned int.
Correct. That's the tricky part when implementing itoa.

I looked at glibc, it implements atoi using strtol, and implements
that assuming -LONG_MIN fits into unsigned long (actually it seems
it's assuming LONG_MIN is -LONG_MAX - 1). I may be wrong,
but it seems sensible that implementations do not try to use
portable code.
I don't think glibc is designed to work with any compiler other than
gcc; it's free to assume two's-complement representation, no padding
bits, CHAR_BIT==8, etc. A completely portable implementation of
atoi() or strtol() would be more work -- work that's not necessary for
glibc.

--
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."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 13 '07 #15

P: n/a
Keith Thompson wrote:
Yevgen Muntyan <mu****************@tamu.eduwrites:
>pete wrote:
>>Yevgen Muntyan wrote:
Hey,

Is it correct that number of value bits in int and unsigned
int representation may be the same?
Yes.

If it is so, then INT_MIN
may be -(INT_MAX+1) (in mathematical sense), i.e. abs(INT_MIN)
is not representable in int or unsigned int.
Correct. That's the tricky part when implementing itoa.
I looked at glibc, it implements atoi using strtol, and implements
that assuming -LONG_MIN fits into unsigned long (actually it seems
it's assuming LONG_MIN is -LONG_MAX - 1). I may be wrong,
but it seems sensible that implementations do not try to use
portable code.

I don't think glibc is designed to work with any compiler other than
gcc; it's free to assume two's-complement representation, no padding
bits, CHAR_BIT==8, etc. A completely portable implementation of
atoi() or strtol() would be more work -- work that's not necessary for
glibc.
Sure, I was rather wondering about "That's the tricky part when
implementing itoa." - are there portable implementations of it
where INT_MIN is a tricky part. As I said, I guess that C
implementations do not implement it in a portable way. Maybe
some usual programmers did implement portable atoi, just for fun.

Yevgen
Mar 14 '07 #16

P: n/a
In article <ln************@nuthaus.mib.org>
Keith Thompson <ks***@mib.orgwrote:
>Why would any special-case checking be needed? Signed overflow
invokes undefined behavior; no checking of any kind is required.
Indeed, because signed arithmetic is loosely defined, one should
be able to get away with a lot of perversity (e.g., on the DS9k).

On the other hand:
>Consider an existing implementation with 32-bit int, INT_MIN ==
-2**31, INT_MAX == 2**31-1, UINT_MAX == 2**32-1 (i.e., a very typical
32-bit two's-complement system). (I'm using "**" as a shorthand for
exponentiation.)

Now modify the implementation in *only* the following ways:

Change UINT_MAX (in <limits.h>) to 2**31-1, equal to INT_MAX.

Document that unsigned int has a single padding bit, and that any
unsigned int representation in which that padding bit is set is a
trap representation.

and leave *everything else* as it is. Arithmetic, logical, and
bitwise operations will yield exactly the same representations as they
did before (and the same values in cases other than the new trap
representations). The only difference is that some cases that were
well-defined are now undefined behavior.
This implementation is not conforming. For instance:

unsigned int u = UINT_MAX; /* ie 0x7fffffff */
u += 3; /* must put 2 in u */

Hence, if you make the above change to a typical 32-bit machine,
you must also make changes so that unsigned arithmetic masks out
the top bit.

Note, however, that:

unsigned char *p = (unsigned char *)&u;
p[0] = p[1] = p[2] = p[3] = 0xff;

does put a trap representation into "u"; the implementation need
not mask off the top bit in this case.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
Mar 14 '07 #17

P: n/a
On Tue, 13 Mar 2007 09:29:15 +0000, Richard Heathfield
<rj*@see.sig.invalidwrote in comp.lang.c:
Yevgen Muntyan said:
Hey,

Is it correct that number of value bits in int and unsigned
int representation may be the same?

Both int and unsigned int are guaranteed to take the same amount of
storage. In the signed type, one of the bits is reserved as a sign bit.
Thus, if you don't count sign as a value bit, signed int has one value
bit fewer than unsigned int.
While I don't know of any architecture where this is not true, it is
not a requirement of the C standard. See 6.2.6.2 paragraph 2.

It requires that the number of value bits in a signed type (and this
does not include the sign bit) be less than or equal to the number of
value bits in the corresponding unsigned type.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
Mar 14 '07 #18

P: n/a
Jack Klein said:
On Tue, 13 Mar 2007 09:29:15 +0000, Richard Heathfield
<rj*@see.sig.invalidwrote in comp.lang.c:
>Yevgen Muntyan said:
Hey,

Is it correct that number of value bits in int and unsigned
int representation may be the same?

Both int and unsigned int are guaranteed to take the same amount of
storage. In the signed type, one of the bits is reserved as a sign
bit. Thus, if you don't count sign as a value bit, signed int has one
value bit fewer than unsigned int.

While I don't know of any architecture where this is not true, it is
not a requirement of the C standard. See 6.2.6.2 paragraph 2.
Thanks, Jack. My explanation was based on 3.1.2.5 Types:
"For each of the signed integer types, there is a corresponding (but
different) unsigned integer type (designated with the keyword unsigned)
that uses the same amount of storage (including sign information)
and has the same alignment requirements. The range of nonnegative
values of a signed integer type is a subrange of the corresponding
unsigned integer type, and the representation of the same value in
each type is the same."

It seems that 6.2.6.2(2) of C99 waxes rather more lyrically.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Mar 14 '07 #19

P: n/a
Richard Heathfield wrote:
Jack Klein said:
>On Tue, 13 Mar 2007 09:29:15 +0000, Richard Heathfield
<rj*@see.sig.invalidwrote in comp.lang.c:
>>Yevgen Muntyan said:

Hey,

Is it correct that number of value bits in int and unsigned
int representation may be the same?
Both int and unsigned int are guaranteed to take the same amount of
storage. In the signed type, one of the bits is reserved as a sign
bit. Thus, if you don't count sign as a value bit, signed int has one
value bit fewer than unsigned int.
While I don't know of any architecture where this is not true, it is
not a requirement of the C standard. See 6.2.6.2 paragraph 2.

Thanks, Jack. My explanation was based on 3.1.2.5 Types:
"For each of the signed integer types, there is a corresponding (but
different) unsigned integer type (designated with the keyword unsigned)
that uses the same amount of storage (including sign information)
and has the same alignment requirements. The range of nonnegative
values of a signed integer type is a subrange of the corresponding
unsigned integer type, and the representation of the same value in
each type is the same."
Then you simply don't know how the bits are used, and what ranges are.
C89 doesn't mention padding bits but it also doesn't say that UINT_MAX
is 2^(sizeof(int)*CHAR_BIT)-1, or does it? Does it even say that
UINT_MAX must be 2^n_value_bits-1?
It seems that 6.2.6.2(2) of C99 waxes rather more lyrically.
Or more precisely?

Yevgen
Mar 14 '07 #20

P: n/a
Chris Torek <no****@torek.netwrites:
In article <ln************@nuthaus.mib.org>
Keith Thompson <ks***@mib.orgwrote:
>>Why would any special-case checking be needed? Signed overflow
invokes undefined behavior; no checking of any kind is required.

Indeed, because signed arithmetic is loosely defined, one should
be able to get away with a lot of perversity (e.g., on the DS9k).

On the other hand:
>>Consider an existing implementation with 32-bit int, INT_MIN ==
-2**31, INT_MAX == 2**31-1, UINT_MAX == 2**32-1 (i.e., a very typical
32-bit two's-complement system). (I'm using "**" as a shorthand for
exponentiation.)

Now modify the implementation in *only* the following ways:

Change UINT_MAX (in <limits.h>) to 2**31-1, equal to INT_MAX.

Document that unsigned int has a single padding bit, and that any
unsigned int representation in which that padding bit is set is a
trap representation.

and leave *everything else* as it is. Arithmetic, logical, and
bitwise operations will yield exactly the same representations as they
did before (and the same values in cases other than the new trap
representations). The only difference is that some cases that were
well-defined are now undefined behavior.

This implementation is not conforming. For instance:

unsigned int u = UINT_MAX; /* ie 0x7fffffff */
u += 3; /* must put 2 in u */

Hence, if you make the above change to a typical 32-bit machine,
you must also make changes so that unsigned arithmetic masks out
the top bit.
Quite right, thanks.

Removing the wording about trap representations doesn't help; you
still need, for example, printf("%u\n", UINT_MAX + 3) to print 2,
which means the implementation really has to do some extra work,
either to zero the padding bit or to ignore it.

I think you can still play some tricks by defining padding bits for
*signed* int, though. For example, if you change INT_MAX from 2**31-1
to 2**30-1, and document that signed int has a padding bit, and that
setting that bit creates a trap representation, I think you can still
have a conforming implementation. (A trap representation, of course,
isn't required to cause a trap; it just invokes undefined behavior --
which signed overflow does anyway.)

If Chris doesn't shoot this one down, I'll begin to suspect that I'm
right.

--
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."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 14 '07 #21

P: n/a
Yevgen Muntyan wrote:
Sure, I was rather wondering about "That's the tricky part when
implementing itoa." - are there portable implementations of it
where INT_MIN is a tricky part. As I said, I guess that C
implementations do not implement it in a portable way. Maybe
some usual programmers did implement portable atoi, just for fun.
To me, itoa is just exercize 3-4
from the latest edition of the K&R book,
(or 3-3 in the original K&R book).
In that context, itoa should be implemented portably.

void i_to_a(int n, char *s)
{
int tenth, min_offset;
char *p, swap;

min_offset = -INT_MAX n;
if (0 n) {
n += min_offset;
n = -n;
*s++ = '-';
}
p = s;
tenth = n;
do {
tenth /= 10;
*p++ = (char)(n - 10 * tenth + '0');
n = tenth;
} while (tenth != 0);
*s = (char)(*s + min_offset);
*p-- = '\0';
while (p s) {
swap = *s;
*s++ = *p;
*p-- = swap;
}
}

--
pete
Mar 14 '07 #22

P: n/a
pete <pfil...@mindspring.comwrote:
...
To me, itoa is just exercize 3-4
from the latest edition of the K&R book,
(or 3-3 in the original K&R book).
In that context, itoa should be implemented portably.

void i_to_a(int n, char *s)
{
int tenth, min_offset;
char *p, swap;

min_offset = -INT_MAX n;
Personally, I prefer (n < -INT_MAX), because it makes
better 'left to right' sense to put numbers in ascending
order. [Of course, some people are confused by -5 < -4.]
if (0 n) {
n += min_offset;
n = -n;
*s++ = '-';
}
p = s;
Not sure why you have 'tenth' in the following...
tenth = n;
do {
tenth /= 10;
*p++ = (char)(n - 10 * tenth + '0');
n = tenth;
} while (tenth != 0);
do { *p++ = '0' + (n % 10); } while (n /= 10);

Are you just trying to avoid 2 'division' instructions?
*s = (char)(*s + min_offset);
*p-- = '\0';
while (p s) {
swap = *s;
*s++ = *p;
*p-- = swap;
}

}
Can't say I like the redundant (char) casts either. Looks like
you've been using Jacob's compiler on high redundant warning
mode. ;)

--
Peter

Mar 16 '07 #23

P: n/a
Peter Nilsson wrote:
>
pete <pfil...@mindspring.comwrote:
...
To me, itoa is just exercize 3-4
from the latest edition of the K&R book,
(or 3-3 in the original K&R book).
In that context, itoa should be implemented portably.

void i_to_a(int n, char *s)
{
int tenth, min_offset;
char *p, swap;

min_offset = -INT_MAX n;

Personally, I prefer (n < -INT_MAX), because it makes
better 'left to right' sense to put numbers in ascending
order. [Of course, some people are confused by -5 < -4.]
The "less than" operator
dropped out of my repertoire a few years ago
for a few very weak reasons.
>
if (0 n) {
n += min_offset;
n = -n;
*s++ = '-';
}
p = s;

Not sure why you have 'tenth' in the following...
tenth = n;
do {
tenth /= 10;
*p++ = (char)(n - 10 * tenth + '0');
n = tenth;
} while (tenth != 0);

do { *p++ = '0' + (n % 10); } while (n /= 10);

Are you just trying to avoid 2 'division' instructions?
Yes.
*s = (char)(*s + min_offset);
*p-- = '\0';
while (p s) {
swap = *s;
*s++ = *p;
*p-- = swap;
}

}

Can't say I like the redundant (char) casts either. Looks like
you've been using Jacob's compiler on high redundant warning
mode. ;)
Not Jacob's,
but you are correct in that I am kowtowing
to my compiler at high warning level.

--
pete
Mar 16 '07 #24

P: n/a
Peter Nilsson wrote:
>
pete <pfil...@mindspring.comwrote:
...
To me, itoa is just exercize 3-4
from the latest edition of the K&R book,
(or 3-3 in the original K&R book).
In that context, itoa should be implemented portably.

void i_to_a(int n, char *s)
Not sure why you have 'tenth' in the following...
tenth = n;
do {
tenth /= 10;
*p++ = (char)(n - 10 * tenth + '0');
n = tenth;
} while (tenth != 0);

do { *p++ = '0' + (n % 10); } while (n /= 10);

Are you just trying to avoid 2 'division' instructions?
Yes and but I also may have been influenced
by a previously written version of itoa which had more use
for the "tenth" variable.

void (itoa)(int n, char *s);
static char *sput_u(unsigned n, char *s);
static char *sput_up1(unsigned n, char *s);

void (itoa)(int n, char *s)
{
if (0 n) {
*s++ = '-';
*sput_up1(-(n + 1), s) = '\0';
} else {
*sput_u(n, s) = '\0';
}
}

static char *sput_u(unsigned n, char *s)
{
unsigned digit, tenth;

tenth = n / 10;
digit = n - 10 * tenth;
if (tenth != 0) {
s = sput_u(tenth, s);
}
*s = (char)(digit + '0');
return s + 1;
}

static char *sput_up1(unsigned n, char *s)
{
unsigned digit, tenth;

tenth = n / 10;
digit = n - 10 * tenth;
if (digit == 9) {
if (tenth != 0) {
s = sput_up1(tenth, s);
} else {
*s++ = '1';
}
*s = '0';
} else {
if (tenth != 0) {
s = sput_u(tenth, s);
}
*s = (char)(digit + '1');
}
return s + 1;
}

--
pete
Mar 19 '07 #25

This discussion thread is closed

Replies have been disabled for this discussion.