sl@0: // -------------------------------------
sl@0: // integer_log2.hpp
sl@0: //
sl@0: //   Gives the integer part of the logarithm, in base 2, of a
sl@0: // given number. Behavior is undefined if the argument is <= 0.
sl@0: //
sl@0: //
sl@0: //       (C) Copyright Gennaro Prota 2003 - 2004.
sl@0: //
sl@0: // Distributed under the Boost Software License, Version 1.0.
sl@0: //    (See accompanying file LICENSE_1_0.txt or copy at
sl@0: //          http://www.boost.org/LICENSE_1_0.txt)
sl@0: //
sl@0: // ------------------------------------------------------
sl@0: 
sl@0: 
sl@0: 
sl@0: #ifndef BOOST_INTEGER_LOG2_HPP_GP_20030301
sl@0: #define BOOST_INTEGER_LOG2_HPP_GP_20030301
sl@0: 
sl@0: #include <cassert>
sl@0: #include <climits> // actually used for Borland only
sl@0: #include "boost/limits.hpp"
sl@0: #include "boost/config.hpp"
sl@0: 
sl@0: 
sl@0: namespace boost {
sl@0:  namespace detail {
sl@0: 
sl@0:   template <typename T>
sl@0:   int integer_log2_impl(T x, int n) {
sl@0: 
sl@0:       int result = 0;
sl@0: 
sl@0:       while (x != 1) {
sl@0: 
sl@0:           const T t = x >> n;
sl@0:           if (t) {
sl@0:               result += n;
sl@0:               x = t;
sl@0:           }
sl@0:           n /= 2;
sl@0: 
sl@0:       }
sl@0: 
sl@0:       return result;
sl@0:   }
sl@0: 
sl@0: 
sl@0: 
sl@0:   // helper to find the maximum power of two
sl@0:   // less than p (more involved than necessary,
sl@0:   // to avoid PTS)
sl@0:   //
sl@0:   template <int p, int n>
sl@0:   struct max_pow2_less {
sl@0: 
sl@0:       enum { c = 2*n < p };
sl@0: 
sl@0:       BOOST_STATIC_CONSTANT(int, value =
sl@0:           c ? (max_pow2_less< c*p, 2*c*n>::value) : n);
sl@0: 
sl@0:   };
sl@0: 
sl@0:   template <>
sl@0:   struct max_pow2_less<0, 0> {
sl@0: 
sl@0:       BOOST_STATIC_CONSTANT(int, value = 0);
sl@0:   };
sl@0: 
sl@0:   // this template is here just for Borland :(
sl@0:   // we could simply rely on numeric_limits but sometimes
sl@0:   // Borland tries to use numeric_limits<const T>, because
sl@0:   // of its usual const-related problems in argument deduction
sl@0:   // - gps
sl@0:   template <typename T>
sl@0:   struct width {
sl@0: 
sl@0: #ifdef __BORLANDC__
sl@0:       BOOST_STATIC_CONSTANT(int, value = sizeof(T) * CHAR_BIT);
sl@0: #else
sl@0:       BOOST_STATIC_CONSTANT(int, value = (std::numeric_limits<T>::digits));
sl@0: #endif
sl@0: 
sl@0:   };
sl@0: 
sl@0:  } // detail
sl@0: 
sl@0: 
sl@0:  // ---------
sl@0:  // integer_log2
sl@0:  // ---------------
sl@0:  //
sl@0:  template <typename T>
sl@0:  int integer_log2(T x) {
sl@0: 
sl@0:      assert(x > 0);
sl@0: 
sl@0:      const int n = detail::max_pow2_less<
sl@0:                      detail::width<T> :: value, 4
sl@0:                    > :: value;
sl@0: 
sl@0:      return detail::integer_log2_impl(x, n);
sl@0: 
sl@0:  }
sl@0: 
sl@0: 
sl@0: 
sl@0: }
sl@0: 
sl@0: 
sl@0: 
sl@0: #endif // include guard