/home/mhx/git/github/libmoost/include/moost/math/integer/log2.hpp

Go to the documentation of this file.

/* vim:set ts=3 sw=3 sts=3 et: */
#ifndef MOOST_MATH_INTEGER_LOG2_HPP
#define MOOST_MATH_INTEGER_LOG2_HPP

#include <cassert>
#include <climits>

#include <boost/static_assert.hpp>
#include <boost/type_traits/is_unsigned.hpp>

namespace moost { namespace math { namespace integer {

#ifdef __GNUC__
namespace detail {

inline int count_leading_zeroes(unsigned arg)
{
   return __builtin_clz(arg);
}

inline int count_leading_zeroes(unsigned long arg)
{
   return __builtin_clzl(arg);
}

inline int count_leading_zeroes(boost::ulong_long_type arg)
{
   return __builtin_clzll(arg);
}

}
#endif

template <typename T>
inline unsigned log2_compat(T arg)
{
   BOOST_STATIC_ASSERT(boost::is_unsigned<T>::value);

   // This could be optimised using binary search, but I doubt
   // it'll ever get used... ;)
   unsigned r = 0;

   while (arg > static_cast<T>(1))
   {
      arg >>= 1;
      ++r;
   }

   return r;
}

template <typename T>
inline unsigned log2(T arg)
{
   BOOST_STATIC_ASSERT(boost::is_unsigned<T>::value);

   assert(arg > 0U);

#ifdef __GNUC__
   return (8U*unsigned(sizeof(T)) - 1U) - detail::count_leading_zeroes(arg);
#else
   return log2_compat(arg);
#endif
}

}}}

#endif