1760c2415Smrg// <bit> -*- C++ -*- 2760c2415Smrg 3*0bfacb9bSmrg// Copyright (C) 2018-2020 Free Software Foundation, Inc. 4760c2415Smrg// 5760c2415Smrg// This file is part of the GNU ISO C++ Library. This library is free 6760c2415Smrg// software; you can redistribute it and/or modify it under the 7760c2415Smrg// terms of the GNU General Public License as published by the 8760c2415Smrg// Free Software Foundation; either version 3, or (at your option) 9760c2415Smrg// any later version. 10760c2415Smrg 11760c2415Smrg// This library is distributed in the hope that it will be useful, 12760c2415Smrg// but WITHOUT ANY WARRANTY; without even the implied warranty of 13760c2415Smrg// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14760c2415Smrg// GNU General Public License for more details. 15760c2415Smrg 16760c2415Smrg// Under Section 7 of GPL version 3, you are granted additional 17760c2415Smrg// permissions described in the GCC Runtime Library Exception, version 18760c2415Smrg// 3.1, as published by the Free Software Foundation. 19760c2415Smrg 20760c2415Smrg// You should have received a copy of the GNU General Public License and 21760c2415Smrg// a copy of the GCC Runtime Library Exception along with this program; 22760c2415Smrg// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23760c2415Smrg// <http://www.gnu.org/licenses/>. 24760c2415Smrg 25760c2415Smrg/** @file include/bit 26760c2415Smrg * This is a Standard C++ Library header. 27760c2415Smrg */ 28760c2415Smrg 29760c2415Smrg#ifndef _GLIBCXX_BIT 30760c2415Smrg#define _GLIBCXX_BIT 1 31760c2415Smrg 32760c2415Smrg#pragma GCC system_header 33760c2415Smrg 34760c2415Smrg#if __cplusplus >= 201402L 35760c2415Smrg 36760c2415Smrg#include <type_traits> 37*0bfacb9bSmrg 38*0bfacb9bSmrg#if _GLIBCXX_HOSTED 39*0bfacb9bSmrg# include <ext/numeric_traits.h> 40*0bfacb9bSmrg#else 41760c2415Smrg# include <limits> 42*0bfacb9bSmrg/// @cond undocumented 43*0bfacb9bSmrgnamespace __gnu_cxx 44*0bfacb9bSmrg{ 45*0bfacb9bSmrg template<typename _Tp> 46*0bfacb9bSmrg struct __int_traits 47*0bfacb9bSmrg { 48*0bfacb9bSmrg static constexpr int __digits = std::numeric_limits<_Tp>::digits; 49*0bfacb9bSmrg static constexpr _Tp __max = std::numeric_limits<_Tp>::max(); 50*0bfacb9bSmrg }; 51*0bfacb9bSmrg} 52*0bfacb9bSmrg/// @endcond 53*0bfacb9bSmrg#endif 54760c2415Smrg 55760c2415Smrgnamespace std _GLIBCXX_VISIBILITY(default) 56760c2415Smrg{ 57760c2415Smrg_GLIBCXX_BEGIN_NAMESPACE_VERSION 58760c2415Smrg 59*0bfacb9bSmrg /** 60*0bfacb9bSmrg * @defgroup bit_manip Bit manipulation 61*0bfacb9bSmrg * @ingroup numerics 62*0bfacb9bSmrg * 63*0bfacb9bSmrg * Utilities for examining and manipulating individual bits. 64*0bfacb9bSmrg * 65*0bfacb9bSmrg * @{ 66*0bfacb9bSmrg */ 67*0bfacb9bSmrg 68*0bfacb9bSmrg /// @cond undoc 69*0bfacb9bSmrg 70760c2415Smrg template<typename _Tp> 71760c2415Smrg constexpr _Tp 72760c2415Smrg __rotl(_Tp __x, int __s) noexcept 73760c2415Smrg { 74*0bfacb9bSmrg constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 75760c2415Smrg const int __r = __s % _Nd; 76760c2415Smrg if (__r == 0) 77760c2415Smrg return __x; 78760c2415Smrg else if (__r > 0) 79760c2415Smrg return (__x << __r) | (__x >> ((_Nd - __r) % _Nd)); 80760c2415Smrg else 81760c2415Smrg return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r) 82760c2415Smrg } 83760c2415Smrg 84760c2415Smrg template<typename _Tp> 85760c2415Smrg constexpr _Tp 86760c2415Smrg __rotr(_Tp __x, int __s) noexcept 87760c2415Smrg { 88*0bfacb9bSmrg constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 89760c2415Smrg const int __r = __s % _Nd; 90760c2415Smrg if (__r == 0) 91760c2415Smrg return __x; 92760c2415Smrg else if (__r > 0) 93760c2415Smrg return (__x >> __r) | (__x << ((_Nd - __r) % _Nd)); 94760c2415Smrg else 95760c2415Smrg return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r) 96760c2415Smrg } 97760c2415Smrg 98760c2415Smrg template<typename _Tp> 99760c2415Smrg constexpr int 100760c2415Smrg __countl_zero(_Tp __x) noexcept 101760c2415Smrg { 102*0bfacb9bSmrg using __gnu_cxx::__int_traits; 103*0bfacb9bSmrg constexpr auto _Nd = __int_traits<_Tp>::__digits; 104760c2415Smrg 105760c2415Smrg if (__x == 0) 106760c2415Smrg return _Nd; 107760c2415Smrg 108*0bfacb9bSmrg constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits; 109*0bfacb9bSmrg constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits; 110*0bfacb9bSmrg constexpr auto _Nd_u = __int_traits<unsigned>::__digits; 111760c2415Smrg 112760c2415Smrg if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) 113760c2415Smrg { 114760c2415Smrg constexpr int __diff = _Nd_u - _Nd; 115760c2415Smrg return __builtin_clz(__x) - __diff; 116760c2415Smrg } 117760c2415Smrg else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) 118760c2415Smrg { 119760c2415Smrg constexpr int __diff = _Nd_ul - _Nd; 120760c2415Smrg return __builtin_clzl(__x) - __diff; 121760c2415Smrg } 122760c2415Smrg else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) 123760c2415Smrg { 124760c2415Smrg constexpr int __diff = _Nd_ull - _Nd; 125760c2415Smrg return __builtin_clzll(__x) - __diff; 126760c2415Smrg } 127760c2415Smrg else // (_Nd > _Nd_ull) 128760c2415Smrg { 129760c2415Smrg static_assert(_Nd <= (2 * _Nd_ull), 130760c2415Smrg "Maximum supported integer size is 128-bit"); 131760c2415Smrg 132760c2415Smrg unsigned long long __high = __x >> _Nd_ull; 133760c2415Smrg if (__high != 0) 134760c2415Smrg { 135760c2415Smrg constexpr int __diff = (2 * _Nd_ull) - _Nd; 136760c2415Smrg return __builtin_clzll(__high) - __diff; 137760c2415Smrg } 138*0bfacb9bSmrg constexpr auto __max_ull = __int_traits<unsigned long long>::__max; 139760c2415Smrg unsigned long long __low = __x & __max_ull; 140760c2415Smrg return (_Nd - _Nd_ull) + __builtin_clzll(__low); 141760c2415Smrg } 142760c2415Smrg } 143760c2415Smrg 144760c2415Smrg template<typename _Tp> 145760c2415Smrg constexpr int 146760c2415Smrg __countl_one(_Tp __x) noexcept 147760c2415Smrg { 148760c2415Smrg return std::__countl_zero<_Tp>((_Tp)~__x); 149760c2415Smrg } 150760c2415Smrg 151760c2415Smrg template<typename _Tp> 152760c2415Smrg constexpr int 153760c2415Smrg __countr_zero(_Tp __x) noexcept 154760c2415Smrg { 155*0bfacb9bSmrg using __gnu_cxx::__int_traits; 156*0bfacb9bSmrg constexpr auto _Nd = __int_traits<_Tp>::__digits; 157760c2415Smrg 158760c2415Smrg if (__x == 0) 159760c2415Smrg return _Nd; 160760c2415Smrg 161*0bfacb9bSmrg constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits; 162*0bfacb9bSmrg constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits; 163*0bfacb9bSmrg constexpr auto _Nd_u = __int_traits<unsigned>::__digits; 164760c2415Smrg 165760c2415Smrg if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) 166760c2415Smrg return __builtin_ctz(__x); 167760c2415Smrg else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) 168760c2415Smrg return __builtin_ctzl(__x); 169760c2415Smrg else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) 170760c2415Smrg return __builtin_ctzll(__x); 171760c2415Smrg else // (_Nd > _Nd_ull) 172760c2415Smrg { 173760c2415Smrg static_assert(_Nd <= (2 * _Nd_ull), 174760c2415Smrg "Maximum supported integer size is 128-bit"); 175760c2415Smrg 176*0bfacb9bSmrg constexpr auto __max_ull = __int_traits<unsigned long long>::__max; 177760c2415Smrg unsigned long long __low = __x & __max_ull; 178760c2415Smrg if (__low != 0) 179760c2415Smrg return __builtin_ctzll(__low); 180760c2415Smrg unsigned long long __high = __x >> _Nd_ull; 181760c2415Smrg return __builtin_ctzll(__high) + _Nd_ull; 182760c2415Smrg } 183760c2415Smrg } 184760c2415Smrg 185760c2415Smrg template<typename _Tp> 186760c2415Smrg constexpr int 187760c2415Smrg __countr_one(_Tp __x) noexcept 188760c2415Smrg { 189760c2415Smrg return std::__countr_zero((_Tp)~__x); 190760c2415Smrg } 191760c2415Smrg 192760c2415Smrg template<typename _Tp> 193760c2415Smrg constexpr int 194760c2415Smrg __popcount(_Tp __x) noexcept 195760c2415Smrg { 196*0bfacb9bSmrg using __gnu_cxx::__int_traits; 197*0bfacb9bSmrg constexpr auto _Nd = __int_traits<_Tp>::__digits; 198760c2415Smrg 199*0bfacb9bSmrg constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits; 200*0bfacb9bSmrg constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits; 201*0bfacb9bSmrg constexpr auto _Nd_u = __int_traits<unsigned>::__digits; 202760c2415Smrg 203760c2415Smrg if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) 204760c2415Smrg return __builtin_popcount(__x); 205760c2415Smrg else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) 206760c2415Smrg return __builtin_popcountl(__x); 207760c2415Smrg else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) 208760c2415Smrg return __builtin_popcountll(__x); 209760c2415Smrg else // (_Nd > _Nd_ull) 210760c2415Smrg { 211760c2415Smrg static_assert(_Nd <= (2 * _Nd_ull), 212760c2415Smrg "Maximum supported integer size is 128-bit"); 213760c2415Smrg 214*0bfacb9bSmrg constexpr auto __max_ull = __int_traits<unsigned long long>::__max; 215760c2415Smrg unsigned long long __low = __x & __max_ull; 216760c2415Smrg unsigned long long __high = __x >> _Nd_ull; 217760c2415Smrg return __builtin_popcountll(__low) + __builtin_popcountll(__high); 218760c2415Smrg } 219760c2415Smrg } 220760c2415Smrg 221760c2415Smrg template<typename _Tp> 222760c2415Smrg constexpr bool 223*0bfacb9bSmrg __has_single_bit(_Tp __x) noexcept 224760c2415Smrg { return std::__popcount(__x) == 1; } 225760c2415Smrg 226760c2415Smrg template<typename _Tp> 227760c2415Smrg constexpr _Tp 228*0bfacb9bSmrg __bit_ceil(_Tp __x) noexcept 229760c2415Smrg { 230*0bfacb9bSmrg using __gnu_cxx::__int_traits; 231*0bfacb9bSmrg constexpr auto _Nd = __int_traits<_Tp>::__digits; 232760c2415Smrg if (__x == 0 || __x == 1) 233760c2415Smrg return 1; 234760c2415Smrg auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u)); 235760c2415Smrg // If the shift exponent equals _Nd then the correct result is not 236760c2415Smrg // representable as a value of _Tp, and so the result is undefined. 237760c2415Smrg // Want that undefined behaviour to be detected in constant expressions, 238760c2415Smrg // by UBSan, and by debug assertions. 239760c2415Smrg#ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED 240760c2415Smrg if (!__builtin_is_constant_evaluated()) 241*0bfacb9bSmrg { 242*0bfacb9bSmrg __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits ); 243*0bfacb9bSmrg } 244760c2415Smrg#endif 245760c2415Smrg using __promoted_type = decltype(__x << 1); 246760c2415Smrg if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value) 247760c2415Smrg { 248760c2415Smrg // If __x undergoes integral promotion then shifting by _Nd is 249760c2415Smrg // not undefined. In order to make the shift undefined, so that 250760c2415Smrg // it is diagnosed in constant expressions and by UBsan, we also 251760c2415Smrg // need to "promote" the shift exponent to be too large for the 252760c2415Smrg // promoted type. 253760c2415Smrg const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2; 254760c2415Smrg __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp; 255760c2415Smrg } 256760c2415Smrg return (_Tp)1u << __shift_exponent; 257760c2415Smrg } 258760c2415Smrg 259760c2415Smrg template<typename _Tp> 260760c2415Smrg constexpr _Tp 261*0bfacb9bSmrg __bit_floor(_Tp __x) noexcept 262760c2415Smrg { 263*0bfacb9bSmrg constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 264760c2415Smrg if (__x == 0) 265760c2415Smrg return 0; 266760c2415Smrg return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1))); 267760c2415Smrg } 268760c2415Smrg 269760c2415Smrg template<typename _Tp> 270760c2415Smrg constexpr _Tp 271*0bfacb9bSmrg __bit_width(_Tp __x) noexcept 272760c2415Smrg { 273*0bfacb9bSmrg constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 274760c2415Smrg return _Nd - std::__countl_zero(__x); 275760c2415Smrg } 276760c2415Smrg 277*0bfacb9bSmrg /// @endcond 278*0bfacb9bSmrg 279760c2415Smrg#if __cplusplus > 201703L 280760c2415Smrg 281*0bfacb9bSmrg#define __cpp_lib_bitops 201907L 282760c2415Smrg 283*0bfacb9bSmrg /// @cond undoc 284760c2415Smrg template<typename _Tp, typename _Up = _Tp> 285760c2415Smrg using _If_is_unsigned_integer 286*0bfacb9bSmrg = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>; 287*0bfacb9bSmrg /// @endcond 288760c2415Smrg 289760c2415Smrg // [bit.rot], rotating 290760c2415Smrg 291*0bfacb9bSmrg /// Rotate `x` to the left by `s` bits. 292760c2415Smrg template<typename _Tp> 293760c2415Smrg [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp> 294760c2415Smrg rotl(_Tp __x, int __s) noexcept 295760c2415Smrg { return std::__rotl(__x, __s); } 296760c2415Smrg 297*0bfacb9bSmrg /// Rotate `x` to the right by `s` bits. 298760c2415Smrg template<typename _Tp> 299760c2415Smrg [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp> 300760c2415Smrg rotr(_Tp __x, int __s) noexcept 301760c2415Smrg { return std::__rotr(__x, __s); } 302760c2415Smrg 303760c2415Smrg // [bit.count], counting 304760c2415Smrg 305*0bfacb9bSmrg /// The number of contiguous zero bits, starting from the highest bit. 306760c2415Smrg template<typename _Tp> 307760c2415Smrg constexpr _If_is_unsigned_integer<_Tp, int> 308760c2415Smrg countl_zero(_Tp __x) noexcept 309760c2415Smrg { return std::__countl_zero(__x); } 310760c2415Smrg 311*0bfacb9bSmrg /// The number of contiguous one bits, starting from the highest bit. 312760c2415Smrg template<typename _Tp> 313760c2415Smrg constexpr _If_is_unsigned_integer<_Tp, int> 314760c2415Smrg countl_one(_Tp __x) noexcept 315760c2415Smrg { return std::__countl_one(__x); } 316760c2415Smrg 317*0bfacb9bSmrg /// The number of contiguous zero bits, starting from the lowest bit. 318760c2415Smrg template<typename _Tp> 319760c2415Smrg constexpr _If_is_unsigned_integer<_Tp, int> 320760c2415Smrg countr_zero(_Tp __x) noexcept 321760c2415Smrg { return std::__countr_zero(__x); } 322760c2415Smrg 323*0bfacb9bSmrg /// The number of contiguous one bits, starting from the lowest bit. 324760c2415Smrg template<typename _Tp> 325760c2415Smrg constexpr _If_is_unsigned_integer<_Tp, int> 326760c2415Smrg countr_one(_Tp __x) noexcept 327760c2415Smrg { return std::__countr_one(__x); } 328760c2415Smrg 329*0bfacb9bSmrg /// The number of bits set in `x`. 330760c2415Smrg template<typename _Tp> 331760c2415Smrg constexpr _If_is_unsigned_integer<_Tp, int> 332760c2415Smrg popcount(_Tp __x) noexcept 333760c2415Smrg { return std::__popcount(__x); } 334760c2415Smrg 335760c2415Smrg // [bit.pow.two], integral powers of 2 336760c2415Smrg 337*0bfacb9bSmrg#define __cpp_lib_int_pow2 202002L 338*0bfacb9bSmrg 339*0bfacb9bSmrg /// True if `x` is a power of two, false otherwise. 340760c2415Smrg template<typename _Tp> 341760c2415Smrg constexpr _If_is_unsigned_integer<_Tp, bool> 342*0bfacb9bSmrg has_single_bit(_Tp __x) noexcept 343*0bfacb9bSmrg { return std::__has_single_bit(__x); } 344760c2415Smrg 345*0bfacb9bSmrg /// The smallest power-of-two not less than `x`. 346760c2415Smrg template<typename _Tp> 347760c2415Smrg constexpr _If_is_unsigned_integer<_Tp> 348*0bfacb9bSmrg bit_ceil(_Tp __x) noexcept 349*0bfacb9bSmrg { return std::__bit_ceil(__x); } 350760c2415Smrg 351*0bfacb9bSmrg /// The largest power-of-two not greater than `x`. 352760c2415Smrg template<typename _Tp> 353760c2415Smrg constexpr _If_is_unsigned_integer<_Tp> 354*0bfacb9bSmrg bit_floor(_Tp __x) noexcept 355*0bfacb9bSmrg { return std::__bit_floor(__x); } 356760c2415Smrg 357*0bfacb9bSmrg /// The smallest integer greater than the base-2 logarithm of `x`. 358760c2415Smrg template<typename _Tp> 359760c2415Smrg constexpr _If_is_unsigned_integer<_Tp> 360*0bfacb9bSmrg bit_width(_Tp __x) noexcept 361*0bfacb9bSmrg { return std::__bit_width(__x); } 362760c2415Smrg 363760c2415Smrg#define __cpp_lib_endian 201907L 364760c2415Smrg 365760c2415Smrg /// Byte order 366760c2415Smrg enum class endian 367760c2415Smrg { 368760c2415Smrg little = __ORDER_LITTLE_ENDIAN__, 369760c2415Smrg big = __ORDER_BIG_ENDIAN__, 370760c2415Smrg native = __BYTE_ORDER__ 371760c2415Smrg }; 372760c2415Smrg#endif // C++2a 373760c2415Smrg 374*0bfacb9bSmrg /// @} 375*0bfacb9bSmrg 376760c2415Smrg_GLIBCXX_END_NAMESPACE_VERSION 377760c2415Smrg} // namespace std 378760c2415Smrg 379760c2415Smrg#endif // C++14 380760c2415Smrg#endif // _GLIBCXX_BIT 381