[thirdparty/gcc.git] / libstdc++-v3 / include / std / bit

// <bit> -*- C++ -*-

// Copyright (C) 2018-2023 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file include/bit
 *  This is a Standard C++ Library header.
 */

#ifndef _GLIBCXX_BIT
#define _GLIBCXX_BIT 1

#pragma GCC system_header

#if __cplusplus >= 201402L

#include <type_traits>

#if _GLIBCXX_HOSTED || __has_include(<ext/numeric_traits.h>)
# include <ext/numeric_traits.h>
#else
# include <limits>
/// @cond undocumented
namespace __gnu_cxx
{
  template<typename _Tp>
    struct __int_traits
    {
      static constexpr int __digits = std::numeric_limits<_Tp>::digits;
      static constexpr _Tp __max = std::numeric_limits<_Tp>::max();
    };
}
/// @endcond
#endif

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**
   * @defgroup bit_manip Bit manipulation
   * @ingroup numerics
   *
   * Utilities for examining and manipulating individual bits.
   *
   * @{
   */

#if __cplusplus > 201703l && __has_builtin(__builtin_bit_cast)
#define __cpp_lib_bit_cast 201806L

  /// Create a value of type `To` from the bits of `from`.
  /**
   * @tparam _To   A trivially-copyable type.
   * @param __from A trivially-copyable object of the same size as `_To`.
   * @return       An object of type `_To`.
   * @since C++20
   */
  template<typename _To, typename _From>
    [[nodiscard]]
    constexpr _To
    bit_cast(const _From& __from) noexcept
#ifdef __cpp_concepts
    requires (sizeof(_To) == sizeof(_From))
      && __is_trivially_copyable(_To) && __is_trivially_copyable(_From)
#endif
    {
      return __builtin_bit_cast(_To, __from);
    }
#endif

#if __cplusplus > 202002L
#define __cpp_lib_byteswap 202110L

  /// Reverse order of bytes in the object representation of `value`.
  /**
   * @tparam _Tp     An integral type.
   * @param __value  An object of integer type.
   * @return         An object of the same type, with the bytes reversed.
   * @since C++23
   */
  template<typename _Tp>
    [[nodiscard]]
    constexpr enable_if_t<is_integral<_Tp>::value, _Tp>
    byteswap(_Tp __value) noexcept
    {
      if constexpr (sizeof(_Tp) == 1)
	return __value;
#if __cpp_if_consteval >= 202106L && __CHAR_BIT__ == 8
      if !consteval
	{
	  if constexpr (sizeof(_Tp) == 2)
	    return __builtin_bswap16(__value);
	  if constexpr (sizeof(_Tp) == 4)
	    return __builtin_bswap32(__value);
	  if constexpr (sizeof(_Tp) == 8)
	    return __builtin_bswap64(__value);
	  if constexpr (sizeof(_Tp) == 16)
#if __has_builtin(__builtin_bswap128)
	    return __builtin_bswap128(__value);
#else
	    return (__builtin_bswap64(__value >> 64)
		    | (static_cast<_Tp>(__builtin_bswap64(__value)) << 64));
#endif
	}
#endif

      // Fallback implementation that handles even __int24 etc.
      using _Up = typename __make_unsigned<__remove_cv_t<_Tp>>::__type;
      size_t __diff = __CHAR_BIT__ * (sizeof(_Tp) - 1);
      _Up __mask1 = static_cast<unsigned char>(~0);
      _Up __mask2 = __mask1 << __diff;
      _Up __val = __value;
      for (size_t __i = 0; __i < sizeof(_Tp) / 2; ++__i)
	{
	  _Up __byte1 = __val & __mask1;
	  _Up __byte2 = __val & __mask2;
	  __val = (__val ^ __byte1 ^ __byte2
		   ^ (__byte1 << __diff) ^ (__byte2 >> __diff));
	  __mask1 <<= __CHAR_BIT__;
	  __mask2 >>= __CHAR_BIT__;
	  __diff -= 2 * __CHAR_BIT__;
	}
      return __val;
    }
#endif

  /// @cond undoc

  template<typename _Tp>
    constexpr _Tp
    __rotl(_Tp __x, int __s) noexcept
    {
      constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
      if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
	{
	  // Variant for power of two _Nd which the compiler can
	  // easily pattern match.
	  constexpr unsigned __uNd = _Nd;
	  const unsigned __r = __s;
	  return (__x << (__r % __uNd)) | (__x >> ((-__r) % __uNd));
	}
      const int __r = __s % _Nd;
      if (__r == 0)
	return __x;
      else if (__r > 0)
	return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
      else
	return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r)
    }

  template<typename _Tp>
    constexpr _Tp
    __rotr(_Tp __x, int __s) noexcept
    {
      constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
      if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
	{
	  // Variant for power of two _Nd which the compiler can
	  // easily pattern match.
	  constexpr unsigned __uNd = _Nd;
	  const unsigned __r = __s;
	  return (__x >> (__r % __uNd)) | (__x << ((-__r) % __uNd));
	}
      const int __r = __s % _Nd;
      if (__r == 0)
	return __x;
      else if (__r > 0)
	return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
      else
	return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
    }

  template<typename _Tp>
    constexpr int
    __countl_zero(_Tp __x) noexcept
    {
      using __gnu_cxx::__int_traits;
      constexpr auto _Nd = __int_traits<_Tp>::__digits;

      if (__x == 0)
        return _Nd;

      constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
      constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
      constexpr auto _Nd_u = __int_traits<unsigned>::__digits;

      if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
	{
	  constexpr int __diff = _Nd_u - _Nd;
	  return __builtin_clz(__x) - __diff;
	}
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
	{
	  constexpr int __diff = _Nd_ul - _Nd;
	  return __builtin_clzl(__x) - __diff;
	}
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
	{
	  constexpr int __diff = _Nd_ull - _Nd;
	  return __builtin_clzll(__x) - __diff;
	}
      else // (_Nd > _Nd_ull)
	{
	  static_assert(_Nd <= (2 * _Nd_ull),
			"Maximum supported integer size is 128-bit");

	  unsigned long long __high = __x >> _Nd_ull;
	  if (__high != 0)
	    {
	      constexpr int __diff = (2 * _Nd_ull) - _Nd;
	      return __builtin_clzll(__high) - __diff;
	    }
	  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
	  unsigned long long __low = __x & __max_ull;
	  return (_Nd - _Nd_ull) + __builtin_clzll(__low);
	}
    }

  template<typename _Tp>
    constexpr int
    __countl_one(_Tp __x) noexcept
    {
      return std::__countl_zero<_Tp>((_Tp)~__x);
    }

  template<typename _Tp>
    constexpr int
    __countr_zero(_Tp __x) noexcept
    {
      using __gnu_cxx::__int_traits;
      constexpr auto _Nd = __int_traits<_Tp>::__digits;

      if (__x == 0)
        return _Nd;

      constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
      constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
      constexpr auto _Nd_u = __int_traits<unsigned>::__digits;

      if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
	return __builtin_ctz(__x);
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
	return __builtin_ctzl(__x);
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
	return __builtin_ctzll(__x);
      else // (_Nd > _Nd_ull)
	{
	  static_assert(_Nd <= (2 * _Nd_ull),
			"Maximum supported integer size is 128-bit");

	  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
	  unsigned long long __low = __x & __max_ull;
	  if (__low != 0)
	    return __builtin_ctzll(__low);
	  unsigned long long __high = __x >> _Nd_ull;
	  return __builtin_ctzll(__high) + _Nd_ull;
	}
    }

  template<typename _Tp>
    constexpr int
    __countr_one(_Tp __x) noexcept
    {
      return std::__countr_zero((_Tp)~__x);
    }

  template<typename _Tp>
    constexpr int
    __popcount(_Tp __x) noexcept
    {
      using __gnu_cxx::__int_traits;
      constexpr auto _Nd = __int_traits<_Tp>::__digits;

      constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
      constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
      constexpr auto _Nd_u = __int_traits<unsigned>::__digits;

      if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
	return __builtin_popcount(__x);
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
	return __builtin_popcountl(__x);
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
	return __builtin_popcountll(__x);
      else // (_Nd > _Nd_ull)
	{
	  static_assert(_Nd <= (2 * _Nd_ull),
			"Maximum supported integer size is 128-bit");

	  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
	  unsigned long long __low = __x & __max_ull;
	  unsigned long long __high = __x >> _Nd_ull;
	  return __builtin_popcountll(__low) + __builtin_popcountll(__high);
	}
    }

  template<typename _Tp>
    constexpr bool
    __has_single_bit(_Tp __x) noexcept
    { return std::__popcount(__x) == 1; }

  template<typename _Tp>
    constexpr _Tp
    __bit_ceil(_Tp __x) noexcept
    {
      using __gnu_cxx::__int_traits;
      constexpr auto _Nd = __int_traits<_Tp>::__digits;
      if (__x == 0 || __x == 1)
        return 1;
      auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
      // If the shift exponent equals _Nd then the correct result is not
      // representable as a value of _Tp, and so the result is undefined.
      // Want that undefined behaviour to be detected in constant expressions,
      // by UBSan, and by debug assertions.
      if (!std::__is_constant_evaluated())
	{
	  __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
	}

      using __promoted_type = decltype(__x << 1);
      if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
	{
	  // If __x undergoes integral promotion then shifting by _Nd is
	  // not undefined. In order to make the shift undefined, so that
	  // it is diagnosed in constant expressions and by UBsan, we also
	  // need to "promote" the shift exponent to be too large for the
	  // promoted type.
	  const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2;
	  __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
	}
      return (_Tp)1u << __shift_exponent;
    }

  template<typename _Tp>
    constexpr _Tp
    __bit_floor(_Tp __x) noexcept
    {
      constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
      if (__x == 0)
        return 0;
      return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
    }

  template<typename _Tp>
    constexpr int
    __bit_width(_Tp __x) noexcept
    {
      constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
      return _Nd - std::__countl_zero(__x);
    }

  /// @endcond

#if __cplusplus > 201703L

#define __cpp_lib_bitops 201907L

  /// @cond undoc
  template<typename _Tp, typename _Up = _Tp>
    using _If_is_unsigned_integer
      = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
  /// @endcond

  // [bit.rot], rotating

  /// Rotate `x` to the left by `s` bits.
  template<typename _Tp>
    [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
    rotl(_Tp __x, int __s) noexcept
    { return std::__rotl(__x, __s); }

  /// Rotate `x` to the right by `s` bits.
  template<typename _Tp>
    [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
    rotr(_Tp __x, int __s) noexcept
    { return std::__rotr(__x, __s); }

  // [bit.count], counting

  /// The number of contiguous zero bits, starting from the highest bit.
  template<typename _Tp>
    constexpr _If_is_unsigned_integer<_Tp, int>
    countl_zero(_Tp __x) noexcept
    { return std::__countl_zero(__x); }

  /// The number of contiguous one bits, starting from the highest bit.
  template<typename _Tp>
    constexpr _If_is_unsigned_integer<_Tp, int>
    countl_one(_Tp __x) noexcept
    { return std::__countl_one(__x); }

  /// The number of contiguous zero bits, starting from the lowest bit.
  template<typename _Tp>
    constexpr _If_is_unsigned_integer<_Tp, int>
    countr_zero(_Tp __x) noexcept
    { return std::__countr_zero(__x); }

  /// The number of contiguous one bits, starting from the lowest bit.
  template<typename _Tp>
    constexpr _If_is_unsigned_integer<_Tp, int>
    countr_one(_Tp __x) noexcept
    { return std::__countr_one(__x); }

  /// The number of bits set in `x`.
  template<typename _Tp>
    constexpr _If_is_unsigned_integer<_Tp, int>
    popcount(_Tp __x) noexcept
    { return std::__popcount(__x); }

  // [bit.pow.two], integral powers of 2

#define __cpp_lib_int_pow2 202002L

  /// True if `x` is a power of two, false otherwise.
  template<typename _Tp>
    constexpr _If_is_unsigned_integer<_Tp, bool>
    has_single_bit(_Tp __x) noexcept
    { return std::__has_single_bit(__x); }

  /// The smallest power-of-two not less than `x`.
  template<typename _Tp>
    constexpr _If_is_unsigned_integer<_Tp>
    bit_ceil(_Tp __x) noexcept
    { return std::__bit_ceil(__x); }

  /// The largest power-of-two not greater than `x`.
  template<typename _Tp>
    constexpr _If_is_unsigned_integer<_Tp>
    bit_floor(_Tp __x) noexcept
    { return std::__bit_floor(__x); }

  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // 3656. Inconsistent bit operations returning a count
  /// The smallest integer greater than the base-2 logarithm of `x`.
  template<typename _Tp>
    constexpr _If_is_unsigned_integer<_Tp, int>
    bit_width(_Tp __x) noexcept
    { return std::__bit_width(__x); }

#define __cpp_lib_endian 201907L

  /// Byte order constants
  /**
   * The platform endianness can be checked by comparing `std::endian::native`
   * to one of `std::endian::big` or `std::endian::little`.
   *
   * @since C++20
   */
  enum class endian
  {
    little = __ORDER_LITTLE_ENDIAN__,
    big    = __ORDER_BIG_ENDIAN__,
    native = __BYTE_ORDER__
  };
#endif // C++2a

  /// @}

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std

#endif // C++14
#endif // _GLIBCXX_BIT
Commit	Line	Data
f3e91052 JW	1	// <bit> -- C++ --
f3e91052 JW	2
83ffe9cd	3	// Copyright (C) 2018-2023 Free Software Foundation, Inc.
f3e91052 JW	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the
	7	// terms of the GNU General Public License as published by the
	8	// Free Software Foundation; either version 3, or (at your option)
	9	// any later version.
	10
	11	// This library is distributed in the hope that it will be useful,
	12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	// GNU General Public License for more details.
	15
	16	// Under Section 7 of GPL version 3, you are granted additional
	17	// permissions described in the GCC Runtime Library Exception, version
	18	// 3.1, as published by the Free Software Foundation.
	19
	20	// You should have received a copy of the GNU General Public License and
	21	// a copy of the GCC Runtime Library Exception along with this program;
	22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
	23	// <http://www.gnu.org/licenses/>.
	24
	25	/** @file include/bit
	26	* This is a Standard C++ Library header.
	27	*/
	28
	29	#ifndef _GLIBCXX_BIT
	30	#define _GLIBCXX_BIT 1
	31
	32	#pragma GCC system_header
	33
	34	#if __cplusplus >= 201402L
	35
	36	#include <type_traits>
474cb5a0	37
cf0fded5	38	#if _GLIBCXX_HOSTED \|\| __has_include(<ext/numeric_traits.h>)
474cb5a0 JW	39	# include <ext/numeric_traits.h>
	40	#else
	41	# include <limits>
	42	/// @cond undocumented
	43	namespace __gnu_cxx
	44	{
	45	template<typename _Tp>
	46	struct __int_traits
	47	{
	48	static constexpr int __digits = std::numeric_limits<_Tp>::digits;
	49	static constexpr _Tp __max = std::numeric_limits<_Tp>::max();
	50	};
	51	}
	52	/// @endcond
	53	#endif
f3e91052 JW	54
	55	namespace std _GLIBCXX_VISIBILITY(default)
	56	{
	57	_GLIBCXX_BEGIN_NAMESPACE_VERSION
	58
27e6c1f4 JW	59	/**
	60	* @defgroup bit_manip Bit manipulation
	61	* @ingroup numerics
	62	*
	63	* Utilities for examining and manipulating individual bits.
	64	*
	65	* @{
	66	*/
	67
9e433b34 JW	68	#if __cplusplus > 201703l && __has_builtin(__builtin_bit_cast)
	69	#define __cpp_lib_bit_cast 201806L
	70
	71	/// Create a value of type `To` from the bits of `from`.
674ec679 JW	72	/**
	73	* @tparam _To A trivially-copyable type.
	74	* @param __from A trivially-copyable object of the same size as `_To`.
	75	* @return An object of type `_To`.
	76	* @since C++20
	77	*/
9e433b34	78	template<typename _To, typename _From>
406f58e1	79	[[nodiscard]]
9e433b34 JW	80	constexpr _To
9e433b34 JW	81	bit_cast(const _From& __from) noexcept
4894d69a JW	82	#ifdef __cpp_concepts
	83	requires (sizeof(_To) == sizeof(_From))
	84	&& __is_trivially_copyable(_To) && __is_trivially_copyable(_From)
	85	#endif
9e433b34 JW	86	{
	87	return __builtin_bit_cast(_To, __from);
	88	}
	89	#endif
	90
7393fa8b JJ	91	#if __cplusplus > 202002L
	92	#define __cpp_lib_byteswap 202110L
	93
	94	/// Reverse order of bytes in the object representation of `value`.
674ec679 JW	95	/**
	96	* @tparam _Tp An integral type.
	97	* @param __value An object of integer type.
	98	* @return An object of the same type, with the bytes reversed.
	99	* @since C++23
	100	*/
7393fa8b	101	template<typename _Tp>
92084a6d	102	[[nodiscard]]
7393fa8b JJ	103	constexpr enable_if_t<is_integral<_Tp>::value, _Tp>
	104	byteswap(_Tp __value) noexcept
	105	{
	106	if constexpr (sizeof(_Tp) == 1)
	107	return __value;
	108	#if __cpp_if_consteval >= 202106L && __CHAR_BIT__ == 8
	109	if !consteval
	110	{
	111	if constexpr (sizeof(_Tp) == 2)
	112	return __builtin_bswap16(__value);
	113	if constexpr (sizeof(_Tp) == 4)
	114	return __builtin_bswap32(__value);
	115	if constexpr (sizeof(_Tp) == 8)
	116	return __builtin_bswap64(__value);
	117	if constexpr (sizeof(_Tp) == 16)
	118	#if __has_builtin(__builtin_bswap128)
	119	return __builtin_bswap128(__value);
	120	#else
	121	return (__builtin_bswap64(__value >> 64)
	122	\| (static_cast<_Tp>(__builtin_bswap64(__value)) << 64));
	123	#endif
	124	}
	125	#endif
	126
	127	// Fallback implementation that handles even __int24 etc.
	128	using _Up = typename __make_unsigned<__remove_cv_t<_Tp>>::__type;
	129	size_t __diff = __CHAR_BIT__ * (sizeof(_Tp) - 1);
	130	_Up __mask1 = static_cast<unsigned char>(~0);
	131	_Up __mask2 = __mask1 << __diff;
	132	_Up __val = __value;
	133	for (size_t __i = 0; __i < sizeof(_Tp) / 2; ++__i)
	134	{
	135	_Up __byte1 = __val & __mask1;
	136	_Up __byte2 = __val & __mask2;
	137	__val = (__val ^ __byte1 ^ __byte2
	138	^ (__byte1 << __diff) ^ (__byte2 >> __diff));
	139	__mask1 <<= __CHAR_BIT__;
	140	__mask2 >>= __CHAR_BIT__;
	141	__diff -= 2 * __CHAR_BIT__;
	142	}
	143	return __val;
	144	}
	145	#endif
	146
27e6c1f4 JW	147	/// @cond undoc
27e6c1f4 JW	148
f3e91052 JW	149	template<typename _Tp>
f3e91052 JW	150	constexpr _Tp
f35da524	151	__rotl(_Tp __x, int __s) noexcept
f3e91052	152	{
eb04805b	153	constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
84185598 JJ	154	if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
	155	{
	156	// Variant for power of two _Nd which the compiler can
	157	// easily pattern match.
	158	constexpr unsigned __uNd = _Nd;
	159	const unsigned __r = __s;
	160	return (__x << (__r % __uNd)) \| (__x >> ((-__r) % __uNd));
	161	}
f35da524 JW	162	const int __r = __s % _Nd;
	163	if (__r == 0)
	164	return __x;
	165	else if (__r > 0)
	166	return (__x << __r) \| (__x >> ((_Nd - __r) % _Nd));
	167	else
	168	return (__x >> -__r) \| (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r)
f3e91052 JW	169	}
	170
	171	template<typename _Tp>
	172	constexpr _Tp
f35da524	173	__rotr(_Tp __x, int __s) noexcept
f3e91052	174	{
eb04805b	175	constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
84185598 JJ	176	if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
	177	{
	178	// Variant for power of two _Nd which the compiler can
	179	// easily pattern match.
	180	constexpr unsigned __uNd = _Nd;
	181	const unsigned __r = __s;
	182	return (__x >> (__r % __uNd)) \| (__x << ((-__r) % __uNd));
	183	}
f35da524 JW	184	const int __r = __s % _Nd;
	185	if (__r == 0)
	186	return __x;
	187	else if (__r > 0)
	188	return (__x >> __r) \| (__x << ((_Nd - __r) % _Nd));
	189	else
	190	return (__x << -__r) \| (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
f3e91052 JW	191	}
	192
	193	template<typename _Tp>
	194	constexpr int
	195	__countl_zero(_Tp __x) noexcept
	196	{
eb04805b JW	197	using __gnu_cxx::__int_traits;
eb04805b JW	198	constexpr auto _Nd = __int_traits<_Tp>::__digits;
f3e91052 JW	199
f3e91052 JW	200	if (__x == 0)
337dc307	201	return _Nd;
f3e91052	202
eb04805b JW	203	constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
	204	constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
	205	constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
f3e91052	206
337dc307	207	if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
f3e91052	208	{
337dc307	209	constexpr int __diff = _Nd_u - _Nd;
f3e91052 JW	210	return __builtin_clz(__x) - __diff;
f3e91052 JW	211	}
337dc307	212	else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
f3e91052	213	{
337dc307	214	constexpr int __diff = _Nd_ul - _Nd;
f3e91052 JW	215	return __builtin_clzl(__x) - __diff;
f3e91052 JW	216	}
337dc307	217	else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
f3e91052	218	{
337dc307	219	constexpr int __diff = _Nd_ull - _Nd;
f3e91052 JW	220	return __builtin_clzll(__x) - __diff;
f3e91052 JW	221	}
337dc307	222	else // (_Nd > _Nd_ull)
f3e91052	223	{
337dc307	224	static_assert(_Nd <= (2 * _Nd_ull),
f3e91052 JW	225	"Maximum supported integer size is 128-bit");
f3e91052 JW	226
337dc307	227	unsigned long long __high = __x >> _Nd_ull;
f3e91052 JW	228	if (__high != 0)
f3e91052 JW	229	{
337dc307	230	constexpr int __diff = (2 * _Nd_ull) - _Nd;
f3e91052 JW	231	return __builtin_clzll(__high) - __diff;
f3e91052 JW	232	}
eb04805b	233	constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
337dc307 JW	234	unsigned long long __low = __x & __max_ull;
337dc307 JW	235	return (_Nd - _Nd_ull) + __builtin_clzll(__low);
f3e91052 JW	236	}
	237	}
	238
	239	template<typename _Tp>
	240	constexpr int
	241	__countl_one(_Tp __x) noexcept
	242	{
f3e91052 JW	243	return std::__countl_zero<_Tp>((_Tp)~__x);
	244	}
	245
	246	template<typename _Tp>
	247	constexpr int
	248	__countr_zero(_Tp __x) noexcept
	249	{
eb04805b JW	250	using __gnu_cxx::__int_traits;
eb04805b JW	251	constexpr auto _Nd = __int_traits<_Tp>::__digits;
f3e91052 JW	252
f3e91052 JW	253	if (__x == 0)
337dc307	254	return _Nd;
f3e91052	255
eb04805b JW	256	constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
	257	constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
	258	constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
f3e91052	259
337dc307	260	if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
f3e91052	261	return __builtin_ctz(__x);
337dc307	262	else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
f3e91052	263	return __builtin_ctzl(__x);
337dc307	264	else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
f3e91052	265	return __builtin_ctzll(__x);
337dc307	266	else // (_Nd > _Nd_ull)
f3e91052	267	{
337dc307	268	static_assert(_Nd <= (2 * _Nd_ull),
f3e91052 JW	269	"Maximum supported integer size is 128-bit");
f3e91052 JW	270
eb04805b	271	constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
337dc307	272	unsigned long long __low = __x & __max_ull;
f3e91052 JW	273	if (__low != 0)
f3e91052 JW	274	return __builtin_ctzll(__low);
337dc307 JW	275	unsigned long long __high = __x >> _Nd_ull;
337dc307 JW	276	return __builtin_ctzll(__high) + _Nd_ull;
f3e91052 JW	277	}
	278	}
	279
	280	template<typename _Tp>
	281	constexpr int
	282	__countr_one(_Tp __x) noexcept
	283	{
f3e91052 JW	284	return std::__countr_zero((_Tp)~__x);
	285	}
	286
	287	template<typename _Tp>
	288	constexpr int
	289	__popcount(_Tp __x) noexcept
	290	{
eb04805b JW	291	using __gnu_cxx::__int_traits;
eb04805b JW	292	constexpr auto _Nd = __int_traits<_Tp>::__digits;
f3e91052	293
eb04805b JW	294	constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
	295	constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
	296	constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
f3e91052	297
337dc307	298	if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
f3e91052	299	return __builtin_popcount(__x);
337dc307	300	else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
f3e91052	301	return __builtin_popcountl(__x);
337dc307	302	else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
f3e91052	303	return __builtin_popcountll(__x);
337dc307	304	else // (_Nd > _Nd_ull)
f3e91052	305	{
337dc307	306	static_assert(_Nd <= (2 * _Nd_ull),
f3e91052 JW	307	"Maximum supported integer size is 128-bit");
f3e91052 JW	308
eb04805b	309	constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
337dc307 JW	310	unsigned long long __low = __x & __max_ull;
337dc307 JW	311	unsigned long long __high = __x >> _Nd_ull;
f3e91052 JW	312	return __builtin_popcountll(__low) + __builtin_popcountll(__high);
	313	}
	314	}
	315
	316	template<typename _Tp>
	317	constexpr bool
9866abe3	318	__has_single_bit(_Tp __x) noexcept
f3e91052 JW	319	{ return std::__popcount(__x) == 1; }
	320
	321	template<typename _Tp>
	322	constexpr _Tp
9866abe3	323	__bit_ceil(_Tp __x) noexcept
f3e91052	324	{
eb04805b JW	325	using __gnu_cxx::__int_traits;
eb04805b JW	326	constexpr auto _Nd = __int_traits<_Tp>::__digits;
2fb17d2d	327	if (__x == 0 \|\| __x == 1)
f3e91052	328	return 1;
281ab2fb JW	329	auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
	330	// If the shift exponent equals _Nd then the correct result is not
	331	// representable as a value of _Tp, and so the result is undefined.
	332	// Want that undefined behaviour to be detected in constant expressions,
	333	// by UBSan, and by debug assertions.
74d14778	334	if (!std::__is_constant_evaluated())
3b39526e	335	{
eb04805b	336	__glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
3b39526e	337	}
74d14778	338
281ab2fb JW	339	using __promoted_type = decltype(__x << 1);
	340	if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
	341	{
	342	// If __x undergoes integral promotion then shifting by _Nd is
	343	// not undefined. In order to make the shift undefined, so that
	344	// it is diagnosed in constant expressions and by UBsan, we also
	345	// need to "promote" the shift exponent to be too large for the
	346	// promoted type.
	347	const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2;
	348	__shift_exponent \|= (__shift_exponent & _Nd) << __extra_exp;
	349	}
	350	return (_Tp)1u << __shift_exponent;
f3e91052 JW	351	}
	352
	353	template<typename _Tp>
	354	constexpr _Tp
9866abe3	355	__bit_floor(_Tp __x) noexcept
f3e91052	356	{
eb04805b	357	constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
f3e91052 JW	358	if (__x == 0)
	359	return 0;
	360	return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
	361	}
	362
	363	template<typename _Tp>
45813280	364	constexpr int
9866abe3	365	__bit_width(_Tp __x) noexcept
f3e91052	366	{
eb04805b	367	constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
f3e91052 JW	368	return _Nd - std::__countl_zero(__x);
	369	}
	370
27e6c1f4 JW	371	/// @endcond
27e6c1f4 JW	372
f3e91052 JW	373	#if __cplusplus > 201703L
f3e91052 JW	374
0d58d88d JW	375	#define __cpp_lib_bitops 201907L
0d58d88d JW	376
27e6c1f4	377	/// @cond undoc
f3e91052 JW	378	template<typename _Tp, typename _Up = _Tp>
f3e91052 JW	379	using _If_is_unsigned_integer
47f79054	380	= enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
27e6c1f4	381	/// @endcond
f3e91052	382
f35da524	383	// [bit.rot], rotating
f3e91052	384
27e6c1f4	385	/// Rotate `x` to the left by `s` bits.
f3e91052	386	template<typename _Tp>
f35da524 JW	387	[[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
f35da524 JW	388	rotl(_Tp __x, int __s) noexcept
f3e91052 JW	389	{ return std::__rotl(__x, __s); }
f3e91052 JW	390
27e6c1f4	391	/// Rotate `x` to the right by `s` bits.
f3e91052	392	template<typename _Tp>
f35da524 JW	393	[[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
f35da524 JW	394	rotr(_Tp __x, int __s) noexcept
f3e91052 JW	395	{ return std::__rotr(__x, __s); }
f3e91052 JW	396
f35da524	397	// [bit.count], counting
f3e91052	398
27e6c1f4	399	/// The number of contiguous zero bits, starting from the highest bit.
f3e91052 JW	400	template<typename _Tp>
	401	constexpr _If_is_unsigned_integer<_Tp, int>
	402	countl_zero(_Tp __x) noexcept
	403	{ return std::__countl_zero(__x); }
	404
27e6c1f4	405	/// The number of contiguous one bits, starting from the highest bit.
f3e91052 JW	406	template<typename _Tp>
	407	constexpr _If_is_unsigned_integer<_Tp, int>
	408	countl_one(_Tp __x) noexcept
	409	{ return std::__countl_one(__x); }
	410
27e6c1f4	411	/// The number of contiguous zero bits, starting from the lowest bit.
f3e91052 JW	412	template<typename _Tp>
	413	constexpr _If_is_unsigned_integer<_Tp, int>
	414	countr_zero(_Tp __x) noexcept
	415	{ return std::__countr_zero(__x); }
	416
27e6c1f4	417	/// The number of contiguous one bits, starting from the lowest bit.
f3e91052 JW	418	template<typename _Tp>
	419	constexpr _If_is_unsigned_integer<_Tp, int>
	420	countr_one(_Tp __x) noexcept
	421	{ return std::__countr_one(__x); }
	422
27e6c1f4	423	/// The number of bits set in `x`.
f3e91052 JW	424	template<typename _Tp>
	425	constexpr _If_is_unsigned_integer<_Tp, int>
	426	popcount(_Tp __x) noexcept
	427	{ return std::__popcount(__x); }
f3e91052	428
f35da524	429	// [bit.pow.two], integral powers of 2
f3e91052	430
9866abe3 JW	431	#define __cpp_lib_int_pow2 202002L
9866abe3 JW	432
27e6c1f4	433	/// True if `x` is a power of two, false otherwise.
f3e91052 JW	434	template<typename _Tp>
f3e91052 JW	435	constexpr _If_is_unsigned_integer<_Tp, bool>
9866abe3 JW	436	has_single_bit(_Tp __x) noexcept
9866abe3 JW	437	{ return std::__has_single_bit(__x); }
f3e91052	438
27e6c1f4	439	/// The smallest power-of-two not less than `x`.
f3e91052 JW	440	template<typename _Tp>
f3e91052 JW	441	constexpr _If_is_unsigned_integer<_Tp>
9866abe3 JW	442	bit_ceil(_Tp __x) noexcept
9866abe3 JW	443	{ return std::__bit_ceil(__x); }
f3e91052	444
27e6c1f4	445	/// The largest power-of-two not greater than `x`.
f3e91052 JW	446	template<typename _Tp>
f3e91052 JW	447	constexpr _If_is_unsigned_integer<_Tp>
9866abe3 JW	448	bit_floor(_Tp __x) noexcept
9866abe3 JW	449	{ return std::__bit_floor(__x); }
f3e91052	450
45813280 JW	451	// _GLIBCXX_RESOLVE_LIB_DEFECTS
45813280 JW	452	// 3656. Inconsistent bit operations returning a count
27e6c1f4	453	/// The smallest integer greater than the base-2 logarithm of `x`.
f3e91052	454	template<typename _Tp>
45813280	455	constexpr _If_is_unsigned_integer<_Tp, int>
9866abe3 JW	456	bit_width(_Tp __x) noexcept
9866abe3 JW	457	{ return std::__bit_width(__x); }
f3e91052	458
a5378f9b JW	459	#define __cpp_lib_endian 201907L
a5378f9b JW	460
674ec679 JW	461	/// Byte order constants
	462	/**
	463	* The platform endianness can be checked by comparing `std::endian::native`
	464	* to one of `std::endian::big` or `std::endian::little`.
	465	*
	466	* @since C++20
	467	*/
45c7215c JW	468	enum class endian
	469	{
	470	little = __ORDER_LITTLE_ENDIAN__,
	471	big = __ORDER_BIG_ENDIAN__,
	472	native = __BYTE_ORDER__
	473	};
f3e91052 JW	474	#endif // C++2a
f3e91052 JW	475
27e6c1f4 JW	476	/// @}
27e6c1f4 JW	477
f3e91052 JW	478	_GLIBCXX_END_NAMESPACE_VERSION
	479	} // namespace std
	480
	481	#endif // C++14
	482	#endif // _GLIBCXX_BIT