Chris@16: // boost heap: integer log2
Chris@16: //
Chris@16: // Copyright (C) 2010 Tim Blechmann
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_HEAP_DETAIL_ILOG2_HPP
Chris@16: #define BOOST_HEAP_DETAIL_ILOG2_HPP
Chris@16: 
Chris@16: #include <string> // std::size_t
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace heap {
Chris@16: namespace detail {
Chris@16: 
Chris@16: template <typename IntType>
Chris@16: struct log2
Chris@16: {
Chris@16:     IntType operator()(IntType value)
Chris@16:     {
Chris@16:         IntType l = 0;
Chris@16:         while( (value >> l) > 1 )
Chris@16:             ++l;
Chris@16:         return l;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: #ifdef __GNUC__
Chris@16: template<>
Chris@16: struct log2<unsigned int>
Chris@16: {
Chris@16:     unsigned int operator()(unsigned int value)
Chris@16:     {
Chris@16:         return sizeof(unsigned int)*8 - __builtin_clz(value - 1);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template<>
Chris@16: struct log2<unsigned long>
Chris@16: {
Chris@16:     unsigned long operator()(unsigned long value)
Chris@16:     {
Chris@16:         return sizeof(unsigned long)*8 - __builtin_clzl(value - 1);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: } /* namespace detail */
Chris@16: 
Chris@16: 
Chris@16: template <typename IntType>
Chris@16: IntType log2(IntType value)
Chris@16: {
Chris@16:     detail::log2<IntType> fn;
Chris@16:     return fn(value);
Chris@16: }
Chris@16: 
Chris@16: } /* namespace heap */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif /* BOOST_HEAP_DETAIL_ILOG2_HPP */