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
0013 namespace boost { namespace heap {
0014 namespace detail {
0015
0016 template < typename IntType >
0017 struct log2
0018 {
0019     IntType operator()( IntType value )
0020     {
0021         IntType l = 0;
0022         while ( ( value >> l ) > 1 )
0023             ++l;
0024         return l;
0025     }
0026 };
0027
0028 #ifdef __GNUC__
0029 template <>
0030 struct log2< unsigned int >
0031 {
0032     unsigned int operator()( unsigned int value )
0033     {
0034         return sizeof( unsigned int ) * 8 - __builtin_clz( value - 1 );
0035     }
0036 };
0037
0038 template <>
0039 struct log2< unsigned long >
0040 {
0041     unsigned long operator()( unsigned long value )
0042     {
0043         return sizeof( unsigned long ) * 8 - __builtin_clzl( value - 1 );
0044     }
0045 };
0046
0047 #endif
0048
0049 } /* namespace detail */
0050
0051
0052 template < typename IntType >
0053 IntType log2( IntType value )
0054 {
0055     detail::log2< IntType > fn;
0056     return fn( value );
0057 }
0058
0059 }}     // namespace boost::heap
0060
0061 #endif /* BOOST_HEAP_DETAIL_ILOG2_HPP */