458,208 Members | 1,215 Online Need help? Post your question and get tips & solutions from a community of 458,208 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
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 unsignedint 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 Yevgen Muntyan said: >>Is it correct that number of value bits in int and unsignedint representation may be the same? Both int and unsigned int are guaranteed to take the same amount ofstorage. In the signed type, one of the bits is reserved as a signbit. Thus, if you don't count sign as a value bit, signed int hasone 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 San Diego Supercomputer Center <* "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 Richard Heathfield wrote: >>Yevgen Muntyan said:Is it correct that number of value bits in int and unsignedint representation may be the same?Both int and unsigned int are guaranteed to take the same amount ofstorage. In the signed type, one of the bits is reserved as a signbit. Thus, if you don't count sign as a value bit, signed int hasone value bit fewer than unsigned int. This is only true if number of padding bits is the same in int andunsigned. 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 Consider a CPU that supports signed but not unsigned arithmetic.It'snot 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 intmight have the same layout, but treating the sign bit as a paddingbit. 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 ) 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 San Diego Supercomputer Center <* "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

 P: n/a Keith Thompson wrote: Yevgen Muntyan Keith Thompson wrote: [...] >>Consider a CPU that supports signed but not unsigned arithmetic.It'snot 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 intmight have the same layout, but treating the sign bit as a paddingbit. This gives us UINT_MAX == INT_MAX. Yep (and we can add same amount of padding bits into int and unsignedfor the same effect, and it's be the only possible case whenUINT_MAX == INT_MAX). Question is: doesn't the standard explicitlydisallow 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 ispossible, 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 tospecial-case INT_MIN multipliers (in addition to fancy replacementfor 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 ) 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 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 typical32-bit two's-complement system). (I'm using "**" as a shorthand forexponentiation.)Now modify the implementation in *only* the following ways: Change UINT_MAX (in ) 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, andbitwise operations will yield exactly the same representations as theydid before (and the same values in cases other than the new traprepresentations). The only difference is that some cases that werewell-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 San Diego Supercomputer Center <* "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 >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

 P: n/a Peter Nilsson wrote: Yevgen Muntyan Is it correct that number of value bits in int and unsignedint 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 mathematicalsense), 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 inunsigned 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 unsignedint representation may be the same? Yes. >If it is so, then INT_MINmay 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 Yevgen Muntyan wrote: >>Hey,Is it correct that number of value bits in int and unsignedint representation may be the same? Yes. >>If it is so, then INT_MINmay 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 San Diego Supercomputer Center <* "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 pete wrote: >>Yevgen Muntyan wrote:Hey,Is it correct that number of value bits in int and unsignedint representation may be the same?Yes.If it is so, then INT_MINmay 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 implementsthat assuming -LONG_MIN fits into unsigned long (actually it seemsit's assuming LONG_MIN is -LONG_MAX - 1). I may be wrong,but it seems sensible that implementations do not try to useportable 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 Keith Thompson Why would any special-case checking be needed? Signed overflowinvokes 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 typical32-bit two's-complement system). (I'm using "**" as a shorthand forexponentiation.)Now modify the implementation in *only* the following ways: Change UINT_MAX (in ) 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, andbitwise operations will yield exactly the same representations as theydid before (and the same values in cases other than the new traprepresentations). The only difference is that some cases that werewell-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 = p = p = p = 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 (40°39.22'N, 111°50.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

 P: n/a Jack Klein said: On Tue, 13 Mar 2007 09:29:15 +0000, 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 ofstorage. In the signed type, one of the bits is reserved as a signbit. Thus, if you don't count sign as a value bit, signed int has onevalue 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>Yevgen Muntyan said:Hey,Is it correct that number of value bits in int and unsignedint representation may be the same?Both int and unsigned int are guaranteed to take the same amount ofstorage. In the signed type, one of the bits is reserved as a signbit. Thus, if you don't count sign as a value bit, signed int has onevalue bit fewer than unsigned int. While I don't know of any architecture where this is not true, it isnot 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 Keith Thompson >Why would any special-case checking be needed? Signed overflowinvokes 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 typical32-bit two's-complement system). (I'm using "**" as a shorthand forexponentiation.)Now modify the implementation in *only* the following ways: Change UINT_MAX (in ) 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, andbitwise operations will yield exactly the same representations as theydid before (and the same values in cases other than the new traprepresentations). The only difference is that some cases that werewell-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 San Diego Supercomputer Center <* "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

 P: n/a Peter Nilsson wrote: > pete 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

### This discussion thread is closed

Replies have been disabled for this discussion. 