blob: d8504db57eb730047d32d15ec462e7db056f736a [file] [log] [blame]
Jeff Thompson86b6d642013-10-17 15:01:56 -07001// -----------------------------------------------------------
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 NDNBOOST_INTEGER_LOG2_HPP_GP_20030301
16#define NDNBOOST_INTEGER_LOG2_HPP_GP_20030301
17
18#include <assert.h>
19#ifdef __BORLANDC__
20#include <climits>
21#endif
22#include "ndnboost/limits.hpp"
23#include "ndnboost/config.hpp"
24
25
26namespace ndnboost {
27 namespace detail {
28
29 template <typename T>
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 NDNBOOST_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 NDNBOOST_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 __BORLANDC__
79 NDNBOOST_STATIC_CONSTANT(int, value = sizeof(T) * CHAR_BIT);
80#else
81 NDNBOOST_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>
94 int integer_log2(T x) {
95
96 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