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]

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.

 

[Yevgen Muntyan]

Yevgen Muntyan said:


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]

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.

 

[Yevgen Muntyan]

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]

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.

 

[Guest]

No, it's not forbidden; there's no specific requirement for -INT_MIN
to be representable in unsigned.


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]

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]

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

 

[Yevgen Muntyan]

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]

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.

 

[Peter Nilsson]

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.

 

[Yevgen Muntyan]

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.

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.

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

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]

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]

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.

 

[Yevgen Muntyan]

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

 

[Chris Torek]

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

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.

 

[Jack Klein]

Yevgen Muntyan said:


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.

 

[Richard Heathfield]

Jack Klein said:

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.

 

[Yevgen Muntyan]

Jack Klein said:


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