RE: [boost] Re: Need help in solving compile-time log2

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2001-05-17 06:28:56

 Daryle Walker wrote:

> // Need to simulate this as a template for compile-time processing
> int
> dynamic_lb( unsigned long val )
> {
>     int  place = 0;
>     for ( int i = std::numeric_limits<unsigned long>::digits ; i > 0
>      ; i /= 2 )
>     {
>         int const            half_place = i / 2;
>         unsigned long const  lower_mask = (1ul << half_place) - 1;
>         unsigned long const  upper_mask = ~lower_mask;
>         if ( (val & upper_mask) != 0 )
>         {
>             val >>= half_place;
>             place += half_place;
>         }
>     }
>     return place;
> }
> 
> Now, how would I convert this to a template "routine" so I 
> can compute this for a compile-time constant?  Also, would 
> it work if an "unsigned long" had a bit count that wasn't a 
> power of two?  (That would necessitate at least one odd 
> number halving.  Would it be better to keep the larger or 
> smaller part?)  Maybe we should get those compile-time
> IFs and FORs up and running.

FWIW, here is an example how one can implement a compile-time equivalent of
above algorithm using preliminary
version of 'boost::mpl' library:

#include <boost/mpl/for_loop.hpp>
#include <boost/mpl/loop_variable.hpp> 
#include <boost/mpl/int_value.hpp>
#include <boost/mpl/comparision.hpp>
#include <boost/static_assert.hpp>
#include <limits.hpp>

namespace mpl = boost::mpl;

template<unsigned long Value, int Place = 0>
struct lb_body
  {
  BOOST_STATIC_CONSTANT(int, place = Place);
  template<class N> struct body
    {
    BOOST_STATIC_CONSTANT(int,  half_place = N::value / 2);
    BOOST_STATIC_CONSTANT(long, lower_mask = (1ul << half_place) - 1);
    BOOST_STATIC_CONSTANT(long, upper_mask = ~lower_mask);
    typedef typename mpl::select_type< 
          (Value & upper_mask) != 0
        , lb_body< (Value >> half_place), (Place + half_place) >
        , lb_body< Value, Place >
        >::type next_statement;
    };
};

template<long N>
struct divide_by
  {
  template<class T> struct apply
    {
    BOOST_STATIC_CONSTANT(long, result = (T::value / N));
    typedef mpl::int_value<result> type;
    };
  };

template<int N>
struct lb 
  {
  typedef mpl::for_loop< mpl::int_value< std::numeric_limits<unsigned
long>::digits >
                       , mpl::greater_than<0>
                       , divide_by<2>
                       , mpl::loop_variable_accessor< lb_body<N> >
                       > loop_;

  BOOST_STATIC_CONSTANT(int
    , value = loop_::executed::statement::place
    );
  };

BOOST_STATIC_ASSERT(lb<1023>::value == 9);
BOOST_STATIC_ASSERT(lb<1024>::value == 10);
BOOST_STATIC_ASSERT(lb<1025>::value == 10);

If you are interested enough to take a more close look at this, the library
archive lies here - http://groups.yahoo.com/group/boost/files/mpl/, but for
now it lacks the documentation, so be prepared :).

Aleksey