1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_BITSET
11#define _LIBCPP_BITSET
12
13// clang-format off
14
15/*
16 bitset synopsis
17
18namespace std
19{
20
21namespace std {
22
23template <size_t N>
24class bitset
25{
26public:
27 // bit reference:
28 class reference
29 {
30 friend class bitset;
31 reference() noexcept;
32 public:
33 ~reference() noexcept;
34 reference& operator=(bool x) noexcept; // for b[i] = x;
35 reference& operator=(const reference&) noexcept; // for b[i] = b[j];
36 bool operator~() const noexcept; // flips the bit
37 operator bool() const noexcept; // for x = b[i];
38 reference& flip() noexcept; // for b[i].flip();
39 };
40
41 // 23.3.5.1 constructors:
42 constexpr bitset() noexcept;
43 constexpr bitset(unsigned long long val) noexcept;
44 template <class charT>
45 constexpr explicit bitset(const charT* str,
46 typename basic_string<charT>::size_type n = basic_string<charT>::npos,
47 charT zero = charT('0'), charT one = charT('1')); // until C++26, constexpr since C++23
48 template <class charT>
49 constexpr explicit bitset(const charT* str,
50 typename basic_string_view<charT>::size_type n = basic_string_view<charT>::npos,
51 charT zero = charT('0'), charT one = charT('1')); // since C++26
52 template<class charT, class traits>
53 explicit bitset(
54 const basic_string_view<charT,traits>& str,
55 typename basic_string_view<charT,traits>::size_type pos = 0,
56 typename basic_string_view<charT,traits>::size_type n = basic_string_view<charT,traits>::npos,
57 charT zero = charT('0'), charT one = charT('1')); // since C++26
58 template<class charT, class traits, class Allocator>
59 constexpr explicit bitset(
60 const basic_string<charT,traits,Allocator>& str,
61 typename basic_string<charT,traits,Allocator>::size_type pos = 0,
62 typename basic_string<charT,traits,Allocator>::size_type n = basic_string<charT,traits,Allocator>::npos,
63 charT zero = charT('0'), charT one = charT('1')); // constexpr since C++23
64
65 // 23.3.5.2 bitset operations:
66 bitset& operator&=(const bitset& rhs) noexcept; // constexpr since C++23
67 bitset& operator|=(const bitset& rhs) noexcept; // constexpr since C++23
68 bitset& operator^=(const bitset& rhs) noexcept; // constexpr since C++23
69 bitset& operator<<=(size_t pos) noexcept; // constexpr since C++23
70 bitset& operator>>=(size_t pos) noexcept; // constexpr since C++23
71 bitset& set() noexcept; // constexpr since C++23
72 bitset& set(size_t pos, bool val = true); // constexpr since C++23
73 bitset& reset() noexcept; // constexpr since C++23
74 bitset& reset(size_t pos); // constexpr since C++23
75 bitset operator~() const noexcept; // constexpr since C++23
76 bitset& flip() noexcept; // constexpr since C++23
77 bitset& flip(size_t pos); // constexpr since C++23
78
79 // element access:
80 constexpr bool operator[](size_t pos) const;
81 reference operator[](size_t pos); // constexpr since C++23
82 unsigned long to_ulong() const; // constexpr since C++23
83 unsigned long long to_ullong() const; // constexpr since C++23
84 template <class charT, class traits, class Allocator> // constexpr since C++23
85 basic_string<charT, traits, Allocator> to_string(charT zero = charT('0'), charT one = charT('1')) const;
86 template <class charT, class traits> // constexpr since C++23
87 basic_string<charT, traits, allocator<charT> > to_string(charT zero = charT('0'), charT one = charT('1')) const;
88 template <class charT> // constexpr since C++23
89 basic_string<charT, char_traits<charT>, allocator<charT> > to_string(charT zero = charT('0'), charT one = charT('1')) const;
90 basic_string<char, char_traits<char>, allocator<char> > to_string(char zero = '0', char one = '1') const; // constexpr since C++23
91 size_t count() const noexcept; // constexpr since C++23
92 constexpr size_t size() const noexcept; // constexpr since C++23
93 bool operator==(const bitset& rhs) const noexcept; // constexpr since C++23
94 bool operator!=(const bitset& rhs) const noexcept; // removed in C++20
95 bool test(size_t pos) const; // constexpr since C++23
96 bool all() const noexcept; // constexpr since C++23
97 bool any() const noexcept; // constexpr since C++23
98 bool none() const noexcept; // constexpr since C++23
99 bitset<N> operator<<(size_t pos) const noexcept; // constexpr since C++23
100 bitset<N> operator>>(size_t pos) const noexcept; // constexpr since C++23
101};
102
103// 23.3.5.3 bitset operators:
104template <size_t N>
105bitset<N> operator&(const bitset<N>&, const bitset<N>&) noexcept; // constexpr since C++23
106
107template <size_t N>
108bitset<N> operator|(const bitset<N>&, const bitset<N>&) noexcept; // constexpr since C++23
109
110template <size_t N>
111bitset<N> operator^(const bitset<N>&, const bitset<N>&) noexcept; // constexpr since C++23
112
113template <class charT, class traits, size_t N>
114basic_istream<charT, traits>&
115operator>>(basic_istream<charT, traits>& is, bitset<N>& x);
116
117template <class charT, class traits, size_t N>
118basic_ostream<charT, traits>&
119operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x);
120
121template <size_t N> struct hash<std::bitset<N>>;
122
123} // std
124
125*/
126
127// clang-format on
128
129#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
130# include <__cxx03/bitset>
131#else
132# include <__algorithm/copy.h>
133# include <__algorithm/copy_backward.h>
134# include <__algorithm/count.h>
135# include <__algorithm/equal.h>
136# include <__algorithm/fill.h>
137# include <__algorithm/fill_n.h>
138# include <__algorithm/find.h>
139# include <__algorithm/min.h>
140# include <__assert>
141# include <__bit/countr.h>
142# include <__bit/invert_if.h>
143# include <__bit_reference>
144# include <__config>
145# include <__cstddef/ptrdiff_t.h>
146# include <__cstddef/size_t.h>
147# include <__functional/hash.h>
148# include <__functional/identity.h>
149# include <__functional/unary_function.h>
150# include <__tuple/tuple_indices.h>
151# include <__type_traits/enable_if.h>
152# include <__type_traits/integral_constant.h>
153# include <__type_traits/is_char_like_type.h>
154# include <__utility/integer_sequence.h>
155# include <climits>
156# include <stdexcept>
157# include <string_view>
158# include <version>
159
160// standard-mandated includes
161
162// [bitset.syn]
163# include <iosfwd>
164# include <string>
165
166# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
167# pragma GCC system_header
168# endif
169
170_LIBCPP_PUSH_MACROS
171# include <__undef_macros>
172
173_LIBCPP_BEGIN_NAMESPACE_STD
174
175template <size_t _N_words, size_t _Size>
176class __bitset;
177
178template <size_t _N_words, size_t _Size>
179struct __has_storage_type<__bitset<_N_words, _Size> > {
180 static const bool value = true;
181};
182
183template <size_t _N_words, size_t _Size>
184class __bitset {
185public:
186 typedef size_t __storage_type;
187
188protected:
189 typedef __bitset __self;
190 typedef __storage_type* __storage_pointer;
191 typedef const __storage_type* __const_storage_pointer;
192 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
193
194 friend class __bit_reference<__bitset>;
195 friend class __bit_const_reference<__bitset>;
196 friend class __bit_iterator<__bitset, false>;
197 friend class __bit_iterator<__bitset, true>;
198 friend struct __bit_array<__bitset>;
199
200 __storage_type __first_[_N_words];
201
202 typedef __bit_reference<__bitset> reference;
203 typedef __bit_const_reference<__bitset> __const_reference;
204 typedef __bit_iterator<__bitset, false> __iterator;
205 typedef __bit_iterator<__bitset, true> __const_iterator;
206
207 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT;
208 _LIBCPP_HIDE_FROM_ABI explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long __v) _NOEXCEPT;
209
210 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 reference __make_ref(size_t __pos) _NOEXCEPT {
211 return reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
212 }
213 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __const_reference __make_ref(size_t __pos) const _NOEXCEPT {
214 return __const_reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
215 }
216 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 __iterator __make_iter(size_t __pos) _NOEXCEPT {
217 return __iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);
218 }
219 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 __const_iterator __make_iter(size_t __pos) const _NOEXCEPT {
220 return __const_iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);
221 }
222
223 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void operator&=(const __bitset& __v) _NOEXCEPT;
224 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void operator|=(const __bitset& __v) _NOEXCEPT;
225 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void operator^=(const __bitset& __v) _NOEXCEPT;
226
227 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void flip() _NOEXCEPT;
228
229 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 unsigned long to_ulong() const {
230 if _LIBCPP_CONSTEXPR (_Size > sizeof(unsigned long) * CHAR_BIT) {
231 if (auto __e = __make_iter(_Size); std::find(__make_iter(sizeof(unsigned long) * CHAR_BIT), __e, true) != __e)
232 std::__throw_overflow_error(msg: "__bitset<_N_words, _Size>::to_ulong overflow error");
233 }
234
235 static_assert(sizeof(__storage_type) >= sizeof(unsigned long),
236 "libc++ only supports platforms where sizeof(size_t) >= sizeof(unsigned long), such as 32-bit and "
237 "64-bit platforms. If you're interested in supporting a platform where that is not the case, please "
238 "contact the libc++ developers.");
239 return static_cast<unsigned long>(__first_[0]);
240 }
241
242 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 unsigned long long to_ullong() const {
243 // Check for overflow if _Size does not fit in unsigned long long
244 if _LIBCPP_CONSTEXPR (_Size > sizeof(unsigned long long) * CHAR_BIT) {
245 if (auto __e = __make_iter(_Size);
246 std::find(__make_iter(sizeof(unsigned long long) * CHAR_BIT), __e, true) != __e)
247 std::__throw_overflow_error(msg: "__bitset<_N_words, _Size>::to_ullong overflow error");
248 }
249
250 // At this point, the effective bitset size (excluding leading zeros) fits in unsigned long long
251
252 if _LIBCPP_CONSTEXPR (sizeof(__storage_type) >= sizeof(unsigned long long)) {
253 // If __storage_type is at least as large as unsigned long long, the result spans only one word
254 return static_cast<unsigned long long>(__first_[0]);
255 } else {
256 // Otherwise, the result spans multiple words which are concatenated
257 const size_t __ull_words = (sizeof(unsigned long long) - 1) / sizeof(__storage_type) + 1;
258 const size_t __n_words = _N_words < __ull_words ? _N_words : __ull_words;
259 unsigned long long __r = static_cast<unsigned long long>(__first_[0]);
260 for (size_t __i = 1; __i < __n_words; ++__i)
261 __r |= static_cast<unsigned long long>(__first_[__i]) << (__bits_per_word * __i);
262 return __r;
263 }
264 }
265
266 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool all() const _NOEXCEPT { return !__scan_bits(__bit_not()); }
267 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool any() const _NOEXCEPT {
268 return __scan_bits(std::__identity());
269 }
270 _LIBCPP_HIDE_FROM_ABI size_t __hash_code() const _NOEXCEPT;
271
272 template <bool _Sparse, class _CharT, class _Traits, class _Allocator>
273 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<_CharT, _Traits, _Allocator>
274 __to_string(_CharT __zero, _CharT __one) const {
275 basic_string<_CharT, _Traits, _Allocator> __r(_Size, _Sparse ? __zero : __one);
276 for (size_t __i = 0, __bits = 0; __i < _N_words; ++__i, __bits += __bits_per_word) {
277 __storage_type __word = std::__invert_if<!_Sparse>(__first_[__i]);
278 if (__i == _N_words - 1 && _Size - __bits < __bits_per_word)
279 __word &= (__storage_type(1) << (_Size - __bits)) - 1;
280 for (; __word; __word &= (__word - 1))
281 __r[_Size - 1 - (__bits + std::__countr_zero(t: __word))] = _Sparse ? __one : __zero;
282 }
283
284 return __r;
285 }
286
287private:
288 struct __bit_not {
289 template <class _Tp>
290 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _Tp operator()(const _Tp& __x) const _NOEXCEPT {
291 return ~__x;
292 }
293 };
294
295 template <typename _Proj>
296 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool __scan_bits(_Proj __proj) const _NOEXCEPT {
297 size_t __n = _Size;
298 __const_storage_pointer __p = __first_;
299 // do middle whole words
300 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
301 if (__proj(*__p))
302 return true;
303 // do last partial word
304 if (__n > 0) {
305 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
306 if (__proj(*__p) & __m)
307 return true;
308 }
309 return false;
310 }
311
312# ifdef _LIBCPP_CXX03_LANG
313 void __init(unsigned long long __v, false_type) _NOEXCEPT;
314 _LIBCPP_HIDE_FROM_ABI void __init(unsigned long long __v, true_type) _NOEXCEPT;
315# else
316 template <size_t... _Indices>
317 _LIBCPP_HIDE_FROM_ABI constexpr __bitset(unsigned long long __v, std::__tuple_indices<_Indices...>) _NOEXCEPT
318 : __first_{static_cast<__storage_type>(__v >> (_Indices * __bits_per_word))...} {}
319# endif // _LIBCPP_CXX03_LANG
320};
321
322template <size_t _N_words, size_t _Size>
323inline _LIBCPP_CONSTEXPR __bitset<_N_words, _Size>::__bitset() _NOEXCEPT
324# ifndef _LIBCPP_CXX03_LANG
325 : __first_{0}
326# endif
327{
328# ifdef _LIBCPP_CXX03_LANG
329 std::fill_n(__first_, _N_words, __storage_type(0));
330# endif
331}
332
333# ifdef _LIBCPP_CXX03_LANG
334
335template <size_t _N_words, size_t _Size>
336void __bitset<_N_words, _Size>::__init(unsigned long long __v, false_type) _NOEXCEPT {
337 const size_t __n_words = std::min((sizeof(unsigned long long) - 1) / sizeof(__storage_type) + 1, _N_words);
338 for (size_t __i = 0; __i < __n_words; ++__i, __v >>= __bits_per_word)
339 __first_[__i] = static_cast<__storage_type>(__v);
340 std::fill(__first_ + __n_words, __first_ + _N_words, __storage_type(0));
341}
342
343template <size_t _N_words, size_t _Size>
344inline _LIBCPP_HIDE_FROM_ABI void __bitset<_N_words, _Size>::__init(unsigned long long __v, true_type) _NOEXCEPT {
345 __first_[0] = __v;
346 std::fill(__first_ + 1, __first_ + _N_words, __storage_type(0));
347}
348
349# endif // _LIBCPP_CXX03_LANG
350
351template <size_t _N_words, size_t _Size>
352inline _LIBCPP_CONSTEXPR __bitset<_N_words, _Size>::__bitset(unsigned long long __v) _NOEXCEPT
353# ifndef _LIBCPP_CXX03_LANG
354 : __bitset(__v,
355 std::__make_indices_imp< (_N_words < (sizeof(unsigned long long) - 1) / sizeof(__storage_type) + 1)
356 ? _N_words
357 : (sizeof(unsigned long long) - 1) / sizeof(__storage_type) + 1,
358 0>{})
359# endif
360{
361# ifdef _LIBCPP_CXX03_LANG
362 __init(__v, _BoolConstant<sizeof(unsigned long long) <= sizeof(__storage_type)>());
363# endif
364}
365
366template <size_t _N_words, size_t _Size>
367inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void
368__bitset<_N_words, _Size>::operator&=(const __bitset& __v) _NOEXCEPT {
369 for (size_t __i = 0; __i < _N_words; ++__i)
370 __first_[__i] &= __v.__first_[__i];
371}
372
373template <size_t _N_words, size_t _Size>
374inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void
375__bitset<_N_words, _Size>::operator|=(const __bitset& __v) _NOEXCEPT {
376 for (size_t __i = 0; __i < _N_words; ++__i)
377 __first_[__i] |= __v.__first_[__i];
378}
379
380template <size_t _N_words, size_t _Size>
381inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void
382__bitset<_N_words, _Size>::operator^=(const __bitset& __v) _NOEXCEPT {
383 for (size_t __i = 0; __i < _N_words; ++__i)
384 __first_[__i] ^= __v.__first_[__i];
385}
386
387template <size_t _N_words, size_t _Size>
388_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void __bitset<_N_words, _Size>::flip() _NOEXCEPT {
389 // do middle whole words
390 size_t __n = _Size;
391 __storage_pointer __p = __first_;
392 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
393 *__p = ~*__p;
394 // do last partial word
395 // Ensure trailing padding bits are zeroed as part of the ABI for consistent hashing behavior. std::hash<bitset>
396 // assumes trailing bits are zeroed; otherwise, identical bitsets could hash differently.
397 if (__n > 0)
398 *__p ^= (__storage_type(1) << __n) - 1;
399}
400
401template <size_t _N_words, size_t _Size>
402inline size_t __bitset<_N_words, _Size>::__hash_code() const _NOEXCEPT {
403 size_t __h = 0;
404 for (size_t __i = 0; __i < _N_words; ++__i)
405 __h ^= __first_[__i];
406 return __h;
407}
408
409template <size_t _Size>
410class __bitset<1, _Size> {
411public:
412 typedef size_t __storage_type;
413
414protected:
415 typedef __bitset __self;
416 typedef __storage_type* __storage_pointer;
417 typedef const __storage_type* __const_storage_pointer;
418 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
419
420 friend class __bit_reference<__bitset>;
421 friend class __bit_const_reference<__bitset>;
422 friend class __bit_iterator<__bitset, false>;
423 friend class __bit_iterator<__bitset, true>;
424 friend struct __bit_array<__bitset>;
425
426 __storage_type __first_;
427
428 typedef __bit_reference<__bitset> reference;
429 typedef __bit_const_reference<__bitset> __const_reference;
430 typedef __bit_iterator<__bitset, false> __iterator;
431 typedef __bit_iterator<__bitset, true> __const_iterator;
432
433 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT;
434 _LIBCPP_HIDE_FROM_ABI explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long __v) _NOEXCEPT;
435
436 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 reference __make_ref(size_t __pos) _NOEXCEPT {
437 return reference(&__first_, __storage_type(1) << __pos);
438 }
439 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __const_reference __make_ref(size_t __pos) const _NOEXCEPT {
440 return __const_reference(&__first_, __storage_type(1) << __pos);
441 }
442 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 __iterator __make_iter(size_t __pos) _NOEXCEPT {
443 // Allow the == case to accommodate the past-the-end iterator.
444 _LIBCPP_ASSERT_INTERNAL(__pos <= __bits_per_word, "Out of bounds access in the single-word bitset implementation.");
445 return __pos != __bits_per_word ? __iterator(&__first_, __pos) : __iterator(&__first_ + 1, 0);
446 }
447 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 __const_iterator __make_iter(size_t __pos) const _NOEXCEPT {
448 // Allow the == case to accommodate the past-the-end iterator.
449 _LIBCPP_ASSERT_INTERNAL(__pos <= __bits_per_word, "Out of bounds access in the single-word bitset implementation.");
450 return __pos != __bits_per_word ? __const_iterator(&__first_, __pos) : __const_iterator(&__first_ + 1, 0);
451 }
452
453 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void operator&=(const __bitset& __v) _NOEXCEPT;
454 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void operator|=(const __bitset& __v) _NOEXCEPT;
455 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void operator^=(const __bitset& __v) _NOEXCEPT;
456
457 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void flip() _NOEXCEPT;
458
459 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 unsigned long to_ulong() const {
460 if _LIBCPP_CONSTEXPR (_Size > sizeof(unsigned long) * CHAR_BIT) {
461 if (auto __e = __make_iter(_Size); std::find(__make_iter(sizeof(unsigned long) * CHAR_BIT), __e, true) != __e)
462 __throw_overflow_error(msg: "__bitset<1, _Size>::to_ulong overflow error");
463 }
464 return static_cast<unsigned long>(__first_);
465 }
466
467 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 unsigned long long to_ullong() const {
468 // If _Size exceeds the size of unsigned long long, check for overflow
469 if _LIBCPP_CONSTEXPR (_Size > sizeof(unsigned long long) * CHAR_BIT) {
470 if (auto __e = __make_iter(_Size);
471 std::find(__make_iter(sizeof(unsigned long long) * CHAR_BIT), __e, true) != __e)
472 __throw_overflow_error(msg: "__bitset<1, _Size>::to_ullong overflow error");
473 }
474
475 // If _Size fits or no overflow, directly cast to unsigned long long
476 return static_cast<unsigned long long>(__first_);
477 }
478
479 template <bool _Sparse, class _CharT, class _Traits, class _Allocator>
480 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<_CharT, _Traits, _Allocator>
481 __to_string(_CharT __zero, _CharT __one) const {
482 basic_string<_CharT, _Traits, _Allocator> __r(_Size, _Sparse ? __zero : __one);
483 __storage_type __word = std::__invert_if<!_Sparse>(__first_);
484 if (_Size < __bits_per_word)
485 __word &= (__storage_type(1) << _Size) - 1;
486 for (; __word; __word &= (__word - 1)) {
487 size_t __pos = std::__countr_zero(__word);
488 __r[_Size - 1 - __pos] = _Sparse ? __one : __zero;
489 }
490 return __r;
491 }
492
493 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool all() const _NOEXCEPT;
494 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool any() const _NOEXCEPT;
495
496 _LIBCPP_HIDE_FROM_ABI size_t __hash_code() const _NOEXCEPT;
497};
498
499template <size_t _Size>
500inline _LIBCPP_CONSTEXPR __bitset<1, _Size>::__bitset() _NOEXCEPT : __first_(0) {}
501
502template <size_t _Size>
503inline _LIBCPP_CONSTEXPR __bitset<1, _Size>::__bitset(unsigned long long __v) _NOEXCEPT
504 // TODO: We must refer to __bits_per_word in order to work around an issue with the GDB pretty-printers.
505 // Without it, the pretty-printers complain about a missing __bits_per_word member. This needs to
506 // be investigated further.
507 : __first_(_Size == __bits_per_word ? static_cast<__storage_type>(__v) : static_cast<__storage_type>(__v)) {}
508
509template <size_t _Size>
510inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void
511__bitset<1, _Size>::operator&=(const __bitset& __v) _NOEXCEPT {
512 __first_ &= __v.__first_;
513}
514
515template <size_t _Size>
516inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void
517__bitset<1, _Size>::operator|=(const __bitset& __v) _NOEXCEPT {
518 __first_ |= __v.__first_;
519}
520
521template <size_t _Size>
522inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void
523__bitset<1, _Size>::operator^=(const __bitset& __v) _NOEXCEPT {
524 __first_ ^= __v.__first_;
525}
526
527template <size_t _Size>
528inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void __bitset<1, _Size>::flip() _NOEXCEPT {
529 __first_ ^= ~__storage_type(0) >> (__bits_per_word - _Size);
530}
531
532template <size_t _Size>
533inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool __bitset<1, _Size>::all() const _NOEXCEPT {
534 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
535 return !(~__first_ & __m);
536}
537
538template <size_t _Size>
539inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool __bitset<1, _Size>::any() const _NOEXCEPT {
540 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
541 return __first_ & __m;
542}
543
544template <size_t _Size>
545inline size_t __bitset<1, _Size>::__hash_code() const _NOEXCEPT {
546 return __first_;
547}
548
549template <>
550class __bitset<0, 0> {
551public:
552 typedef size_t __storage_type;
553
554protected:
555 typedef __bitset __self;
556 typedef __storage_type* __storage_pointer;
557 typedef const __storage_type* __const_storage_pointer;
558 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
559
560 friend class __bit_reference<__bitset>;
561 friend class __bit_const_reference<__bitset>;
562 friend class __bit_iterator<__bitset, false>;
563 friend class __bit_iterator<__bitset, true>;
564 friend struct __bit_array<__bitset>;
565
566 typedef __bit_reference<__bitset> reference;
567 typedef __bit_const_reference<__bitset> __const_reference;
568 typedef __bit_iterator<__bitset, false> __iterator;
569 typedef __bit_iterator<__bitset, true> __const_iterator;
570
571 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT;
572 _LIBCPP_HIDE_FROM_ABI explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long) _NOEXCEPT;
573
574 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 reference __make_ref(size_t) _NOEXCEPT {
575 return reference(nullptr, 1);
576 }
577 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __const_reference __make_ref(size_t) const _NOEXCEPT {
578 return __const_reference(nullptr, 1);
579 }
580 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 __iterator __make_iter(size_t) _NOEXCEPT {
581 return __iterator(nullptr, 0);
582 }
583 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 __const_iterator __make_iter(size_t) const _NOEXCEPT {
584 return __const_iterator(nullptr, 0);
585 }
586
587 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void operator&=(const __bitset&) _NOEXCEPT {}
588 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void operator|=(const __bitset&) _NOEXCEPT {}
589 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void operator^=(const __bitset&) _NOEXCEPT {}
590
591 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void flip() _NOEXCEPT {}
592
593 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 unsigned long to_ulong() const { return 0; }
594 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 unsigned long long to_ullong() const { return 0; }
595
596 template <bool _Sparse, class _CharT, class _Traits, class _Allocator>
597 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<_CharT, _Traits, _Allocator>
598 __to_string(_CharT, _CharT) const {
599 return basic_string<_CharT, _Traits, _Allocator>();
600 }
601
602 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool all() const _NOEXCEPT { return true; }
603 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool any() const _NOEXCEPT { return false; }
604
605 _LIBCPP_HIDE_FROM_ABI size_t __hash_code() const _NOEXCEPT { return 0; }
606};
607
608inline _LIBCPP_CONSTEXPR __bitset<0, 0>::__bitset() _NOEXCEPT {}
609
610inline _LIBCPP_CONSTEXPR __bitset<0, 0>::__bitset(unsigned long long) _NOEXCEPT {}
611
612template <size_t _Size>
613class bitset;
614template <size_t _Size>
615struct hash<bitset<_Size> >;
616
617template <size_t _Size>
618class bitset : private __bitset<_Size == 0 ? 0 : (_Size - 1) / (sizeof(size_t) * CHAR_BIT) + 1, _Size> {
619public:
620 static const unsigned __n_words = _Size == 0 ? 0 : (_Size - 1) / (sizeof(size_t) * CHAR_BIT) + 1;
621 typedef __bitset<__n_words, _Size> __base;
622 typedef typename __base::reference reference;
623 typedef typename __base::__const_reference __const_reference;
624
625 // 23.3.5.1 constructors:
626 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bitset() _NOEXCEPT {}
627 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bitset(unsigned long long __v) _NOEXCEPT
628 : __base(sizeof(unsigned long long) * CHAR_BIT <= _Size ? __v : __v & ((1ULL << _Size) - 1)) {}
629 template <class _CharT, __enable_if_t<_IsCharLikeType<_CharT>::value, int> = 0>
630 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 explicit bitset(
631 const _CharT* __str,
632 size_t __n = basic_string<_CharT>::npos,
633 _CharT __zero = _CharT('0'),
634 _CharT __one = _CharT('1')) {
635 if (__n == basic_string<_CharT>::npos)
636 __init_from_string_view(basic_string_view<_CharT>(__str), __zero, __one);
637 else
638 __init_from_string_view(basic_string_view<_CharT>(__str, __n), __zero, __one);
639 }
640# if _LIBCPP_STD_VER >= 26
641 template <class _CharT, class _Traits>
642 _LIBCPP_HIDE_FROM_ABI constexpr explicit bitset(
643 basic_string_view<_CharT, _Traits> __str,
644 typename basic_string_view<_CharT, _Traits>::size_type __pos = 0,
645 typename basic_string_view<_CharT, _Traits>::size_type __n = basic_string_view<_CharT, _Traits>::npos,
646 _CharT __zero = _CharT('0'),
647 _CharT __one = _CharT('1')) {
648 if (__pos > __str.size())
649 std::__throw_out_of_range("bitset string pos out of range");
650
651 size_t __rlen = std::min(__n, __str.size() - __pos);
652 __init_from_string_view(basic_string_view<_CharT, _Traits>(__str.data() + __pos, __rlen), __zero, __one);
653 }
654# endif
655 template <class _CharT, class _Traits, class _Allocator>
656 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 explicit bitset(
657 const basic_string<_CharT, _Traits, _Allocator>& __str,
658 typename basic_string<_CharT, _Traits, _Allocator>::size_type __pos = 0,
659 typename basic_string<_CharT, _Traits, _Allocator>::size_type __n =
660 basic_string<_CharT, _Traits, _Allocator>::npos,
661 _CharT __zero = _CharT('0'),
662 _CharT __one = _CharT('1')) {
663 if (__pos > __str.size())
664 std::__throw_out_of_range(msg: "bitset string pos out of range");
665
666 size_t __rlen = std::min(__n, __str.size() - __pos);
667 __init_from_string_view(basic_string_view<_CharT, _Traits>(__str.data() + __pos, __rlen), __zero, __one);
668 }
669
670 // 23.3.5.2 bitset operations:
671 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& operator&=(const bitset& __rhs) _NOEXCEPT;
672 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& operator|=(const bitset& __rhs) _NOEXCEPT;
673 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& operator^=(const bitset& __rhs) _NOEXCEPT;
674 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& operator<<=(size_t __pos) _NOEXCEPT;
675 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& operator>>=(size_t __pos) _NOEXCEPT;
676 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& set() _NOEXCEPT;
677 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& set(size_t __pos, bool __val = true);
678 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& reset() _NOEXCEPT;
679 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& reset(size_t __pos);
680 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset operator~() const _NOEXCEPT;
681 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& flip() _NOEXCEPT;
682 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset& flip(size_t __pos);
683
684 // element access:
685# ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
686 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool operator[](size_t __p) const {
687 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__p < _Size, "bitset::operator[] index out of bounds");
688 return __base::__make_ref(__p);
689 }
690# else
691 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __const_reference operator[](size_t __p) const {
692 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__p < _Size, "bitset::operator[] index out of bounds");
693 return __base::__make_ref(__p);
694 }
695# endif
696 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 reference operator[](size_t __p) {
697 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__p < _Size, "bitset::operator[] index out of bounds");
698 return __base::__make_ref(__p);
699 }
700 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 unsigned long to_ulong() const { return __base::to_ulong(); }
701 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 unsigned long long to_ullong() const {
702 return __base::to_ullong();
703 }
704 template <class _CharT, class _Traits, class _Allocator>
705 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<_CharT, _Traits, _Allocator>
706 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const;
707 template <class _CharT, class _Traits>
708 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<_CharT, _Traits, allocator<_CharT> >
709 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const;
710 template <class _CharT>
711 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<_CharT, char_traits<_CharT>, allocator<_CharT> >
712 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const;
713 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<char, char_traits<char>, allocator<char> >
714 to_string(char __zero = '0', char __one = '1') const;
715 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 size_t count() const _NOEXCEPT;
716 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR size_t size() const _NOEXCEPT { return _Size; }
717 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool operator==(const bitset& __rhs) const _NOEXCEPT;
718# if _LIBCPP_STD_VER <= 17
719 _LIBCPP_HIDE_FROM_ABI bool operator!=(const bitset& __rhs) const _NOEXCEPT;
720# endif
721 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool test(size_t __pos) const;
722 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool all() const _NOEXCEPT { return __base::all(); }
723 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool any() const _NOEXCEPT { return __base::any(); }
724 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool none() const _NOEXCEPT { return !any(); }
725 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset operator<<(size_t __pos) const _NOEXCEPT;
726 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset operator>>(size_t __pos) const _NOEXCEPT;
727
728private:
729 template <class _CharT, class _Traits>
730 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 void
731 __init_from_string_view(basic_string_view<_CharT, _Traits> __str, _CharT __zero, _CharT __one) {
732 for (size_t __i = 0; __i < __str.size(); ++__i)
733 if (!_Traits::eq(__str[__i], __zero) && !_Traits::eq(__str[__i], __one))
734 std::__throw_invalid_argument(msg: "bitset string ctor has invalid argument");
735
736 size_t __mp = std::min(__str.size(), _Size);
737 size_t __i = 0;
738 for (; __i < __mp; ++__i) {
739 _CharT __c = __str[__mp - 1 - __i];
740 (*this)[__i] = _Traits::eq(__c, __one);
741 }
742 }
743
744 _LIBCPP_HIDE_FROM_ABI size_t __hash_code() const _NOEXCEPT { return __base::__hash_code(); }
745
746 friend struct hash<bitset>;
747};
748
749template <size_t _Size>
750inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>&
751bitset<_Size>::operator&=(const bitset& __rhs) _NOEXCEPT {
752 __base::operator&=(__rhs);
753 return *this;
754}
755
756template <size_t _Size>
757inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>&
758bitset<_Size>::operator|=(const bitset& __rhs) _NOEXCEPT {
759 __base::operator|=(__rhs);
760 return *this;
761}
762
763template <size_t _Size>
764inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>&
765bitset<_Size>::operator^=(const bitset& __rhs) _NOEXCEPT {
766 __base::operator^=(__rhs);
767 return *this;
768}
769
770template <size_t _Size>
771_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>& bitset<_Size>::operator<<=(size_t __pos) _NOEXCEPT {
772 __pos = std::min(a: __pos, b: _Size);
773 std::copy_backward(__base::__make_iter(0), __base::__make_iter(_Size - __pos), __base::__make_iter(_Size));
774 std::fill_n(__base::__make_iter(0), __pos, false);
775 return *this;
776}
777
778template <size_t _Size>
779_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>& bitset<_Size>::operator>>=(size_t __pos) _NOEXCEPT {
780 __pos = std::min(a: __pos, b: _Size);
781 std::copy(__base::__make_iter(__pos), __base::__make_iter(_Size), __base::__make_iter(0));
782 std::fill_n(__base::__make_iter(_Size - __pos), __pos, false);
783 return *this;
784}
785
786template <size_t _Size>
787inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>& bitset<_Size>::set() _NOEXCEPT {
788 std::fill_n(__base::__make_iter(0), _Size, true);
789 return *this;
790}
791
792template <size_t _Size>
793_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>& bitset<_Size>::set(size_t __pos, bool __val) {
794 if (__pos >= _Size)
795 std::__throw_out_of_range(msg: "bitset set argument out of range");
796
797 (*this)[__pos] = __val;
798 return *this;
799}
800
801template <size_t _Size>
802inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>& bitset<_Size>::reset() _NOEXCEPT {
803 std::fill_n(__base::__make_iter(0), _Size, false);
804 return *this;
805}
806
807template <size_t _Size>
808_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>& bitset<_Size>::reset(size_t __pos) {
809 if (__pos >= _Size)
810 std::__throw_out_of_range(msg: "bitset reset argument out of range");
811
812 (*this)[__pos] = false;
813 return *this;
814}
815
816template <size_t _Size>
817inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size> bitset<_Size>::operator~() const _NOEXCEPT {
818 bitset __x(*this);
819 __x.flip();
820 return __x;
821}
822
823template <size_t _Size>
824inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>& bitset<_Size>::flip() _NOEXCEPT {
825 __base::flip();
826 return *this;
827}
828
829template <size_t _Size>
830_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>& bitset<_Size>::flip(size_t __pos) {
831 if (__pos >= _Size)
832 std::__throw_out_of_range(msg: "bitset flip argument out of range");
833
834 reference __r = __base::__make_ref(__pos);
835 __r = ~__r;
836 return *this;
837}
838
839template <size_t _Size>
840template <class _CharT, class _Traits, class _Allocator>
841_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<_CharT, _Traits, _Allocator>
842bitset<_Size>::to_string(_CharT __zero, _CharT __one) const {
843 bool __sparse = size_t(std::count(__base::__make_iter(0), __base::__make_iter(_Size), true)) < _Size / 2;
844 if (__sparse)
845 return __base::template __to_string<true, _CharT, _Traits, _Allocator>(__zero, __one);
846 else
847 return __base::template __to_string<false, _CharT, _Traits, _Allocator>(__zero, __one);
848}
849
850template <size_t _Size>
851template <class _CharT, class _Traits>
852inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<_CharT, _Traits, allocator<_CharT> >
853bitset<_Size>::to_string(_CharT __zero, _CharT __one) const {
854 return to_string<_CharT, _Traits, allocator<_CharT> >(__zero, __one);
855}
856
857template <size_t _Size>
858template <class _CharT>
859inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<_CharT, char_traits<_CharT>, allocator<_CharT> >
860bitset<_Size>::to_string(_CharT __zero, _CharT __one) const {
861 return to_string<_CharT, char_traits<_CharT>, allocator<_CharT> >(__zero, __one);
862}
863
864template <size_t _Size>
865inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 basic_string<char, char_traits<char>, allocator<char> >
866bitset<_Size>::to_string(char __zero, char __one) const {
867 return to_string<char, char_traits<char>, allocator<char> >(__zero, __one);
868}
869
870template <size_t _Size>
871inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 size_t bitset<_Size>::count() const _NOEXCEPT {
872 return static_cast<size_t>(std::count(__base::__make_iter(0), __base::__make_iter(_Size), true));
873}
874
875template <size_t _Size>
876inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool
877bitset<_Size>::operator==(const bitset& __rhs) const _NOEXCEPT {
878 return std::equal(__base::__make_iter(0), __base::__make_iter(_Size), __rhs.__make_iter(0));
879}
880
881# if _LIBCPP_STD_VER <= 17
882
883template <size_t _Size>
884inline _LIBCPP_HIDE_FROM_ABI bool bitset<_Size>::operator!=(const bitset& __rhs) const _NOEXCEPT {
885 return !(*this == __rhs);
886}
887
888# endif
889
890template <size_t _Size>
891_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bool bitset<_Size>::test(size_t __pos) const {
892 if (__pos >= _Size)
893 std::__throw_out_of_range(msg: "bitset test argument out of range");
894
895 return (*this)[__pos];
896}
897
898template <size_t _Size>
899inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>
900bitset<_Size>::operator<<(size_t __pos) const _NOEXCEPT {
901 bitset __r = *this;
902 __r <<= __pos;
903 return __r;
904}
905
906template <size_t _Size>
907inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>
908bitset<_Size>::operator>>(size_t __pos) const _NOEXCEPT {
909 bitset __r = *this;
910 __r >>= __pos;
911 return __r;
912}
913
914template <size_t _Size>
915inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>
916operator&(const bitset<_Size>& __x, const bitset<_Size>& __y) _NOEXCEPT {
917 bitset<_Size> __r = __x;
918 __r &= __y;
919 return __r;
920}
921
922template <size_t _Size>
923inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>
924operator|(const bitset<_Size>& __x, const bitset<_Size>& __y) _NOEXCEPT {
925 bitset<_Size> __r = __x;
926 __r |= __y;
927 return __r;
928}
929
930template <size_t _Size>
931inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX23 bitset<_Size>
932operator^(const bitset<_Size>& __x, const bitset<_Size>& __y) _NOEXCEPT {
933 bitset<_Size> __r = __x;
934 __r ^= __y;
935 return __r;
936}
937
938template <size_t _Size>
939struct hash<bitset<_Size> > : public __unary_function<bitset<_Size>, size_t> {
940 _LIBCPP_HIDE_FROM_ABI size_t operator()(const bitset<_Size>& __bs) const _NOEXCEPT { return __bs.__hash_code(); }
941};
942
943template <class _CharT, class _Traits, size_t _Size>
944_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
945operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Size>& __x);
946
947template <class _CharT, class _Traits, size_t _Size>
948_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
949operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Size>& __x);
950
951_LIBCPP_END_NAMESPACE_STD
952
953_LIBCPP_POP_MACROS
954
955# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
956# include <concepts>
957# include <cstdlib>
958# include <optional>
959# include <type_traits>
960# endif
961#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
962
963#endif // _LIBCPP_BITSET
964