absl/numeric/bits.h

0001 // Copyright 2020 The Abseil Authors
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //     https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014 //
0015 // -----------------------------------------------------------------------------
0016 // File: bits.h
0017 // -----------------------------------------------------------------------------
0018 //
0019 // This file contains implementations of C++20's bitwise math functions, as
0020 // defined by:
0021 //
0022 // P0553R4:
0023 //  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html
0024 // P0556R3:
0025 //  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0556r3.html
0026 // P1355R2:
0027 //  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1355r2.html
0028 // P1956R1:
0029 //  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1956r1.pdf
0030 //
0031 // When using a standard library that implements these functions, we use the
0032 // standard library's implementation.
0033
0034 #ifndef ABSL_NUMERIC_BITS_H_
0035 #define ABSL_NUMERIC_BITS_H_
0036
0037 #include <cstdint>
0038 #include <limits>
0039 #include <type_traits>
0040
0041 #include "absl/base/config.h"
0042
0043 #if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L
0044 #include <bit>
0045 #endif
0046
0047 #include "absl/base/attributes.h"
0048 #include "absl/numeric/internal/bits.h"
0049
0050 namespace absl {
0051 ABSL_NAMESPACE_BEGIN
0052
0053 // https://github.com/llvm/llvm-project/issues/64544
0054 // libc++ had the wrong signature for std::rotl and std::rotr
0055 // prior to libc++ 18.0.
0056 //
0057 #if (defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L) &&     \
0058     (!defined(_LIBCPP_VERSION) || _LIBCPP_VERSION >= 180000)
0059 using std::rotl;
0060 using std::rotr;
0061
0062 #else
0063
0064 // Rotating functions
0065 template <class T>
0066 ABSL_MUST_USE_RESULT constexpr
0067     typename std::enable_if<std::is_unsigned<T>::value, T>::type
0068     rotl(T x, int s) noexcept {
0069   return numeric_internal::RotateLeft(x, s);
0070 }
0071
0072 template <class T>
0073 ABSL_MUST_USE_RESULT constexpr
0074     typename std::enable_if<std::is_unsigned<T>::value, T>::type
0075     rotr(T x, int s) noexcept {
0076   return numeric_internal::RotateRight(x, s);
0077 }
0078
0079 #endif
0080
0081 // https://github.com/llvm/llvm-project/issues/64544
0082 // libc++ had the wrong signature for std::rotl and std::rotr
0083 // prior to libc++ 18.0.
0084 //
0085 #if (defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L)
0086
0087 using std::countl_one;
0088 using std::countl_zero;
0089 using std::countr_one;
0090 using std::countr_zero;
0091 using std::popcount;
0092
0093 #else
0094
0095 // Counting functions
0096 //
0097 // While these functions are typically constexpr, on some platforms, they may
0098 // not be marked as constexpr due to constraints of the compiler/available
0099 // intrinsics.
0100 template <class T>
0101 ABSL_INTERNAL_CONSTEXPR_CLZ inline
0102     typename std::enable_if<std::is_unsigned<T>::value, int>::type
0103     countl_zero(T x) noexcept {
0104   return numeric_internal::CountLeadingZeroes(x);
0105 }
0106
0107 template <class T>
0108 ABSL_INTERNAL_CONSTEXPR_CLZ inline
0109     typename std::enable_if<std::is_unsigned<T>::value, int>::type
0110     countl_one(T x) noexcept {
0111   // Avoid integer promotion to a wider type
0112   return countl_zero(static_cast<T>(~x));
0113 }
0114
0115 template <class T>
0116 ABSL_INTERNAL_CONSTEXPR_CTZ inline
0117     typename std::enable_if<std::is_unsigned<T>::value, int>::type
0118     countr_zero(T x) noexcept {
0119   return numeric_internal::CountTrailingZeroes(x);
0120 }
0121
0122 template <class T>
0123 ABSL_INTERNAL_CONSTEXPR_CTZ inline
0124     typename std::enable_if<std::is_unsigned<T>::value, int>::type
0125     countr_one(T x) noexcept {
0126   // Avoid integer promotion to a wider type
0127   return countr_zero(static_cast<T>(~x));
0128 }
0129
0130 template <class T>
0131 ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline
0132     typename std::enable_if<std::is_unsigned<T>::value, int>::type
0133     popcount(T x) noexcept {
0134   return numeric_internal::Popcount(x);
0135 }
0136
0137 #endif
0138
0139 #if (defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L)
0140
0141 using std::bit_ceil;
0142 using std::bit_floor;
0143 using std::bit_width;
0144 using std::has_single_bit;
0145
0146 #else
0147
0148 // Returns: true if x is an integral power of two; false otherwise.
0149 template <class T>
0150 constexpr inline typename std::enable_if<std::is_unsigned<T>::value, bool>::type
0151 has_single_bit(T x) noexcept {
0152   return x != 0 && (x & (x - 1)) == 0;
0153 }
0154
0155 // Returns: If x == 0, 0; otherwise one plus the base-2 logarithm of x, with any
0156 // fractional part discarded.
0157 template <class T>
0158 ABSL_INTERNAL_CONSTEXPR_CLZ inline
0159     typename std::enable_if<std::is_unsigned<T>::value, int>::type
0160     bit_width(T x) noexcept {
0161   return std::numeric_limits<T>::digits - countl_zero(x);
0162 }
0163
0164 // Returns: If x == 0, 0; otherwise the maximal value y such that
0165 // has_single_bit(y) is true and y <= x.
0166 template <class T>
0167 ABSL_INTERNAL_CONSTEXPR_CLZ inline
0168     typename std::enable_if<std::is_unsigned<T>::value, T>::type
0169     bit_floor(T x) noexcept {
0170   return x == 0 ? 0 : T{1} << (bit_width(x) - 1);
0171 }
0172
0173 // Returns: N, where N is the smallest power of 2 greater than or equal to x.
0174 //
0175 // Preconditions: N is representable as a value of type T.
0176 template <class T>
0177 ABSL_INTERNAL_CONSTEXPR_CLZ inline
0178     typename std::enable_if<std::is_unsigned<T>::value, T>::type
0179     bit_ceil(T x) {
0180   // If T is narrower than unsigned, T{1} << bit_width will be promoted.  We
0181   // want to force it to wraparound so that bit_ceil of an invalid value are not
0182   // core constant expressions.
0183   //
0184   // BitCeilNonPowerOf2 triggers an overflow in constexpr contexts if we would
0185   // undergo promotion to unsigned but not fit the result into T without
0186   // truncation.
0187   return has_single_bit(x) ? T{1} << (bit_width(x) - 1)
0188                            : numeric_internal::BitCeilNonPowerOf2(x);
0189 }
0190
0191 #endif
0192
0193 ABSL_NAMESPACE_END
0194 }  // namespace absl
0195
0196 #endif  // ABSL_NUMERIC_BITS_H_