1// -----------------------------------------------------------
2// integer_log2.hpp
3//
4// Gives the integer part of the logarithm, in base 2, of a
5// given number. Behavior is undefined if the argument is <= 0.
6//
7// Copyright (c) 2003-2004, 2008 Gennaro Prota
8// Copyright (c) 2022 Andrey Semashev
9//
10// Distributed under the Boost Software License, Version 1.0.
11// (See accompanying file LICENSE_1_0.txt or copy at
12// https://www.boost.org/LICENSE_1_0.txt)
13//
14// -----------------------------------------------------------
15
16#ifndef BOOST_INTEGER_INTEGER_LOG2_HPP
17#define BOOST_INTEGER_INTEGER_LOG2_HPP
18
19#include <climits>
20#include <limits>
21#include <boost/config.hpp>
22#include <boost/assert.hpp>
23#include <boost/cstdint.hpp>
24#include <boost/core/bit.hpp>
25#include <boost/core/enable_if.hpp>
26#include <boost/type_traits/is_integral.hpp>
27#include <boost/type_traits/make_unsigned.hpp>
28
29namespace boost {
30namespace detail {
31
32// helper to find the maximum power of two
33// less than p
34template< unsigned int p, unsigned int n, bool = ((2u * n) < p) >
35struct max_pow2_less :
36 public max_pow2_less< p, 2u * n >
37{
38};
39
40template< unsigned int p, unsigned int n >
41struct max_pow2_less< p, n, false >
42{
43 BOOST_STATIC_CONSTANT(unsigned int, value = n);
44};
45
46template< typename T >
47inline typename boost::disable_if< boost::is_integral< T >, int >::type integer_log2_impl(T x)
48{
49 unsigned int n = detail::max_pow2_less<
50 std::numeric_limits< T >::digits,
51 CHAR_BIT / 2u
52 >::value;
53
54 int result = 0;
55 while (x != 1)
56 {
57 T t(x >> n);
58 if (t)
59 {
60 result += static_cast< int >(n);
61#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
62 x = static_cast< T&& >(t);
63#else
64 x = t;
65#endif
66 }
67 n >>= 1u;
68 }
69
70 return result;
71}
72
73template< typename T >
74inline typename boost::enable_if< boost::is_integral< T >, int >::type integer_log2_impl(T x)
75{
76 // We could simply rely on numeric_limits but sometimes
77 // Borland tries to use numeric_limits<const T>, because
78 // of its usual const-related problems in argument deduction
79 // - gps
80 return static_cast< int >((sizeof(T) * CHAR_BIT - 1u) -
81 boost::core::countl_zero(static_cast< typename boost::make_unsigned< T >::type >(x)));
82}
83
84#if defined(BOOST_HAS_INT128)
85// We need to provide explicit overloads for __int128 because (a) boost/core/bit.hpp currently does not support it and
86// (b) std::numeric_limits are not specialized for __int128 in some standard libraries.
87inline int integer_log2_impl(boost::uint128_type x)
88{
89 const boost::uint64_t x_hi = static_cast< boost::uint64_t >(x >> 64u);
90 if (x_hi != 0u)
91 return 127 - boost::core::countl_zero(x: x_hi);
92 else
93 return 63 - boost::core::countl_zero(x: static_cast< boost::uint64_t >(x));
94}
95
96inline int integer_log2_impl(boost::int128_type x)
97{
98 return detail::integer_log2_impl(x: static_cast< boost::uint128_type >(x));
99}
100#endif // defined(BOOST_HAS_INT128)
101
102} // namespace detail
103
104
105// ------------
106// integer_log2
107// ------------
108template< typename T >
109inline int integer_log2(T x)
110{
111 BOOST_ASSERT(x > 0);
112 return detail::integer_log2_impl(x);
113}
114
115} // namespace boost
116
117#endif // BOOST_INTEGER_INTEGER_LOG2_HPP
118

source code of boost/libs/integer/include/boost/integer/integer_log2.hpp