On Mon, 20 Jan 2003 00:08:33 +0200, "Vesa Karvonen" <[EMAIL PROTECTED]> wrote:
>Gennaro Prota: >>Can someone who was subscribed when the Integer library was approved >>explain me what were the reasons to choose the current implementation >>of static_log2 against e.g. > >I can't help in that, but > >> template <unsigned long n> >> struct log2 { >> BOOST_STATIC_CONSTANT(unsigned long, >> value = 1 + (log2<n/2>::value)); >> }; >> >> template <> >> struct log2<1> { >> BOOST_STATIC_CONSTANT(unsigned long, value = 0); >> }; > >the above algorithm is inefficient .... > and should not be used. Consider the >following algorithm instead: > >#include <iostream> >#include <climits> > >template<unsigned long x, > int n = sizeof(unsigned long) * CHAR_BIT / 2> >struct log2 { >private: > enum {c = (1 << n) <= x}; Wrong. The left-shift may give undefined behavior, because n can be greater than or equal to the number of value bits in an unsigned long (The C++ standard isn't clear about this, and I have a DR ready in the oven since a long time) >public: > enum {value = c*n + log2<(x>>(c*n)),(n/2)>::value}; Same as above. The value you want here is not sizeof(unsigned long) * CHAR_BIT / 2 but std::numeric_limits<unsigned long>::digits / 2 Alternatively you could use my width<> or my precision<> template, if it wasn't that they in turn use log2. The problem is that the C standard (and so C++) provides a xx_BIT macro only for the type char. You don't have e.g. INT_BIT or LONG_BIT, and you can't use CHAR_BIT*sizeof(int) and CHAR_BIT*sizeof(long) in their place, at least not portably, because those expressions give you the number of bits in the object representation, and that's not necessarily the same as the number of bits used to represent values. One way to remain portable is to compute such a number by calculating, for a given integer type, 1 + the integral part of the log2 of its maximum value (this in turn relies on other properties guaranteed by the C language but I don't think I have to explain such basics here). PS: Another problem with your implementation I'll leave it as an exercise ;-) This is a hint: log2 (511) |---- 4 + log2<31, 2> |--- 2 + log2<7, 1> |--- 1 + log2<3, 0> // oops... Genny. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost