heap/detail/ilog2.hpp

0001 // boost heap: integer log2
0002 //
0003 // Copyright (C) 2010 Tim Blechmann
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_HEAP_DETAIL_ILOG2_HPP
0010 #define BOOST_HEAP_DETAIL_ILOG2_HPP
0011
0012 #include <string> // std::size_t
0013
0014 namespace boost {
0015 namespace heap {
0016 namespace detail {
0017
0018 template <typename IntType>
0019 struct log2
0020 {
0021     IntType operator()(IntType value)
0022     {
0023         IntType l = 0;
0024         while( (value >> l) > 1 )
0025             ++l;
0026         return l;
0027     }
0028 };
0029
0030 #ifdef __GNUC__
0031 template<>
0032 struct log2<unsigned int>
0033 {
0034     unsigned int operator()(unsigned int value)
0035     {
0036         return sizeof(unsigned int)*8 - __builtin_clz(value - 1);
0037     }
0038 };
0039
0040 template<>
0041 struct log2<unsigned long>
0042 {
0043     unsigned long operator()(unsigned long value)
0044     {
0045         return sizeof(unsigned long)*8 - __builtin_clzl(value - 1);
0046     }
0047 };
0048
0049 #endif
0050
0051 } /* namespace detail */
0052
0053
0054 template <typename IntType>
0055 IntType log2(IntType value)
0056 {
0057     detail::log2<IntType> fn;
0058     return fn(value);
0059 }
0060
0061 } /* namespace heap */
0062 } /* namespace boost */
0063
0064 #endif /* BOOST_HEAP_DETAIL_ILOG2_HPP */