// -------------------------------------

// integer_log2.hpp

//

//   Gives the integer part of the logarithm, in base 2, of a

// given number. Behavior is undefined if the argument is <= 0.

//

//

//       (C) Copyright Gennaro Prota 2003 - 2004.

//

// Distributed under the Boost Software License, Version 1.0.

//    (See accompanying file LICENSE_1_0.txt or copy at

//          http://www.boost.org/LICENSE_1_0.txt)

//

// ------------------------------------------------------

//

// $Id: integer_log2.hpp 41369 2007-11-25 18:07:19Z bemandawes $





#ifndef BOOST_INTEGER_LOG2_HPP_GP_20030301

#define BOOST_INTEGER_LOG2_HPP_GP_20030301



#include <assert.h>

#ifdef __BORLANDC__

#include <climits>

#endif

#include "boost/limits.hpp"

#include "boost/config.hpp"





namespace boost {

 namespace detail {



  template <typename T>

  int integer_log2_impl(T x, int n) {



      int result = 0;



      while (x != 1) {



          const T t = x >> n;

          if (t) {

              result += n;

              x = t;

          }

          n /= 2;



      }



      return result;

  }







  // helper to find the maximum power of two

  // less than p (more involved than necessary,

  // to avoid PTS)

  //

  template <int p, int n>

  struct max_pow2_less {



      enum { c = 2*n < p };



      BOOST_STATIC_CONSTANT(int, value =

          c ? (max_pow2_less< c*p, 2*c*n>::value) : n);



  };



  template <>

  struct max_pow2_less<0, 0> {



      BOOST_STATIC_CONSTANT(int, value = 0);

  };



  // this template is here just for Borland :(

  // we could simply rely on numeric_limits but sometimes

  // Borland tries to use numeric_limits<const T>, because

  // of its usual const-related problems in argument deduction

  // - gps

  template <typename T>

  struct width {



#ifdef __BORLANDC__

      BOOST_STATIC_CONSTANT(int, value = sizeof(T) * CHAR_BIT);

#else

      BOOST_STATIC_CONSTANT(int, value = (std::numeric_limits<T>::digits));

#endif



  };



 } // detail





 // ---------

 // integer_log2

 // ---------------

 //

 template <typename T>

 int integer_log2(T x) {



     assert(x > 0);



     const int n = detail::max_pow2_less<

                     detail::width<T> :: value, 4

                   > :: value;



     return detail::integer_log2_impl(x, n);



 }







}







#endif // include guard

