1 // ----------------------------------------------------------- 2 // integer_log2.hpp 3 // 4 // Gives the integer part of the logarithm, in base 2, of a 5 // given number. Behavior is undefined if the argument is <= 0. 6 // 7 // Copyright (c) 2003-2004, 2008 Gennaro Prota 8 // 9 // Distributed under the Boost Software License, Version 1.0. 10 // (See accompanying file LICENSE_1_0.txt or copy at 11 // http://www.boost.org/LICENSE_1_0.txt) 12 // 13 // ----------------------------------------------------------- 14 15 #ifndef BOOST_INTEGER_INTEGER_LOG2_HPP 16 #define BOOST_INTEGER_INTEGER_LOG2_HPP 17 18 #include <boost/limits.hpp> 19 #include <boost/config.hpp> 20 #include <boost/assert.hpp> 21 #if defined(BOOST_BORLANDC) 22 #include <climits> 23 #endif 24 25 26 namespace boost { 27 namespace detail { 28 29 template <typename T> integer_log2_impl(T x,int n)30 int integer_log2_impl(T x, int n) { 31 32 int result = 0; 33 34 while (x != 1) { 35 36 const T t = static_cast<T>(x >> n); 37 if (t) { 38 result += n; 39 x = t; 40 } 41 n /= 2; 42 43 } 44 45 return result; 46 } 47 48 49 50 // helper to find the maximum power of two 51 // less than p (more involved than necessary, 52 // to avoid PTS) 53 // 54 template <int p, int n> 55 struct max_pow2_less { 56 57 enum { c = 2*n < p }; 58 59 BOOST_STATIC_CONSTANT(int, value = 60 c ? (max_pow2_less< c*p, 2*c*n>::value) : n); 61 62 }; 63 64 template <> 65 struct max_pow2_less<0, 0> { 66 67 BOOST_STATIC_CONSTANT(int, value = 0); 68 }; 69 70 // this template is here just for Borland :( 71 // we could simply rely on numeric_limits but sometimes 72 // Borland tries to use numeric_limits<const T>, because 73 // of its usual const-related problems in argument deduction 74 // - gps 75 template <typename T> 76 struct width { 77 78 #ifdef BOOST_BORLANDC 79 BOOST_STATIC_CONSTANT(int, value = sizeof(T) * CHAR_BIT); 80 #else 81 BOOST_STATIC_CONSTANT(int, value = (std::numeric_limits<T>::digits)); 82 #endif 83 84 }; 85 86 } // detail 87 88 89 // --------- 90 // integer_log2 91 // --------------- 92 // 93 template <typename T> integer_log2(T x)94 int integer_log2(T x) { 95 96 BOOST_ASSERT(x > 0); 97 98 const int n = detail::max_pow2_less< 99 detail::width<T> :: value, 4 100 > :: value; 101 102 return detail::integer_log2_impl(x, n); 103 104 } 105 106 107 108 } 109 110 111 112 #endif // include guard 113