1 // boost heap: integer log2
2 //
3 // Copyright (C) 2010 Tim Blechmann
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 
9 #ifndef BOOST_HEAP_DETAIL_ILOG2_HPP
10 #define BOOST_HEAP_DETAIL_ILOG2_HPP
11 
12 #include <string> // std::size_t
13 
14 namespace boost {
15 namespace heap {
16 namespace detail {
17 
18 template <typename IntType>
19 struct log2
20 {
operator ()boost::heap::detail::log221     IntType operator()(IntType value)
22     {
23         IntType l = 0;
24         while( (value >> l) > 1 )
25             ++l;
26         return l;
27     }
28 };
29 
30 #ifdef __GNUC__
31 template<>
32 struct log2<unsigned int>
33 {
operator ()boost::heap::detail::log234     unsigned int operator()(unsigned int value)
35     {
36         return sizeof(unsigned int)*8 - __builtin_clz(value - 1);
37     }
38 };
39 
40 template<>
41 struct log2<unsigned long>
42 {
operator ()boost::heap::detail::log243     unsigned long operator()(unsigned long value)
44     {
45         return sizeof(unsigned long)*8 - __builtin_clzl(value - 1);
46     }
47 };
48 
49 #endif
50 
51 } /* namespace detail */
52 
53 
54 template <typename IntType>
log2(IntType value)55 IntType log2(IntType value)
56 {
57     detail::log2<IntType> fn;
58     return fn(value);
59 }
60 
61 } /* namespace heap */
62 } /* namespace boost */
63 
64 #endif /* BOOST_HEAP_DETAIL_ILOG2_HPP */
65