1// -------------- Boost static_log2.hpp header file ----------------------- //
2//
3// Copyright (C) 2001 Daryle Walker.
4// Copyright (C) 2003 Vesa Karvonen.
5// Copyright (C) 2003 Gennaro Prota.
6//
7// Distributed under the Boost Software License, Version 1.0.
8// (See accompanying file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10//
11// ---------------------------------------------------
12// See http://www.boost.org/libs/integer for documentation.
13// ------------------------------------------------------------------------- //
14
15
16#ifndef BOOST_INTEGER_STATIC_LOG2_HPP
17#define BOOST_INTEGER_STATIC_LOG2_HPP
18
19#include <boost/config.hpp>
20#include <boost/integer_fwd.hpp>
21
22namespace boost {
23
24 namespace detail {
25
26 namespace static_log2_impl {
27
28 // choose_initial_n<>
29 //
30 // Recursively doubles its integer argument, until it
31 // becomes >= of the "width" (C99, 6.2.6.2p4) of
32 // static_log2_argument_type.
33 //
34 // Used to get the maximum power of two less then the width.
35 //
36 // Example: if on your platform argument_type has 48 value
37 // bits it yields n=32.
38 //
39 // It's easy to prove that, starting from such a value
40 // of n, the core algorithm works correctly for any width
41 // of static_log2_argument_type and that recursion always
42 // terminates with x = 1 and n = 0 (see the algorithm's
43 // invariant).
44
45 typedef boost::static_log2_argument_type argument_type;
46 typedef boost::static_log2_result_type result_type;
47
48 template <result_type n>
49 struct choose_initial_n {
50
51 BOOST_STATIC_CONSTANT(bool, c = (argument_type(1) << n << n) != 0);
52 BOOST_STATIC_CONSTANT(
53 result_type,
54 value = !c*n + choose_initial_n<2*c*n>::value
55 );
56
57 };
58
59 template <>
60 struct choose_initial_n<0> {
61 BOOST_STATIC_CONSTANT(result_type, value = 0);
62 };
63
64
65
66 // start computing from n_zero - must be a power of two
67 const result_type n_zero = 16;
68 const result_type initial_n = choose_initial_n<n_zero>::value;
69
70 // static_log2_impl<>
71 //
72 // * Invariant:
73 // 2n
74 // 1 <= x && x < 2 at the start of each recursion
75 // (see also choose_initial_n<>)
76 //
77 // * Type requirements:
78 //
79 // argument_type maybe any unsigned type with at least n_zero + 1
80 // value bits. (Note: If larger types will be standardized -e.g.
81 // unsigned long long- then the argument_type typedef can be
82 // changed without affecting the rest of the code.)
83 //
84
85 template <argument_type x, result_type n = initial_n>
86 struct static_log2_impl {
87
88 BOOST_STATIC_CONSTANT(bool, c = (x >> n) > 0); // x >= 2**n ?
89 BOOST_STATIC_CONSTANT(
90 result_type,
91 value = c*n + (static_log2_impl< (x>>c*n), n/2 >::value)
92 );
93
94 };
95
96 template <>
97 struct static_log2_impl<1, 0> {
98 BOOST_STATIC_CONSTANT(result_type, value = 0);
99 };
100
101 }
102 } // detail
103
104
105
106 // --------------------------------------
107 // static_log2<x>
108 // ----------------------------------------
109
110 template <static_log2_argument_type x>
111 struct static_log2 {
112
113 BOOST_STATIC_CONSTANT(
114 static_log2_result_type,
115 value = detail::static_log2_impl::static_log2_impl<x>::value
116 );
117
118 };
119
120
121 template <>
122 struct static_log2<0> { };
123
124}
125
126#endif // include guard
127

source code of include/boost/integer/static_log2.hpp