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