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