boost/integer/integer_log2.hpp

0001 // -----------------------------------------------------------
0002 // integer_log2.hpp
0003 //
0004 //   Gives the integer part of the logarithm, in base 2, of a
0005 // given number. Behavior is undefined if the argument is <= 0.
0006 //
0007 //        Copyright (c) 2003-2004, 2008 Gennaro Prota
0008 //            Copyright (c) 2022 Andrey Semashev
0009 //
0010 // Distributed under the Boost Software License, Version 1.0.
0011 //    (See accompanying file LICENSE_1_0.txt or copy at
0012 //          https://www.boost.org/LICENSE_1_0.txt)
0013 //
0014 // -----------------------------------------------------------
0015
0016 #ifndef BOOST_INTEGER_INTEGER_LOG2_HPP
0017 #define BOOST_INTEGER_INTEGER_LOG2_HPP
0018
0019 #include <climits>
0020 #include <limits>
0021 #include <boost/config.hpp>
0022 #include <boost/assert.hpp>
0023 #include <boost/cstdint.hpp>
0024 #include <boost/core/bit.hpp>
0025 #include <boost/core/enable_if.hpp>
0026 #include <boost/type_traits/is_integral.hpp>
0027 #include <boost/type_traits/make_unsigned.hpp>
0028
0029 namespace boost {
0030 namespace detail {
0031
0032 // helper to find the maximum power of two
0033 // less than p
0034 template< unsigned int p, unsigned int n, bool = ((2u * n) < p) >
0035 struct max_pow2_less :
0036     public max_pow2_less< p, 2u * n >
0037 {
0038 };
0039
0040 template< unsigned int p, unsigned int n >
0041 struct max_pow2_less< p, n, false >
0042 {
0043     BOOST_STATIC_CONSTANT(unsigned int, value = n);
0044 };
0045
0046 template< typename T >
0047 inline typename boost::disable_if< boost::is_integral< T >, int >::type integer_log2_impl(T x)
0048 {
0049     unsigned int n = detail::max_pow2_less<
0050         std::numeric_limits< T >::digits,
0051         CHAR_BIT / 2u
0052     >::value;
0053
0054     int result = 0;
0055     while (x != 1)
0056     {
0057         T t(x >> n);
0058         if (t)
0059         {
0060             result += static_cast< int >(n);
0061 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
0062             x = static_cast< T&& >(t);
0063 #else
0064             x = t;
0065 #endif
0066         }
0067         n >>= 1u;
0068     }
0069
0070     return result;
0071 }
0072
0073 template< typename T >
0074 inline typename boost::enable_if< boost::is_integral< T >, int >::type integer_log2_impl(T x)
0075 {
0076     // We could simply rely on numeric_limits but sometimes
0077     // Borland tries to use numeric_limits<const T>, because
0078     // of its usual const-related problems in argument deduction
0079     // - gps
0080     return static_cast< int >((sizeof(T) * CHAR_BIT - 1u) -
0081         boost::core::countl_zero(static_cast< typename boost::make_unsigned< T >::type >(x)));
0082 }
0083
0084 #if defined(BOOST_HAS_INT128)
0085 // We need to provide explicit overloads for __int128 because (a) boost/core/bit.hpp currently does not support it and
0086 // (b) std::numeric_limits are not specialized for __int128 in some standard libraries.
0087 inline int integer_log2_impl(boost::uint128_type x)
0088 {
0089     const boost::uint64_t x_hi = static_cast< boost::uint64_t >(x >> 64u);
0090     if (x_hi != 0u)
0091         return 127 - boost::core::countl_zero(x_hi);
0092     else
0093         return 63 - boost::core::countl_zero(static_cast< boost::uint64_t >(x));
0094 }
0095
0096 inline int integer_log2_impl(boost::int128_type x)
0097 {
0098     return detail::integer_log2_impl(static_cast< boost::uint128_type >(x));
0099 }
0100 #endif // defined(BOOST_HAS_INT128)
0101
0102 } // namespace detail
0103
0104
0105 // ------------
0106 // integer_log2
0107 // ------------
0108 template< typename T >
0109 inline int integer_log2(T x)
0110 {
0111     BOOST_ASSERT(x > 0);
0112     return detail::integer_log2_impl(x);
0113 }
0114
0115 } // namespace boost
0116
0117 #endif // BOOST_INTEGER_INTEGER_LOG2_HPP