C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Problem with range of type int          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Matthias Hofmann Guest Posted: Mon Nov 14, 2005 9:22 am    Post subject: Problem with range of type int Hello! I am implementing some kind of container that uses an array of integers internally. The integers that are stored in the array are indices into the same array. For example, the array could look like this: int array[] = { 0, 3, 2, 0 }; In that case, array[0] and array[2] contain their own indices, effectively "pointing" at themselves, and array[1] points at array[3], which in turn points at array[0]. Although it demonstrates the basic idea, this discription is actually not quite true. An element stores the index of another element as a nonpositive value, while elements not pointing at another element contain a positive value, whose meaning is not that of an index at all. The above example therefore should rather be as follows: int array[] = { 3, -3, 1, 0 }; As above, array[1] points at array[3], which in turn points at array[0], but array[0] and array[2] are not pointing at any other element. If this sounds weird to you, then let me tell you that I am implementing the Hoshen-Kopelman algorithm as described here: http://splorg.org:8080/people/tobin/projects/hoshenkopelman/ hoshenkopelman.html Now for the actual problem: The public interface of the container I am implementing expects only nonnegative integers, but these values might be converted to their negative counterparts internally. Therefore, each nonnegative integer passed through the interface must be representable as a nonpositive integer. My first guess for a definition of the maximum size of the array was: int MaxSize = INT_MAX; This assumes that type int can represent at least as many negative values as positive ones. Unfortunately, I found no such guarantee in the standard (I was looking mainly at 3.9.1), and if this assumption is wrong, then it is possible to pass a value that cannot be represented internally. My second guess was to define the maximum size of the array as: int MaxSize = min( abs( INT_MIN ), INT_MAX ); This would work if type int could represent at least as many positive values as negative ones. However, this is not true on the systems I know, and it probably won't be on many other ones either. For that reason, the expression is likey to not return the required result, because abs( INT_MIN ) cannot be represented either. Now my question is: How can I implement a function "MaxSize()" that retrieves the maximum size of the array? -- Matthias Hofmann Anvil-Soft, CEO http://www.anvil-soft.com - The Creators of Klomanager http://www.anvil-soft.de - Die Macher des Klomanagers [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrew Koenig Guest Posted: Mon Nov 14, 2005 4:46 pm    Post subject: Re: Problem with range of type int "Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> wrote Quote: Now for the actual problem: The public interface of the container I am implementing expects only nonnegative integers, but these values might be converted to their negative counterparts internally. Therefore, each nonnegative integer passed through the interface must be representable as a nonpositive integer. My first guess for a definition of the maximum size of the array was: int MaxSize = INT_MAX; This assumes that type int can represent at least as many negative values as positive ones. Unfortunately, I found no such guarantee in the standard (I was looking mainly at 3.9.1), and if this assumption is wrong, then it is possible to pass a value that cannot be represented internally. My second guess was to define the maximum size of the array as: int MaxSize = min( abs( INT_MIN ), INT_MAX ); This would work if type int could represent at least as many positive values as negative ones. However, this is not true on the systems I know, and it probably won't be on many other ones either. For that reason, the expression is likey to not return the required result, because abs( INT_MIN ) cannot be represented either. Now my question is: How can I implement a function "MaxSize()" that retrieves the maximum size of the array? In a practical way, I would say that you can rely on the fact that in every C and C++ implementation I have ever seen, every positive integer has a corresponding negative integer. The reverse is not true -- on most implementations, -INT_MIN overflows and -INT_MAX doesn't. So if you are willing for your program not to work on a hypothetical implementation in which some positive integers do not have negative counterparts, you can check that INT_MIN + INT_MAX <= 0 and be done with it. If you want to run even on a machine that fails this test, you could use the sign of INT_MIN + INT_MAX to determine whether to invert the sign of everything in your array. That is, if INT_MIN + INT_MAX > 0, you could use negative numbers to represent indices (once you change their sign, of course), and positive numbers to represent data. Personally, I don't think it's worth it, because I've never seen an implementation on which it's necessary, but at least you can do it if you like. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ben Hutchings Guest Posted: Mon Nov 14, 2005 4:47 pm    Post subject: Re: Problem with range of type int Matthias Hofmann <hofmann (AT) anvil-soft (DOT) com> wrote: <snip> Quote: int MaxSize = min( abs( INT_MIN ), INT_MAX ); This would work if type int could represent at least as many positive values as negative ones. However, this is not true on the systems I know, and it probably won't be on many other ones either. For that reason, the expression is likey to not return the required result, because abs( INT_MIN ) cannot be represented either. Now my question is: How can I implement a function "MaxSize()" that retrieves the maximum size of the array? int MaxSize() { return (INT_MIN + INT_MAX > 0) ? -INT_MIN : INT_MAX; } -- Ben Hutchings Having problems with C++ templates? Your questions may be answered by <http://womble.decadentplace.org.uk/c++/template-faq.html>. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze Guest Posted: Tue Nov 15, 2005 2:34 pm    Post subject: Re: Problem with range of type int Andrew Koenig wrote: Quote: "Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> wrote in message news:4377d276$0$7428$9b4e6d93 (AT) newsread4 (DOT) arcor-online.net... [...] Quote: In a practical way, I would say that you can rely on the fact that in every C and C++ implementation I have ever seen, every positive integer has a corresponding negative integer. The reverse is not true -- on most implementations, -INT_MIN overflows and -INT_MAX doesn't. Isn't this required in C99, which says that negative numbers must be represented as 2's complement, 1's complement or signed magnitude? In all three cases, every positive value has a corresponding negative value. And if it is required in C99, isn't there a good chance that it will be required in some future version of C++? (For that matter, didn't the C committee decide that they could require it because they were convinced that no other implementations have ever or ever will exist?) -- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Matthias Hofmann Guest Posted: Wed Nov 16, 2005 1:06 am    Post subject: Re: Problem with range of type int "Ben Hutchings" <ben-public-nospam (AT) decadentplace (DOT) org.uk> schrieb im Newsbeitrag news:slrndnh8p7.kul.ben-public-nospam (AT) decadentplace (DOT) org.uk... Quote: Matthias Hofmann <hofmann (AT) anvil-soft (DOT) com> wrote: int MaxSize() { return (INT_MIN + INT_MAX > 0) ? -INT_MIN : INT_MAX; } Thanks, this is what I've been looking for! I slightly modified the function to make it more accurate: int MaxSize() { return ( INT_MIN + INT_MAX <= 0 ) ? INT_MAX : ( -INT_MIN + 1 ); } Note that unlike an index, the size of the array need not be representable as a negative value. Therefore, if the magnitude of INT_MAX exceeds that of INT_MIN, the maximum size of the array is one more than the absolute value of INT_MIN. -- Matthias Hofmann Anvil-Soft, CEO http://www.anvil-soft.com - The Creators of Klomanager http://www.anvil-soft.de - Die Macher des Klomanagers [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrey Tarasevich Guest Posted: Wed Nov 16, 2005 9:43 am    Post subject: Re: Problem with range of type int kanze wrote: Quote: In a practical way, I would say that you can rely on the fact that in every C and C++ implementation I have ever seen, every positive integer has a corresponding negative integer. The reverse is not true -- on most implementations, -INT_MIN overflows and -INT_MAX doesn't. Isn't this required in C99, which says that negative numbers must be represented as 2's complement, 1's complement or signed magnitude? ... And if it is required in C99, isn't there a good chance that it will be required in some future version of C++? This is actually already required by C++. It is in C++98. Don't remember about C89/90. Quote: In all three cases, every positive value has a corresponding negative value. Well, "has" here probably means "fits into the number of bits in the value representation of the type". But it doesn't mean that any combination of the value-representing bits is a valid one. Formally, there's nothing that prevents an implementation from treating the combination of bits that corresponds to '-INT_MAX' value as trap representation. -- Best regards, Andrey Tarasevich [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze Guest Posted: Wed Nov 16, 2005 12:51 pm    Post subject: Re: Problem with range of type int Andrey Tarasevich wrote: Quote: kanze wrote: In a practical way, I would say that you can rely on the fact that in every C and C++ implementation I have ever seen, every positive integer has a corresponding negative integer. The reverse is not true -- on most implementations, -INT_MIN overflows and -INT_MAX doesn't. Isn't this required in C99, which says that negative numbers must be represented as 2's complement, 1's complement or signed magnitude? ... And if it is required in C99, isn't there a good chance that it will be required in some future version of C++? This is actually already required by C++. It is in C++98. Where? It was my understanding that the requirements of C++98 were based on those of C90, and C90 certainly doesn't have this requirement. Quote: Don't remember about C89/90. In all three cases, every positive value has a corresponding negative value. Well, "has" here probably means "fits into the number of bits in the value representation of the type". Whose talking about bits? The statements seems obvious to me; put mathematically, for all value i such that i >= 0 and i is representable in an int, -i is also representable in an int. Quote: But it doesn't mean that any combination of the value-representing bits is a valid one. This is, I think, one of the differences between C(99) and C++. Although even in C99, I think that the representation of -1 is allowed to trap in 1's complement and signed magnitude. Quote: Formally, there's nothing that prevents an implementation from treating the combination of bits that corresponds to '-INT_MAX' value as trap Formally, I think you're right for C++, and that the stricter requirements for C99 would forbid this for C99. But I think that part of the motivation for the stricter requirements in C99 is that there has never been an implementation which didn't actually meet them. Practically speaking, barring something so revolutionary new that no one can think of it now, it is probably safe to say that all new architectures will use 2's complement, with no trapping representations, no padding bits, and word sizes of 8*2^n. And legacy architectures represent a closed set, it is theoretically possible to list all members. I think that it is, in fact, safe to say that if such an architecture has not existed in the past, it won't exist in the future, and we won't have to deal with it. C and C++ have decided to exclude non-binary architectures (and base 10 architectures have existed), but at least try to allow all binary architectures, or at least those with sufficient word and memory size. (I've worked on 4 bit processors, and processors with a maximum of 64 bytes of RAM. I don't think it reasonable to expect a C++ compiler for either of them.) -- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.