1// <bit> -*- C++ -*- 2 3// Copyright (C) 2018-2021 Free Software Foundation, Inc. 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> 37 38#if _GLIBCXX_HOSTED 39# include <ext/numeric_traits.h> 40#else 41# include <limits> 42/// @cond undocumented 43namespace __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 54 55namespace std _GLIBCXX_VISIBILITY(default) 56{ 57_GLIBCXX_BEGIN_NAMESPACE_VERSION 58 59 /** 60 * @defgroup bit_manip Bit manipulation 61 * @ingroup numerics 62 * 63 * Utilities for examining and manipulating individual bits. 64 * 65 * @{ 66 */ 67 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`. 72 template<typename _To, typename _From> 73 [[nodiscard]] 74 constexpr _To 75 bit_cast(const _From& __from) noexcept 76 { 77 return __builtin_bit_cast(_To, __from); 78 } 79#endif 80 81 /// @cond undoc 82 83 template<typename _Tp> 84 constexpr _Tp 85 __rotl(_Tp __x, int __s) noexcept 86 { 87 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 88 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0) 89 { 90 // Variant for power of two _Nd which the compiler can 91 // easily pattern match. 92 constexpr unsigned __uNd = _Nd; 93 const unsigned __r = __s; 94 return (__x << (__r % __uNd)) | (__x >> ((-__r) % __uNd)); 95 } 96 const int __r = __s % _Nd; 97 if (__r == 0) 98 return __x; 99 else if (__r > 0) 100 return (__x << __r) | (__x >> ((_Nd - __r) % _Nd)); 101 else 102 return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r) 103 } 104 105 template<typename _Tp> 106 constexpr _Tp 107 __rotr(_Tp __x, int __s) noexcept 108 { 109 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 110 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0) 111 { 112 // Variant for power of two _Nd which the compiler can 113 // easily pattern match. 114 constexpr unsigned __uNd = _Nd; 115 const unsigned __r = __s; 116 return (__x >> (__r % __uNd)) | (__x << ((-__r) % __uNd)); 117 } 118 const int __r = __s % _Nd; 119 if (__r == 0) 120 return __x; 121 else if (__r > 0) 122 return (__x >> __r) | (__x << ((_Nd - __r) % _Nd)); 123 else 124 return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r) 125 } 126 127 template<typename _Tp> 128 constexpr int 129 __countl_zero(_Tp __x) noexcept 130 { 131 using __gnu_cxx::__int_traits; 132 constexpr auto _Nd = __int_traits<_Tp>::__digits; 133 134 if (__x == 0) 135 return _Nd; 136 137 constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits; 138 constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits; 139 constexpr auto _Nd_u = __int_traits<unsigned>::__digits; 140 141 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) 142 { 143 constexpr int __diff = _Nd_u - _Nd; 144 return __builtin_clz(__x) - __diff; 145 } 146 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) 147 { 148 constexpr int __diff = _Nd_ul - _Nd; 149 return __builtin_clzl(__x) - __diff; 150 } 151 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) 152 { 153 constexpr int __diff = _Nd_ull - _Nd; 154 return __builtin_clzll(__x) - __diff; 155 } 156 else // (_Nd > _Nd_ull) 157 { 158 static_assert(_Nd <= (2 * _Nd_ull), 159 "Maximum supported integer size is 128-bit"); 160 161 unsigned long long __high = __x >> _Nd_ull; 162 if (__high != 0) 163 { 164 constexpr int __diff = (2 * _Nd_ull) - _Nd; 165 return __builtin_clzll(__high) - __diff; 166 } 167 constexpr auto __max_ull = __int_traits<unsigned long long>::__max; 168 unsigned long long __low = __x & __max_ull; 169 return (_Nd - _Nd_ull) + __builtin_clzll(__low); 170 } 171 } 172 173 template<typename _Tp> 174 constexpr int 175 __countl_one(_Tp __x) noexcept 176 { 177 return std::__countl_zero<_Tp>((_Tp)~__x); 178 } 179 180 template<typename _Tp> 181 constexpr int 182 __countr_zero(_Tp __x) noexcept 183 { 184 using __gnu_cxx::__int_traits; 185 constexpr auto _Nd = __int_traits<_Tp>::__digits; 186 187 if (__x == 0) 188 return _Nd; 189 190 constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits; 191 constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits; 192 constexpr auto _Nd_u = __int_traits<unsigned>::__digits; 193 194 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) 195 return __builtin_ctz(__x); 196 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) 197 return __builtin_ctzl(__x); 198 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) 199 return __builtin_ctzll(__x); 200 else // (_Nd > _Nd_ull) 201 { 202 static_assert(_Nd <= (2 * _Nd_ull), 203 "Maximum supported integer size is 128-bit"); 204 205 constexpr auto __max_ull = __int_traits<unsigned long long>::__max; 206 unsigned long long __low = __x & __max_ull; 207 if (__low != 0) 208 return __builtin_ctzll(__low); 209 unsigned long long __high = __x >> _Nd_ull; 210 return __builtin_ctzll(__high) + _Nd_ull; 211 } 212 } 213 214 template<typename _Tp> 215 constexpr int 216 __countr_one(_Tp __x) noexcept 217 { 218 return std::__countr_zero((_Tp)~__x); 219 } 220 221 template<typename _Tp> 222 constexpr int 223 __popcount(_Tp __x) noexcept 224 { 225 using __gnu_cxx::__int_traits; 226 constexpr auto _Nd = __int_traits<_Tp>::__digits; 227 228 constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits; 229 constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits; 230 constexpr auto _Nd_u = __int_traits<unsigned>::__digits; 231 232 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) 233 return __builtin_popcount(__x); 234 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) 235 return __builtin_popcountl(__x); 236 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) 237 return __builtin_popcountll(__x); 238 else // (_Nd > _Nd_ull) 239 { 240 static_assert(_Nd <= (2 * _Nd_ull), 241 "Maximum supported integer size is 128-bit"); 242 243 constexpr auto __max_ull = __int_traits<unsigned long long>::__max; 244 unsigned long long __low = __x & __max_ull; 245 unsigned long long __high = __x >> _Nd_ull; 246 return __builtin_popcountll(__low) + __builtin_popcountll(__high); 247 } 248 } 249 250 template<typename _Tp> 251 constexpr bool 252 __has_single_bit(_Tp __x) noexcept 253 { return std::__popcount(__x) == 1; } 254 255 template<typename _Tp> 256 constexpr _Tp 257 __bit_ceil(_Tp __x) noexcept 258 { 259 using __gnu_cxx::__int_traits; 260 constexpr auto _Nd = __int_traits<_Tp>::__digits; 261 if (__x == 0 || __x == 1) 262 return 1; 263 auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u)); 264 // If the shift exponent equals _Nd then the correct result is not 265 // representable as a value of _Tp, and so the result is undefined. 266 // Want that undefined behaviour to be detected in constant expressions, 267 // by UBSan, and by debug assertions. 268#ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED 269 if (!__builtin_is_constant_evaluated()) 270 { 271 __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits ); 272 } 273#endif 274 using __promoted_type = decltype(__x << 1); 275 if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value) 276 { 277 // If __x undergoes integral promotion then shifting by _Nd is 278 // not undefined. In order to make the shift undefined, so that 279 // it is diagnosed in constant expressions and by UBsan, we also 280 // need to "promote" the shift exponent to be too large for the 281 // promoted type. 282 const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2; 283 __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp; 284 } 285 return (_Tp)1u << __shift_exponent; 286 } 287 288 template<typename _Tp> 289 constexpr _Tp 290 __bit_floor(_Tp __x) noexcept 291 { 292 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 293 if (__x == 0) 294 return 0; 295 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1))); 296 } 297 298 template<typename _Tp> 299 constexpr _Tp 300 __bit_width(_Tp __x) noexcept 301 { 302 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 303 return _Nd - std::__countl_zero(__x); 304 } 305 306 /// @endcond 307 308#if __cplusplus > 201703L 309 310#define __cpp_lib_bitops 201907L 311 312 /// @cond undoc 313 template<typename _Tp, typename _Up = _Tp> 314 using _If_is_unsigned_integer 315 = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>; 316 /// @endcond 317 318 // [bit.rot], rotating 319 320 /// Rotate `x` to the left by `s` bits. 321 template<typename _Tp> 322 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp> 323 rotl(_Tp __x, int __s) noexcept 324 { return std::__rotl(__x, __s); } 325 326 /// Rotate `x` to the right by `s` bits. 327 template<typename _Tp> 328 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp> 329 rotr(_Tp __x, int __s) noexcept 330 { return std::__rotr(__x, __s); } 331 332 // [bit.count], counting 333 334 /// The number of contiguous zero bits, starting from the highest bit. 335 template<typename _Tp> 336 constexpr _If_is_unsigned_integer<_Tp, int> 337 countl_zero(_Tp __x) noexcept 338 { return std::__countl_zero(__x); } 339 340 /// The number of contiguous one bits, starting from the highest bit. 341 template<typename _Tp> 342 constexpr _If_is_unsigned_integer<_Tp, int> 343 countl_one(_Tp __x) noexcept 344 { return std::__countl_one(__x); } 345 346 /// The number of contiguous zero bits, starting from the lowest bit. 347 template<typename _Tp> 348 constexpr _If_is_unsigned_integer<_Tp, int> 349 countr_zero(_Tp __x) noexcept 350 { return std::__countr_zero(__x); } 351 352 /// The number of contiguous one bits, starting from the lowest bit. 353 template<typename _Tp> 354 constexpr _If_is_unsigned_integer<_Tp, int> 355 countr_one(_Tp __x) noexcept 356 { return std::__countr_one(__x); } 357 358 /// The number of bits set in `x`. 359 template<typename _Tp> 360 constexpr _If_is_unsigned_integer<_Tp, int> 361 popcount(_Tp __x) noexcept 362 { return std::__popcount(__x); } 363 364 // [bit.pow.two], integral powers of 2 365 366#define __cpp_lib_int_pow2 202002L 367 368 /// True if `x` is a power of two, false otherwise. 369 template<typename _Tp> 370 constexpr _If_is_unsigned_integer<_Tp, bool> 371 has_single_bit(_Tp __x) noexcept 372 { return std::__has_single_bit(__x); } 373 374 /// The smallest power-of-two not less than `x`. 375 template<typename _Tp> 376 constexpr _If_is_unsigned_integer<_Tp> 377 bit_ceil(_Tp __x) noexcept 378 { return std::__bit_ceil(__x); } 379 380 /// The largest power-of-two not greater than `x`. 381 template<typename _Tp> 382 constexpr _If_is_unsigned_integer<_Tp> 383 bit_floor(_Tp __x) noexcept 384 { return std::__bit_floor(__x); } 385 386 /// The smallest integer greater than the base-2 logarithm of `x`. 387 template<typename _Tp> 388 constexpr _If_is_unsigned_integer<_Tp> 389 bit_width(_Tp __x) noexcept 390 { return std::__bit_width(__x); } 391 392#define __cpp_lib_endian 201907L 393 394 /// Byte order 395 enum class endian 396 { 397 little = __ORDER_LITTLE_ENDIAN__, 398 big = __ORDER_BIG_ENDIAN__, 399 native = __BYTE_ORDER__ 400 }; 401#endif // C++2a 402 403 /// @} 404 405_GLIBCXX_END_NAMESPACE_VERSION 406} // namespace std 407 408#endif // C++14 409#endif // _GLIBCXX_BIT 410