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)55IntType 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