[boost] Re: A question about static_log2

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2003-01-20 13:40:42

On Mon, 20 Jan 2003 00:08:33 +0200, "Vesa Karvonen"
<vesa_karvonen_at_[hidden]> 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.