1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
// -----------------------------------------------------------
// 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.
//
// Copyright (c) 2003-2004, 2008 Gennaro Prota
//
// 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)
//
// -----------------------------------------------------------
#ifndef BOOST_INTEGER_INTEGER_LOG2_HPP
#define BOOST_INTEGER_INTEGER_LOG2_HPP
#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 = static_cast<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
|
