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 williamr@2: #include // 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 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 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, because williamr@2: // of its usual const-related problems in argument deduction williamr@2: // - gps williamr@2: template 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::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 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 :: 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