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