C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  How to determine the number of "power of two" enum entries?          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Francis Rammeloo Guest Posted: Wed Dec 07, 2005 2:22 pm    Post subject: How to determine the number of "power of two" enum entries? Hello, How can I determine the number of "power of two" enum entries? Following code explains my question: enum ActionCategory { eActionCategory_Color = 0x00000001, eActionCategory_Page = 0x00000002, eActionCategory_Prepress = 0x00000004, eActionCategory_Image = 0x00000008, eActionCategory_Text = 0x00000010, eActionCategory_Transform = 0x00000020, eActionCategory_Font = 0x00000040, eActionCategory_PDFX = 0x00000080, eActionCategory_Output = 0x00000100, eActionCategory_Document = 0x00000200, eActionCategory_Other = 0x00000400, eActionCategory_All = eActionCategory_Color Quote: eActionCategory_Page eActionCategory_Prepress eActionCategory_Image eActionCategory_Text eActionCategory_Transform eActionCategory_Font eActionCategory_PDFX eActionCategory_Output eActionCategory_Document eActionCategory_Other, eNumberOfCategories = ??? ^-- How can I determine the number of categories at compile time? }; Mathematically this is easy, is it also possible to let the compiler calculate the value? I suspect this is a common problem. Is there also a common solution? Thank you very much in advance for all feedback Best regards, Francis (Note to moderators: I hope I didn't double post, I had some problems posting with my new gmail account and am now using my old account ) [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Robert Kindred Guest Posted: Wed Dec 07, 2005 6:45 pm    Post subject: Re: How to determine the number of "power of two" enum entri "Francis Rammeloo" <francisrammeloo (AT) hotmail (DOT) com> wrote Quote: Hello, How can I determine the number of "power of two" enum entries? Following code explains my question: [] How about: #include <math.h> enum ActionCategory { eActionCategory_Color = 0x00000001, eActionCategory_Page = 0x00000002, eActionCategory_Prepress = 0x00000004, eActionCategory_Image = 0x00000008, eActionCategory_Text = 0x00000010, eActionCategory_Transform = 0x00000020, eActionCategory_Font = 0x00000040, eActionCategory_PDFX = 0x00000080, eActionCategory_Output = 0x00000100, eActionCategory_Document = 0x00000200, eActionCategory_Other = 0x00000400}; int eActionCategory_All = eActionCategory_Color Quote: eActionCategory_Page eActionCategory_Prepress eActionCategory_Image eActionCategory_Text eActionCategory_Transform eActionCategory_Font eActionCategory_PDFX eActionCategory_Output eActionCategory_Document eActionCategory_Other; int const eActionCategoryCount(log(eActionCategory_All+1)/log(2)); hth, Robert Kindred [] Thank you very much in advance for all feedback Quote: Best regards, Francis [] [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Kodt Guest Posted: Wed Dec 07, 2005 6:51 pm    Post subject: Re: How to determine the number of "power of two" enum entri How to count '1' bits of a given number ? Brute force: #define N1(x) ((x) & 1) // count bits among #0..0 #define N2(x) ( N1(x) + N1((x)>>1) ) // count among #0..1 #define N4(x) ( N2(x) + N2((x)>>2) ) #define N8(x) ( N4(x) + N4((x)>>4) ) #define N16(x) ( N8(x) + N8((x)>> ) #define N32(x) ( N16(x) + N16((x)>>16) ) Or the same, using templates... [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top elazro Guest Posted: Wed Dec 07, 2005 6:54 pm    Post subject: Re: How to determine the number of "power of two" enum entri Francis Rammeloo wrote: Quote: Hello, How can I determine the number of "power of two" enum entries? Following code explains my question: snip Assuming that all of the categories are powers of two except for eActionCategory_All (that is, there are no other masks formed by or-ing together other entries), then your problem reduces to counting the bits in eActionCategory_All. You might be tempted to just compute the largest power of 2 less than or equal to eActionCategory_All, but if you later removed some flags, that might break, and counting the bits at compile time is not much harder. To do this, you can use template specialization as follows: #include <iostream> #include <ostream> using namespace std; template <unsigned int N> struct CountBits { static const unsigned int result=(N%2)+CountBits<N/2>::result; }; template <> struct CountBits<0> { static const unsigned int result=0; }; Then, you can count the number of bits in a compile-time constant N by: CountBits<N>::result In your case, this can be used as follows: enum ActionCategory { eActionCategory_Color = 0x00000001, eActionCategory_Page = 0x00000002, eActionCategory_Prepress = 0x00000004, eActionCategory_Image = 0x00000008, eActionCategory_Text = 0x00000010, eActionCategory_Transform = 0x00000020, eActionCategory_Font = 0x00000040, eActionCategory_PDFX = 0x00000080, eActionCategory_Output = 0x00000100, eActionCategory_Document = 0x00000200, eActionCategory_Other = 0x00000400, eActionCategory_All = eActionCategory_Color Quote: eActionCategory_Page eActionCategory_Prepress eActionCategory_Image eActionCategory_Text eActionCategory_Transform eActionCategory_Font eActionCategory_PDFX eActionCategory_Output eActionCategory_Document eActionCategory_Other, eNumberOfCategories = CountBits<eActionCategory_All>::result // yields 11 in this case }; I would question the wisdom of putting the number of categories in the enum, since it a category, or even a collection of categories, like the others, and it would be hard to concieve of using it in the same way as another value in the enum. I think I'd rather see it as a separate constant, but that is, of course, up to you. Cheers, -matt [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Brannon Guest Posted: Thu Dec 08, 2005 10:00 pm    Post subject: Re: How to determine the number of "power of two" enum entri I suggest this link for efficient log2 help: http://www.aggregate.org/MAGIC/ [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Carl Barron Guest Posted: Sat Dec 10, 2005 1:03 pm    Post subject: Re: How to determine the number of "power of two" enum entri elazro <mahall (AT) ncsa (DOT) uiuc.edu> wrote: Quote: template <unsigned int N struct CountBits { static const unsigned int result=(N%2)+CountBits }; template struct CountBits<0 { static const unsigned int result=0; }; sure counting the bits this of 2^30 + 2^4 + 2 this way requires a nexting of 30 templates better count the bits in a character and add them:) splitting into chars and adding the results means sizeof(unsigned long) counting the bits in a char. [CHAR_BIT sizeof(unsigned long) deep, typically 4 + 8 = 12, lot smoller than 30 even 64 bit unsigned longs makes it 16 levels deep. More complex binary splitting of the unsigned long may take less depth to expand. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Falk Tannhäuser Guest Posted: Sun Dec 11, 2005 4:32 pm    Post subject: Re: How to determine the number of "power of two" enum entri Carl Barron wrote: Quote: elazro <mahall (AT) ncsa (DOT) uiuc.edu> wrote: template <unsigned int N struct CountBits { static const unsigned int result=(N%2)+CountBits }; template struct CountBits<0 { static const unsigned int result=0; }; sure counting the bits this of 2^30 + 2^4 + 2 this way requires a nexting of 30 templates better count the bits in a character and add them:) splitting into chars and adding the results means sizeof(unsigned long) counting the bits in a char. [CHAR_BIT sizeof(unsigned long) deep, typically 4 + 8 = 12, lot smoller than 30 even 64 bit unsigned longs makes it 16 levels deep. More complex binary splitting of the unsigned long may take less depth to expand. You can have a solution with a template instantiation depth growing only logarithmically with the number of bits to count, based on "parallelization" of counting. A non-templated runtime-calculating function working on 32-bit integers is unsigned bit_count(unsigned n) { n = (n>> 1 & 0x55555555) + (n & 0x55555555); n = (n>> 2 & 0x33333333) + (n & 0x33333333); n = (n>> 4 & 0x0F0F0F0F) + (n & 0x0F0F0F0F); n = (n>> 8 & 0x00FF00FF) + (n & 0x00FF00FF); n = (n>>16 & 0x0000FFFF) + (n & 0x0000FFFF); return n; } Furthermore, one can observe that 0x55555555 == 0xFFFFFFFF / 3 * 1 0x33333333 == 0xFFFFFFFF / 0xF * 3 0x0F0F0F0F == 0xFFFFFFFF / 0xFF * 0xF 0x00FF00FF == 0xFFFFFFFF / 0xFFFF * 0xFF Quote: From this, we can derive a templated compile-time calculation solution: #include <limits> #include <boost/static_assert.hpp> template<typename UIntT, UIntT N, int cnt=1, bool ready=false> struct CountBits { BOOST_STATIC_ASSERT(!std::numeric_limits<UIntT>::is_signed); // Don't want to think about what happens with signed integers static UIntT const bitmask = UIntT(-1) / ((UIntT(1)<<(2*cnt))-1) * ((UIntT(1)< // Could use boost::integer_traits // Note however, that above calculation will break on an exotic machine // where the number of bits in an integer is not a power of 2 static UIntT const result = CountBits<UIntT, (N>>cnt & bitmask) + (N & bitmask), 2*cnt, (4*cnt >= std::numeric_limits<UIntT>::digits) Quote: ::result; }; template<typename UIntT, UIntT N, int cnt> struct CountBits<UIntT, N, cnt, true> { static UIntT const bitmask = (UIntT(1)< static UIntT const result = (N>>cnt & bitmask) + (N & bitmask); }; This should work even with "unsigned long long" once is becomes standardized in C++. Falk [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Robert Kindred Guest Posted: Tue Dec 13, 2005 6:10 pm    Post subject: Re: How to determine the number of "power of two" enum entri "Brannon" <brannonking (AT) yahoo (DOT) com> wrote Quote: I suggest this link for efficient log2 help: http://www.aggregate.org/MAGIC/ Good link, thank you. However, for this example, the calculation is done at compile-time, so I would stick to the one-liner. Robert Kindred [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top elazro Guest Posted: Tue Dec 13, 2005 11:24 pm    Post subject: Re: How to determine the number of "power of two" enum entri Robert Kindred wrote: Quote: "Brannon" <brannonking (AT) yahoo (DOT) com> wrote in message news:1134074826.371981.282680 (AT) o13g2000cwo (DOT) googlegroups.com... I suggest this link for efficient log2 help: http://www.aggregate.org/MAGIC/ Good link, thank you. However, for this example, the calculation is done at compile-time, so I would stick to the one-liner. Robert Kindred Unfortunately, the one-liner: int const eActionCategoryCount(log(eActionCategory_All+1)/log(2)); will not be determined at compile time, as log(N) is not an integral constant expression, even if N is. Therefore, eActionCategoryCount won't be evaluated until runtime, so if you need the count at compile time (for some fancy metaprogramming or some such), this won't do (it should fail to compile). It would be nice if the compiler evaluated the log for you (and some compilers might), but it is not required, and may even be non-conforming. The other methods presented in this thread ( the macro method presented by kodt or the template method presented by Falk Tannhauser (or even my naive template approach) ) will provide the number of bits as a compile-time constant. -matt [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Robert Kindred Guest Posted: Thu Dec 15, 2005 11:23 pm    Post subject: Re: How to determine the number of "power of two" enum entri "elazro" <mahall (AT) ncsa (DOT) uiuc.edu> wrote Quote: Robert Kindred wrote: "Brannon" <brannonking (AT) yahoo (DOT) com> wrote in message news:1134074826.371981.282680 (AT) o13g2000cwo (DOT) googlegroups.com... I suggest this link for efficient log2 help: http://www.aggregate.org/MAGIC/ [] compile-time, so I would stick to the one-liner. [] will not be determined at compile time, as log(N) is not an integral constant expression, even if N is. Therefore, eActionCategoryCount won't be evaluated until runtime, so if you need the count at compile time (for some fancy metaprogramming or some such), this won't do (it should fail to compile). It would be nice if the compiler evaluated the log for you (and some compilers might), but it is not required, and may even be non-conforming. Thanks for the tip. The only clue that I get that my compiler (Builder 5.0) does this at compile time is that there is no blue dot next to the declaration of the global constant during debugging. However, this does not mean that all compilers will perform logarithms at compile time. [] [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top mzaytsev@nyc.rr.com Guest Posted: Sun Dec 18, 2005 12:37 pm    Post subject: Re: How to determine the number of "power of two" enum entri Francis Rammeloo wrote: Quote: Hello, How can I determine the number of "power of two" enum entries? Following code explains my question: enum ActionCategory { eActionCategory_Color = 0x00000001, eActionCategory_Page = 0x00000002, eActionCategory_Prepress = 0x00000004, eActionCategory_Image = 0x00000008, eActionCategory_Text = 0x00000010, eActionCategory_Transform = 0x00000020, eActionCategory_Font = 0x00000040, eActionCategory_PDFX = 0x00000080, eActionCategory_Output = 0x00000100, eActionCategory_Document = 0x00000200, eActionCategory_Other = 0x00000400, eActionCategory_All = eActionCategory_Color | eActionCategory_Page | eActionCategory_Prepress | eActionCategory_Image | eActionCategory_Text | eActionCategory_Transform | eActionCategory_Font | eActionCategory_PDFX | eActionCategory_Output | eActionCategory_Document | eActionCategory_Other, eNumberOfCategories = ??? ^-- How can I determine the number of categories at compile time? }; like: .... eNumberOfCategories = BitCount< eActionCategory_All >::result; template < int n > struct BitCount { enum { result = BitCount< (n >> 1) >::result + 1 }; } template<> struct BitCount< 0 > { enum { result = 0 }; } [ 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.