UINT_MAX == INT_MAX possible?

[Yevgen Muntyan]

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

[Richard Heathfield]

Re: UINT_MAX == INT_MAX possible?

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.

[Yevgen Muntyan]

Re: UINT_MAX == INT_MAX possible?

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

[Keith Thompson]

Re: UINT_MAX == INT_MAX possible?

Yevgen Muntyan <muntyan.remove this@tamu.eduwr ites:

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_Keit h) kst-u@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"

[Yevgen Muntyan]

Re: UINT_MAX == INT_MAX possible?

Keith Thompson wrote:

Yevgen Muntyan <muntyan.remove this@tamu.eduwr ites:

>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

[Keith Thompson]

Re: UINT_MAX == INT_MAX possible?

Yevgen Muntyan <muntyan.remove this@tamu.eduwr ites:

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_Keit h) kst-u@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"

[=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=]

Re: UINT_MAX == INT_MAX possible?

Keith Thompson wrote:

Yevgen Muntyan <muntyan.remove this@tamu.eduwr ites:

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.

[Yevgen Muntyan]

Re: UINT_MAX == INT_MAX possible?

Keith Thompson wrote:

Yevgen Muntyan <muntyan.remove this@tamu.eduwr ites:

>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

[Keith Thompson]

Re: UINT_MAX == INT_MAX possible?

Yevgen Muntyan <muntyan.remove this@tamu.eduwr ites:

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
>representation s). 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_Keit h) kst-u@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"

[Yevgen Muntyan]

Re: UINT_MAX == INT_MAX possible?

Yevgen Muntyan wrote:

Keith Thompson wrote:

>Yevgen Muntyan <muntyan.remove this@tamu.eduwr ites:

>>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

[pete]

Re: UINT_MAX == INT_MAX possible?

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

[Peter Nilsson]

Re: UINT_MAX == INT_MAX possible?

Yevgen Muntyan <muntyan.remove t...@tamu.eduwr ote:

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

[Yevgen Muntyan]

Re: UINT_MAX == INT_MAX possible?

Peter Nilsson wrote:

Yevgen Muntyan <muntyan.remove t...@tamu.eduwr ote:

>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

[Yevgen Muntyan]

Re: UINT_MAX == INT_MAX possible?

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

[Keith Thompson]

Re: UINT_MAX == INT_MAX possible?

Yevgen Muntyan <muntyan.remove this@tamu.eduwr ites:

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_Keit h) kst-u@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"