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