Re: [boost] A question about static_log2

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-01-25 08:06:54

Gennaro Prota:
>Am I missing something?

Yes. I have, in fact, previously explained how to use choose_n correctly. 
Please read more carefully. If something doesn't appear to make sense, 
reconsider your basic assumptions. Only after you have carefully 
reconsidered your assumptions, should you challenge the assertions of 
others.

In this case, you assumed that the value returned by choose_n must be 
divided by two or that choose_n computes the number of value bits in 
unsigned long. This is a false assumption. choose_n does not compute the 
number of value bits in unsigned long. Even the name choose_n should be a 
strong enough hint. Rather it directly chooses the initial n for the core 
static_log2 algorithm.

- Vesa Karvonen

#include "boost/config.hpp"
#include "boost/static_assert.hpp"

namespace boost {
  namespace detail {
    template<int n = 16>
    struct choose_initial_n {
      enum {c = !!(1ul<<n<<n),
            value = !c*n + choose_initial_n<c*n*2>::value};
    };

    template<>
    struct choose_initial_n<0> {
      enum {value = 0};
    };

    template<unsigned long x, int n = choose_initial_n<>::value>
    struct static_log2_impl {
      enum {cn = (1ul<<n <= x) * n,
            value = cn + static_log2_impl<(x>>cn),n/2>::value};
    };

    template<>
    struct static_log2_impl<1,0> {
      enum {value = 0};
    };
  }

  template<unsigned long x>
  struct static_log2 {
    BOOST_STATIC_CONSTANT(int, value = detail::static_log2_impl<x>::value);
  };

  template<>
  struct static_log2<0> {};
}

BOOST_STATIC_ASSERT(boost::static_log2<1>::value == 0);
BOOST_STATIC_ASSERT(boost::static_log2<2>::value == 1);
BOOST_STATIC_ASSERT(boost::static_log2<3>::value == 1);
BOOST_STATIC_ASSERT(boost::static_log2<(1ul<<31)-1>::value == 30);
BOOST_STATIC_ASSERT(boost::static_log2<(1ul<<31)>::value == 31);
BOOST_STATIC_ASSERT(boost::static_log2<(1ul<<31)+1>::value == 31);

int main() {
  return 0;
}

_________________________________________________________________
Add photos to your e-mail with MSN 8. Get 2 months FREE*. 
http://join.msn.com/?page=features/featuredemail