1 // <bitset> -*- C++ -*-
3 // Copyright (C) 2001-2024 Free Software Foundation, Inc.
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)
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.
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.
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/>.
27 * Silicon Graphics Computer Systems, Inc.
29 * Permission to use, copy, modify, distribute and sell this software
30 * and its documentation for any purpose is hereby granted without fee,
31 * provided that the above copyright notice appear in all copies and
32 * that both that copyright notice and this permission notice appear
33 * in supporting documentation. Silicon Graphics makes no
34 * representations about the suitability of this software for any
35 * purpose. It is provided "as is" without express or implied warranty.
38 /** @file include/bitset
39 * This is a Standard C++ Library header.
42 #ifndef _GLIBCXX_BITSET
43 #define _GLIBCXX_BITSET 1
45 #pragma GCC system_header
47 #include <bits/functexcept.h> // For invalid_argument, out_of_range,
49 #include <bits/stl_algobase.h> // For std::fill
54 # include <bits/cxxabi_forced.h>
57 #if __cplusplus >= 201103L
58 # include <bits/functional_hash.h>
61 #define __glibcxx_want_constexpr_bitset
62 #include <bits/version.h>
64 #define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * __SIZEOF_LONG__)
65 #define _GLIBCXX_BITSET_WORDS(__n) \
66 ((__n) / _GLIBCXX_BITSET_BITS_PER_WORD + \
67 ((__n) % _GLIBCXX_BITSET_BITS_PER_WORD == 0 ? 0 : 1))
69 #define _GLIBCXX_BITSET_BITS_PER_ULL (__CHAR_BIT__ * __SIZEOF_LONG_LONG__)
71 namespace std _GLIBCXX_VISIBILITY(default)
73 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
76 * Base class, general case. It is a class invariant that _Nw will be
79 * See documentation for bitset.
84 typedef unsigned long _WordT;
86 /// 0 is the least significant word.
89 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
92 #if __cplusplus >= 201103L
93 constexpr _Base_bitset(unsigned long long __val) noexcept
95 #if __SIZEOF_LONG_LONG__ > __SIZEOF_LONG__
96 , _WordT(__val >> _GLIBCXX_BITSET_BITS_PER_WORD)
100 _Base_bitset(unsigned long __val)
105 static _GLIBCXX_CONSTEXPR size_t
106 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
107 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
109 static _GLIBCXX_CONSTEXPR size_t
110 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
111 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
113 static _GLIBCXX_CONSTEXPR size_t
114 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
115 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
117 static _GLIBCXX_CONSTEXPR _WordT
118 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
119 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
121 _GLIBCXX14_CONSTEXPR _WordT&
122 _M_getword(size_t __pos) _GLIBCXX_NOEXCEPT
123 { return _M_w[_S_whichword(__pos)]; }
125 _GLIBCXX_CONSTEXPR _WordT
126 _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT
127 { return _M_w[_S_whichword(__pos)]; }
129 #if __cplusplus >= 201103L
130 constexpr const _WordT*
131 _M_getdata() const noexcept
135 _GLIBCXX23_CONSTEXPR _WordT&
136 _M_hiword() _GLIBCXX_NOEXCEPT
137 { return _M_w[_Nw - 1]; }
139 _GLIBCXX_CONSTEXPR _WordT
140 _M_hiword() const _GLIBCXX_NOEXCEPT
141 { return _M_w[_Nw - 1]; }
143 _GLIBCXX23_CONSTEXPR void
144 _M_do_and(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
146 for (size_t __i = 0; __i < _Nw; __i++)
147 _M_w[__i] &= __x._M_w[__i];
150 _GLIBCXX14_CONSTEXPR void
151 _M_do_or(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
153 for (size_t __i = 0; __i < _Nw; __i++)
154 _M_w[__i] |= __x._M_w[__i];
157 _GLIBCXX14_CONSTEXPR void
158 _M_do_xor(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
160 for (size_t __i = 0; __i < _Nw; __i++)
161 _M_w[__i] ^= __x._M_w[__i];
164 _GLIBCXX14_CONSTEXPR void
165 _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT;
167 _GLIBCXX14_CONSTEXPR void
168 _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT;
170 _GLIBCXX14_CONSTEXPR void
171 _M_do_flip() _GLIBCXX_NOEXCEPT
173 for (size_t __i = 0; __i < _Nw; __i++)
174 _M_w[__i] = ~_M_w[__i];
177 _GLIBCXX14_CONSTEXPR void
178 _M_do_set() _GLIBCXX_NOEXCEPT
180 #if __cplusplus >= 201402L
181 if (__builtin_is_constant_evaluated())
183 for (_WordT& __w : _M_w)
184 __w = ~static_cast<_WordT>(0);;
188 __builtin_memset(_M_w, 0xFF, _Nw * sizeof(_WordT));
191 _GLIBCXX14_CONSTEXPR void
192 _M_do_reset() _GLIBCXX_NOEXCEPT
194 #if __cplusplus >= 201402L
195 if (__builtin_is_constant_evaluated())
197 for (_WordT& __w : _M_w)
202 __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT));
205 _GLIBCXX14_CONSTEXPR bool
206 _M_is_equal(const _Base_bitset<_Nw>& __x) const _GLIBCXX_NOEXCEPT
208 #if __cplusplus >= 201402L
209 if (__builtin_is_constant_evaluated())
211 for (size_t __i = 0; __i < _Nw; ++__i)
212 if (_M_w[__i] != __x._M_w[__i])
217 return !__builtin_memcmp(_M_w, __x._M_w, _Nw * sizeof(_WordT));
221 _GLIBCXX14_CONSTEXPR bool
222 _M_are_all() const _GLIBCXX_NOEXCEPT
224 for (size_t __i = 0; __i < _Nw - 1; __i++)
225 if (_M_w[__i] != ~static_cast<_WordT>(0))
227 return _M_hiword() == (~static_cast<_WordT>(0)
228 >> (_Nw * _GLIBCXX_BITSET_BITS_PER_WORD
232 _GLIBCXX14_CONSTEXPR bool
233 _M_is_any() const _GLIBCXX_NOEXCEPT
235 for (size_t __i = 0; __i < _Nw; __i++)
236 if (_M_w[__i] != static_cast<_WordT>(0))
241 _GLIBCXX14_CONSTEXPR size_t
242 _M_do_count() const _GLIBCXX_NOEXCEPT
245 for (size_t __i = 0; __i < _Nw; __i++)
246 __result += __builtin_popcountl(_M_w[__i]);
250 _GLIBCXX14_CONSTEXPR unsigned long
251 _M_do_to_ulong() const;
253 #if __cplusplus >= 201103L
254 _GLIBCXX14_CONSTEXPR unsigned long long
255 _M_do_to_ullong() const;
258 // find first "on" bit
259 _GLIBCXX14_CONSTEXPR size_t
260 _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT;
262 // find the next "on" bit that follows "prev"
263 _GLIBCXX14_CONSTEXPR size_t
264 _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT;
267 // Definitions of non-inline functions from _Base_bitset.
269 _GLIBCXX14_CONSTEXPR void
270 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT
272 if (__builtin_expect(__shift != 0, 1))
274 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
275 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
278 for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
279 _M_w[__n] = _M_w[__n - __wshift];
282 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
284 for (size_t __n = _Nw - 1; __n > __wshift; --__n)
285 _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
286 | (_M_w[__n - __wshift - 1] >> __sub_offset));
287 _M_w[__wshift] = _M_w[0] << __offset;
290 std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
295 _GLIBCXX14_CONSTEXPR void
296 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT
298 if (__builtin_expect(__shift != 0, 1))
300 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
301 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
302 const size_t __limit = _Nw - __wshift - 1;
305 for (size_t __n = 0; __n <= __limit; ++__n)
306 _M_w[__n] = _M_w[__n + __wshift];
309 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
311 for (size_t __n = 0; __n < __limit; ++__n)
312 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
313 | (_M_w[__n + __wshift + 1] << __sub_offset));
314 _M_w[__limit] = _M_w[_Nw-1] >> __offset;
317 std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
322 _GLIBCXX14_CONSTEXPR unsigned long
323 _Base_bitset<_Nw>::_M_do_to_ulong() const
325 for (size_t __i = 1; __i < _Nw; ++__i)
327 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong"));
331 #if __cplusplus >= 201103L
333 _GLIBCXX14_CONSTEXPR unsigned long long
334 _Base_bitset<_Nw>::_M_do_to_ullong() const
336 #if __SIZEOF_LONG_LONG__ == __SIZEOF_LONG__
337 return _M_do_to_ulong();
339 for (size_t __i = 2; __i < _Nw; ++__i)
341 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong"));
343 return _M_w[0] + (static_cast<unsigned long long>(_M_w[1])
344 << _GLIBCXX_BITSET_BITS_PER_WORD);
350 _GLIBCXX14_CONSTEXPR size_t
352 _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT
354 for (size_t __i = 0; __i < _Nw; __i++)
356 _WordT __thisword = _M_w[__i];
357 if (__thisword != static_cast<_WordT>(0))
358 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
359 + __builtin_ctzl(__thisword));
361 // not found, so return an indication of failure.
366 _GLIBCXX14_CONSTEXPR size_t
368 _M_do_find_next(size_t __prev, size_t __not_found) const _GLIBCXX_NOEXCEPT
370 // make bound inclusive
373 // check out of bounds
374 if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
378 size_t __i = _S_whichword(__prev);
379 _WordT __thisword = _M_w[__i];
381 // mask off bits below bound
382 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
384 if (__thisword != static_cast<_WordT>(0))
385 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
386 + __builtin_ctzl(__thisword));
388 // check subsequent words
390 for (; __i < _Nw; __i++)
392 __thisword = _M_w[__i];
393 if (__thisword != static_cast<_WordT>(0))
394 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
395 + __builtin_ctzl(__thisword));
397 // not found, so return an indication of failure.
399 } // end _M_do_find_next
402 * Base class, specialization for a single word.
404 * See documentation for bitset.
407 struct _Base_bitset<1>
409 typedef unsigned long _WordT;
412 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
416 #if __cplusplus >= 201103L
417 constexpr _Base_bitset(unsigned long long __val) noexcept
419 _Base_bitset(unsigned long __val)
424 static _GLIBCXX_CONSTEXPR size_t
425 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
426 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
428 static _GLIBCXX_CONSTEXPR size_t
429 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
430 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
432 static _GLIBCXX_CONSTEXPR size_t
433 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
434 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
436 static _GLIBCXX_CONSTEXPR _WordT
437 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
438 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
440 _GLIBCXX14_CONSTEXPR _WordT&
441 _M_getword(size_t) _GLIBCXX_NOEXCEPT
444 _GLIBCXX_CONSTEXPR _WordT
445 _M_getword(size_t) const _GLIBCXX_NOEXCEPT
448 #if __cplusplus >= 201103L
449 constexpr const _WordT*
450 _M_getdata() const noexcept
454 _GLIBCXX14_CONSTEXPR _WordT&
455 _M_hiword() _GLIBCXX_NOEXCEPT
458 _GLIBCXX_CONSTEXPR _WordT
459 _M_hiword() const _GLIBCXX_NOEXCEPT
462 _GLIBCXX14_CONSTEXPR void
463 _M_do_and(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT
464 { _M_w &= __x._M_w; }
466 _GLIBCXX14_CONSTEXPR void
467 _M_do_or(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT
468 { _M_w |= __x._M_w; }
470 _GLIBCXX14_CONSTEXPR void
471 _M_do_xor(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT
472 { _M_w ^= __x._M_w; }
474 _GLIBCXX14_CONSTEXPR void
475 _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT
476 { _M_w <<= __shift; }
478 _GLIBCXX14_CONSTEXPR void
479 _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT
480 { _M_w >>= __shift; }
482 _GLIBCXX14_CONSTEXPR void
483 _M_do_flip() _GLIBCXX_NOEXCEPT
486 _GLIBCXX14_CONSTEXPR void
487 _M_do_set() _GLIBCXX_NOEXCEPT
488 { _M_w = ~static_cast<_WordT>(0); }
490 _GLIBCXX14_CONSTEXPR void
491 _M_do_reset() _GLIBCXX_NOEXCEPT
494 _GLIBCXX14_CONSTEXPR bool
495 _M_is_equal(const _Base_bitset<1>& __x) const _GLIBCXX_NOEXCEPT
496 { return _M_w == __x._M_w; }
499 _GLIBCXX14_CONSTEXPR bool
500 _M_are_all() const _GLIBCXX_NOEXCEPT
501 { return _M_w == (~static_cast<_WordT>(0)
502 >> (_GLIBCXX_BITSET_BITS_PER_WORD - _Nb)); }
504 _GLIBCXX14_CONSTEXPR bool
505 _M_is_any() const _GLIBCXX_NOEXCEPT
506 { return _M_w != 0; }
508 _GLIBCXX14_CONSTEXPR size_t
509 _M_do_count() const _GLIBCXX_NOEXCEPT
510 { return __builtin_popcountl(_M_w); }
512 _GLIBCXX14_CONSTEXPR unsigned long
513 _M_do_to_ulong() const _GLIBCXX_NOEXCEPT
516 #if __cplusplus >= 201103L
517 constexpr unsigned long long
518 _M_do_to_ullong() const noexcept
522 _GLIBCXX14_CONSTEXPR size_t
523 _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT
526 return __builtin_ctzl(_M_w);
531 // find the next "on" bit that follows "prev"
532 _GLIBCXX14_CONSTEXPR size_t
533 _M_do_find_next(size_t __prev, size_t __not_found) const
537 if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
540 _WordT __x = _M_w >> __prev;
542 return __builtin_ctzl(__x) + __prev;
549 * Base class, specialization for no storage (zero-length %bitset).
551 * See documentation for bitset.
554 struct _Base_bitset<0>
556 typedef unsigned long _WordT;
558 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
561 #if __cplusplus >= 201103L
562 constexpr _Base_bitset(unsigned long long) noexcept
564 _Base_bitset(unsigned long)
568 static _GLIBCXX_CONSTEXPR size_t
569 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
570 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
572 static _GLIBCXX_CONSTEXPR size_t
573 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
574 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
576 static _GLIBCXX_CONSTEXPR size_t
577 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
578 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
580 static _GLIBCXX_CONSTEXPR _WordT
581 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
582 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
584 // This would normally give access to the data. The bounds-checking
585 // in the bitset class will prevent the user from getting this far,
586 // but this must fail if the user calls _Unchecked_set directly.
587 // Let's not penalize zero-length users unless they actually
588 // make an unchecked call; all the memory ugliness is therefore
589 // localized to this single should-never-get-this-far function.
590 __attribute__((__noreturn__))
592 _M_getword(size_t) _GLIBCXX_NOEXCEPT
593 { __throw_out_of_range(__N("_Base_bitset::_M_getword")); }
595 _GLIBCXX_CONSTEXPR _WordT
596 _M_getword(size_t) const _GLIBCXX_NOEXCEPT
599 _GLIBCXX_CONSTEXPR _WordT
600 _M_hiword() const _GLIBCXX_NOEXCEPT
603 _GLIBCXX14_CONSTEXPR void
604 _M_do_and(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT
607 _GLIBCXX14_CONSTEXPR void
608 _M_do_or(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT
611 _GLIBCXX14_CONSTEXPR void
612 _M_do_xor(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT
615 _GLIBCXX14_CONSTEXPR void
616 _M_do_left_shift(size_t) _GLIBCXX_NOEXCEPT
619 _GLIBCXX14_CONSTEXPR void
620 _M_do_right_shift(size_t) _GLIBCXX_NOEXCEPT
623 _GLIBCXX14_CONSTEXPR void
624 _M_do_flip() _GLIBCXX_NOEXCEPT
627 _GLIBCXX14_CONSTEXPR void
628 _M_do_set() _GLIBCXX_NOEXCEPT
631 _GLIBCXX14_CONSTEXPR void
632 _M_do_reset() _GLIBCXX_NOEXCEPT
635 // Are all empty bitsets equal to each other? Are they equal to
636 // themselves? How to compare a thing which has no state? What is
637 // the sound of one zero-length bitset clapping?
638 _GLIBCXX_CONSTEXPR bool
639 _M_is_equal(const _Base_bitset<0>&) const _GLIBCXX_NOEXCEPT
643 _GLIBCXX_CONSTEXPR bool
644 _M_are_all() const _GLIBCXX_NOEXCEPT
647 _GLIBCXX_CONSTEXPR bool
648 _M_is_any() const _GLIBCXX_NOEXCEPT
651 _GLIBCXX_CONSTEXPR size_t
652 _M_do_count() const _GLIBCXX_NOEXCEPT
655 _GLIBCXX_CONSTEXPR unsigned long
656 _M_do_to_ulong() const _GLIBCXX_NOEXCEPT
659 #if __cplusplus >= 201103L
660 constexpr unsigned long long
661 _M_do_to_ullong() const noexcept
665 // Normally "not found" is the size, but that could also be
666 // misinterpreted as an index in this corner case. Oh well.
667 _GLIBCXX_CONSTEXPR size_t
668 _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT
671 _GLIBCXX_CONSTEXPR size_t
672 _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT
677 // Helper class to zero out the unused high-order bits in the highest word.
678 template<size_t _Extrabits>
681 typedef unsigned long _WordT;
683 static _GLIBCXX14_CONSTEXPR void
684 _S_do_sanitize(_WordT& __val) _GLIBCXX_NOEXCEPT
685 { __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); }
691 typedef unsigned long _WordT;
693 static _GLIBCXX14_CONSTEXPR void
694 _S_do_sanitize(_WordT) _GLIBCXX_NOEXCEPT { }
697 #if __cplusplus >= 201103L
698 template<size_t _Nb, bool = (_Nb < _GLIBCXX_BITSET_BITS_PER_ULL)>
701 static constexpr unsigned long long
702 _S_do_sanitize_val(unsigned long long __val)
707 struct _Sanitize_val<_Nb, true>
709 static constexpr unsigned long long
710 _S_do_sanitize_val(unsigned long long __val)
711 { return __val & ~((~static_cast<unsigned long long>(0)) << _Nb); }
717 template<typename _CharT>
718 using __string = std::basic_string<_CharT>;
720 template<typename _CharT>
723 using size_type = size_t;
724 static constexpr size_type npos = size_type(-1);
728 static _GLIBCXX14_CONSTEXPR size_t
729 length(const _CharT* __s) noexcept
737 static constexpr bool
738 eq(_CharT __l, _CharT __r) noexcept
739 { return __l == __r; }
743 } // namespace __bitset
747 * @brief The %bitset class represents a @e fixed-size sequence of bits.
750 * (Note that %bitset does @e not meet the formal requirements of a
751 * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.)
753 * The template argument, @a Nb, may be any non-negative number,
754 * specifying the number of bits (e.g., "0", "12", "1024*1024").
756 * In the general unoptimized case, storage is allocated in word-sized
757 * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B
758 * words will be used for storage. B - Nb%B bits are unused. (They are
759 * the high-order bits in the highest word.) It is a class invariant
760 * that those unused bits are always zero.
762 * If you think of %bitset as <em>a simple array of bits</em>, be
763 * aware that your mental picture is reversed: a %bitset behaves
764 * the same way as bits in integers do, with the bit at index 0 in
765 * the <em>least significant / right-hand</em> position, and the bit at
766 * index Nb-1 in the <em>most significant / left-hand</em> position.
767 * Thus, unlike other containers, a %bitset's index <em>counts from
768 * right to left</em>, to put it very loosely.
770 * This behavior is preserved when translating to and from strings. For
771 * example, the first line of the following program probably prints
772 * <em>b('a') is 0001100001</em> on a modern ASCII system.
776 * #include <iostream>
779 * using namespace std;
786 * cout << "b('a') is " << b << endl;
790 * string str = s.str();
791 * cout << "index 3 in the string is " << str[3] << " but\n"
792 * << "index 3 in the bitset is " << b[3] << endl;
797 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_containers.html
798 * for a description of extensions.
800 * Most of the actual code isn't contained in %bitset<> itself, but in the
801 * base class _Base_bitset. The base class works with whole words, not with
802 * individual bits. This allows us to specialize _Base_bitset for the
803 * important special case where the %bitset is only a single word.
805 * Extra confusion can result due to the fact that the storage for
806 * _Base_bitset @e is a regular array, and is indexed as such. This is
807 * carefully encapsulated.
811 : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
814 typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
815 typedef unsigned long _WordT;
818 template<class _CharT, class _Traits, class _Alloc>
821 _M_check_initial_position(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
822 size_t __position) const
824 if (__position > __s.size())
825 __throw_out_of_range_fmt(__N("bitset::bitset: __position "
826 "(which is %zu) > __s.size() "
828 __position, __s.size());
833 void _M_check(size_t __position, const char *__s) const
835 if (__position >= _Nb)
836 __throw_out_of_range_fmt(__N("%s: __position (which is %zu) "
837 ">= _Nb (which is %zu)"),
838 __s, __position, _Nb);
843 _M_do_sanitize() _GLIBCXX_NOEXCEPT
845 typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type;
846 __sanitize_type::_S_do_sanitize(this->_M_hiword());
849 #if __cplusplus >= 201103L
850 friend struct std::hash<bitset>;
855 * This encapsulates the concept of a single bit. An instance of this
856 * class is a proxy for an actual bit; this way the individual bit
857 * operations are done as faster word-size bitwise instructions.
859 * Most users will never need to use this class directly; conversions
860 * to and from bool are automatic and should be transparent. Overloaded
861 * operators help to preserve the illusion.
863 * (On a typical system, this <em>bit %reference</em> is 64
864 * times the size of an actual bit. Ha.)
874 reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT
876 _M_wp = &__b._M_getword(__pos);
877 _M_bpos = _Base::_S_whichbit(__pos);
881 #if __cplusplus >= 201103L
882 reference(const reference&) = default;
885 #if __cplusplus > 202002L && __cpp_constexpr_dynamic_alloc
888 ~reference() _GLIBCXX_NOEXCEPT
894 operator=(bool __x) _GLIBCXX_NOEXCEPT
897 *_M_wp |= _Base::_S_maskbit(_M_bpos);
899 *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
903 // For b[i] = b[__j];
906 operator=(const reference& __j) _GLIBCXX_NOEXCEPT
908 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
909 *_M_wp |= _Base::_S_maskbit(_M_bpos);
911 *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
918 operator~() const _GLIBCXX_NOEXCEPT
919 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
923 operator bool() const _GLIBCXX_NOEXCEPT
924 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
929 flip() _GLIBCXX_NOEXCEPT
931 *_M_wp ^= _Base::_S_maskbit(_M_bpos);
935 friend class reference;
937 // 23.3.5.1 constructors:
938 /// All bits set to zero.
939 _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT
942 /// Initial bits bitwise-copied from a single word (others set to zero).
943 #if __cplusplus >= 201103L
944 constexpr bitset(unsigned long long __val) noexcept
945 : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { }
947 bitset(unsigned long __val)
949 { _M_do_sanitize(); }
954 * Use a subset of a string.
955 * @param __s A string of @a 0 and @a 1 characters.
956 * @param __position Index of the first character in @a __s to use;
958 * @throw std::out_of_range If @a pos is bigger the size of @a __s.
959 * @throw std::invalid_argument If a character appears in the string
960 * which is neither @a 0 nor @a 1.
962 template<class _CharT, class _Traits, class _Alloc>
965 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
966 size_t __position = 0)
969 _M_check_initial_position(__s, __position);
970 _M_copy_from_string(__s, __position,
971 std::basic_string<_CharT, _Traits, _Alloc>::npos,
972 _CharT('0'), _CharT('1'));
976 * Use a subset of a string.
977 * @param __s A string of @a 0 and @a 1 characters.
978 * @param __position Index of the first character in @a __s to use.
979 * @param __n The number of characters to copy.
980 * @throw std::out_of_range If @a __position is bigger the size
982 * @throw std::invalid_argument If a character appears in the string
983 * which is neither @a 0 nor @a 1.
985 template<class _CharT, class _Traits, class _Alloc>
987 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
988 size_t __position, size_t __n)
991 _M_check_initial_position(__s, __position);
992 _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1'));
995 // _GLIBCXX_RESOLVE_LIB_DEFECTS
996 // 396. what are characters zero and one.
997 template<class _CharT, class _Traits, class _Alloc>
999 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
1000 size_t __position, size_t __n,
1001 _CharT __zero, _CharT __one = _CharT('1'))
1004 _M_check_initial_position(__s, __position);
1005 _M_copy_from_string(__s, __position, __n, __zero, __one);
1009 #if __cplusplus >= 201103L
1011 * Construct from a character %array.
1012 * @param __str An %array of characters @a zero and @a one.
1013 * @param __n The number of characters to use.
1014 * @param __zero The character corresponding to the value 0.
1015 * @param __one The character corresponding to the value 1.
1016 * @throw std::invalid_argument If a character appears in the string
1017 * which is neither @a __zero nor @a __one.
1019 template<typename _CharT>
1020 [[__gnu__::__nonnull__]]
1021 _GLIBCXX23_CONSTEXPR
1023 bitset(const _CharT* __str,
1024 typename __bitset::__string<_CharT>::size_type __n
1025 = __bitset::__string<_CharT>::npos,
1026 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'))
1031 __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)"));
1033 using _Traits = typename __bitset::__string<_CharT>::traits_type;
1035 if (__n == __bitset::__string<_CharT>::npos)
1036 __n = _Traits::length(__str);
1037 _M_copy_from_ptr<_CharT, _Traits>(__str, __n, 0, __n, __zero, __one);
1041 // 23.3.5.2 bitset operations:
1044 * Operations on bitsets.
1045 * @param __rhs A same-sized bitset.
1047 * These should be self-explanatory.
1049 _GLIBCXX23_CONSTEXPR
1051 operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
1053 this->_M_do_and(__rhs);
1057 _GLIBCXX23_CONSTEXPR
1059 operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
1061 this->_M_do_or(__rhs);
1065 _GLIBCXX23_CONSTEXPR
1067 operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
1069 this->_M_do_xor(__rhs);
1076 * Operations on bitsets.
1077 * @param __position The number of places to shift.
1079 * These should be self-explanatory.
1081 _GLIBCXX23_CONSTEXPR
1083 operator<<=(size_t __position) _GLIBCXX_NOEXCEPT
1085 if (__builtin_expect(__position < _Nb, 1))
1087 this->_M_do_left_shift(__position);
1088 this->_M_do_sanitize();
1091 this->_M_do_reset();
1095 _GLIBCXX23_CONSTEXPR
1097 operator>>=(size_t __position) _GLIBCXX_NOEXCEPT
1099 if (__builtin_expect(__position < _Nb, 1))
1100 this->_M_do_right_shift(__position);
1102 this->_M_do_reset();
1109 * These versions of single-bit set, reset, flip, and test are
1110 * extensions from the SGI version. They do no range checking.
1111 * @ingroup SGIextensions
1113 _GLIBCXX23_CONSTEXPR
1115 _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT
1117 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
1121 _GLIBCXX23_CONSTEXPR
1123 _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT
1126 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
1128 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
1132 _GLIBCXX23_CONSTEXPR
1134 _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT
1136 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
1140 _GLIBCXX23_CONSTEXPR
1142 _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT
1144 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
1148 _GLIBCXX_CONSTEXPR bool
1149 _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT
1150 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
1151 != static_cast<_WordT>(0)); }
1154 // Set, reset, and flip.
1156 * @brief Sets every bit to true.
1158 _GLIBCXX23_CONSTEXPR
1160 set() _GLIBCXX_NOEXCEPT
1163 this->_M_do_sanitize();
1168 * @brief Sets a given bit to a particular value.
1169 * @param __position The index of the bit.
1170 * @param __val Either true or false, defaults to true.
1171 * @throw std::out_of_range If @a pos is bigger the size of the %set.
1173 _GLIBCXX23_CONSTEXPR
1175 set(size_t __position, bool __val = true)
1177 this->_M_check(__position, __N("bitset::set"));
1178 return _Unchecked_set(__position, __val);
1182 * @brief Sets every bit to false.
1184 _GLIBCXX23_CONSTEXPR
1186 reset() _GLIBCXX_NOEXCEPT
1188 this->_M_do_reset();
1193 * @brief Sets a given bit to false.
1194 * @param __position The index of the bit.
1195 * @throw std::out_of_range If @a pos is bigger the size of the %set.
1197 * Same as writing @c set(pos,false).
1199 _GLIBCXX23_CONSTEXPR
1201 reset(size_t __position)
1203 this->_M_check(__position, __N("bitset::reset"));
1204 return _Unchecked_reset(__position);
1208 * @brief Toggles every bit to its opposite value.
1210 _GLIBCXX23_CONSTEXPR
1212 flip() _GLIBCXX_NOEXCEPT
1215 this->_M_do_sanitize();
1220 * @brief Toggles a given bit to its opposite value.
1221 * @param __position The index of the bit.
1222 * @throw std::out_of_range If @a pos is bigger the size of the %set.
1224 _GLIBCXX23_CONSTEXPR
1226 flip(size_t __position)
1228 this->_M_check(__position, __N("bitset::flip"));
1229 return _Unchecked_flip(__position);
1232 /// See the no-argument flip().
1233 _GLIBCXX23_CONSTEXPR
1235 operator~() const _GLIBCXX_NOEXCEPT
1236 { return bitset<_Nb>(*this).flip(); }
1240 * @brief Array-indexing support.
1241 * @param __position Index into the %bitset.
1242 * @return A bool for a <em>const %bitset</em>. For non-const
1243 * bitsets, an instance of the reference proxy class.
1244 * @note These operators do no range checking and throw no exceptions,
1245 * as required by DR 11 to the standard.
1247 * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
1248 * resolves DR 11 (items 1 and 2), but does not do the range-checking
1249 * required by that DR's resolution. -pme
1250 * The DR has since been changed: range-checking is a precondition
1251 * (users' responsibility), and these functions must not throw. -pme
1253 _GLIBCXX23_CONSTEXPR
1255 operator[](size_t __position)
1256 { return reference(*this, __position); }
1258 _GLIBCXX_CONSTEXPR bool
1259 operator[](size_t __position) const
1260 { return _Unchecked_test(__position); }
1264 * @brief Returns a numerical interpretation of the %bitset.
1265 * @return The integral equivalent of the bits.
1266 * @throw std::overflow_error If there are too many bits to be
1267 * represented in an @c unsigned @c long.
1269 _GLIBCXX23_CONSTEXPR
1272 { return this->_M_do_to_ulong(); }
1274 #if __cplusplus >= 201103L
1275 _GLIBCXX23_CONSTEXPR
1278 { return this->_M_do_to_ullong(); }
1283 * @brief Returns a character interpretation of the %bitset.
1284 * @return The string equivalent of the bits.
1286 * Note the ordering of the bits: decreasing character positions
1287 * correspond to increasing bit positions (see the main class notes for
1290 template<class _CharT, class _Traits, class _Alloc>
1291 _GLIBCXX23_CONSTEXPR
1292 std::basic_string<_CharT, _Traits, _Alloc>
1295 std::basic_string<_CharT, _Traits, _Alloc> __result;
1296 _M_copy_to_string(__result, _CharT('0'), _CharT('1'));
1300 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1301 // 396. what are characters zero and one.
1302 template<class _CharT, class _Traits, class _Alloc>
1303 _GLIBCXX23_CONSTEXPR
1304 std::basic_string<_CharT, _Traits, _Alloc>
1305 to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1307 std::basic_string<_CharT, _Traits, _Alloc> __result;
1308 _M_copy_to_string(__result, __zero, __one);
1312 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1313 // 434. bitset::to_string() hard to use.
1314 template<class _CharT, class _Traits>
1315 _GLIBCXX23_CONSTEXPR
1316 std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1318 { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
1320 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1321 // 853. to_string needs updating with zero and one.
1322 template<class _CharT, class _Traits>
1323 _GLIBCXX23_CONSTEXPR
1324 std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1325 to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1326 { return to_string<_CharT, _Traits,
1327 std::allocator<_CharT> >(__zero, __one); }
1329 template<class _CharT>
1330 _GLIBCXX23_CONSTEXPR
1331 std::basic_string<_CharT, std::char_traits<_CharT>,
1332 std::allocator<_CharT> >
1335 return to_string<_CharT, std::char_traits<_CharT>,
1336 std::allocator<_CharT> >();
1339 template<class _CharT>
1340 _GLIBCXX23_CONSTEXPR
1341 std::basic_string<_CharT, std::char_traits<_CharT>,
1342 std::allocator<_CharT> >
1343 to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1345 return to_string<_CharT, std::char_traits<_CharT>,
1346 std::allocator<_CharT> >(__zero, __one);
1349 _GLIBCXX23_CONSTEXPR
1350 std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1353 return to_string<char, std::char_traits<char>,
1354 std::allocator<char> >();
1357 _GLIBCXX23_CONSTEXPR
1358 std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1359 to_string(char __zero, char __one = '1') const
1361 return to_string<char, std::char_traits<char>,
1362 std::allocator<char> >(__zero, __one);
1366 /// Returns the number of bits which are set.
1367 _GLIBCXX23_CONSTEXPR
1369 count() const _GLIBCXX_NOEXCEPT
1370 { return this->_M_do_count(); }
1372 /// Returns the total number of bits.
1373 _GLIBCXX_CONSTEXPR size_t
1374 size() const _GLIBCXX_NOEXCEPT
1378 /// These comparisons for equality/inequality are, well, @e bitwise.
1379 _GLIBCXX23_CONSTEXPR
1381 operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
1382 { return this->_M_is_equal(__rhs); }
1384 #if __cpp_impl_three_way_comparison < 201907L
1385 _GLIBCXX23_CONSTEXPR
1387 operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
1388 { return !this->_M_is_equal(__rhs); }
1393 * @brief Tests the value of a bit.
1394 * @param __position The index of a bit.
1395 * @return The value at @a pos.
1396 * @throw std::out_of_range If @a pos is bigger the size of the %set.
1398 _GLIBCXX23_CONSTEXPR
1400 test(size_t __position) const
1402 this->_M_check(__position, __N("bitset::test"));
1403 return _Unchecked_test(__position);
1406 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1407 // DR 693. std::bitset::all() missing.
1409 * @brief Tests whether all the bits are on.
1410 * @return True if all the bits are set.
1412 _GLIBCXX23_CONSTEXPR
1414 all() const _GLIBCXX_NOEXCEPT
1415 { return this->template _M_are_all<_Nb>(); }
1418 * @brief Tests whether any of the bits are on.
1419 * @return True if at least one bit is set.
1421 _GLIBCXX23_CONSTEXPR
1423 any() const _GLIBCXX_NOEXCEPT
1424 { return this->_M_is_any(); }
1427 * @brief Tests whether any of the bits are on.
1428 * @return True if none of the bits are set.
1430 _GLIBCXX23_CONSTEXPR
1432 none() const _GLIBCXX_NOEXCEPT
1433 { return !this->_M_is_any(); }
1436 /// Self-explanatory.
1437 _GLIBCXX23_CONSTEXPR
1439 operator<<(size_t __position) const _GLIBCXX_NOEXCEPT
1440 { return bitset<_Nb>(*this) <<= __position; }
1442 _GLIBCXX23_CONSTEXPR
1444 operator>>(size_t __position) const _GLIBCXX_NOEXCEPT
1445 { return bitset<_Nb>(*this) >>= __position; }
1449 * @brief Finds the index of the first "on" bit.
1450 * @return The index of the first bit set, or size() if not found.
1451 * @ingroup SGIextensions
1454 _GLIBCXX23_CONSTEXPR
1456 _Find_first() const _GLIBCXX_NOEXCEPT
1457 { return this->_M_do_find_first(_Nb); }
1460 * @brief Finds the index of the next "on" bit after prev.
1461 * @return The index of the next bit set, or size() if not found.
1462 * @param __prev Where to start searching.
1463 * @ingroup SGIextensions
1466 _GLIBCXX23_CONSTEXPR
1468 _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT
1469 { return this->_M_do_find_next(__prev, _Nb); }
1472 // Helper functions for string operations.
1473 template<class _CharT, class _Traits>
1474 _GLIBCXX23_CONSTEXPR
1476 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
1480 template<class _CharT, class _Traits, class _Alloc>
1481 _GLIBCXX23_CONSTEXPR
1483 _M_copy_from_string(const std::basic_string<_CharT,
1484 _Traits, _Alloc>& __s, size_t __pos, size_t __n,
1485 _CharT __zero, _CharT __one)
1486 { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n,
1489 template<class _CharT, class _Traits, class _Alloc>
1490 _GLIBCXX23_CONSTEXPR
1492 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&,
1493 _CharT, _CharT) const;
1495 template<class _CharT, class _Traits, size_t _Nb2>
1496 friend std::basic_istream<_CharT, _Traits>&
1497 operator>>(std::basic_istream<_CharT, _Traits>&, bitset<_Nb2>&);
1499 template <class _CharT, class _Traits, size_t _Nb2>
1500 friend std::basic_ostream<_CharT, _Traits>&
1501 operator<<(std::basic_ostream<_CharT, _Traits>&, const bitset<_Nb2>&);
1505 // Definitions of non-inline member functions.
1506 template<size_t _Nb>
1507 template<class _CharT, class _Traits>
1508 _GLIBCXX23_CONSTEXPR
1511 _M_copy_from_ptr(const _CharT* __s, size_t __len,
1512 size_t __pos, size_t __n, _CharT __zero, _CharT __one)
1515 const size_t __nbits = std::min(_Nb, std::min(__n, size_t(__len - __pos)));
1516 for (size_t __i = __nbits; __i > 0; --__i)
1518 const _CharT __c = __s[__pos + __nbits - __i];
1519 if (_Traits::eq(__c, __zero))
1521 else if (_Traits::eq(__c, __one))
1522 _Unchecked_set(__i - 1);
1524 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
1529 template<size_t _Nb>
1530 template<class _CharT, class _Traits, class _Alloc>
1531 _GLIBCXX23_CONSTEXPR
1534 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s,
1535 _CharT __zero, _CharT __one) const
1537 __s.assign(_Nb, __zero);
1538 size_t __n = this->_Find_first();
1541 __s[_Nb - __n - 1] = __one;
1542 __n = _Find_next(__n);
1547 // 23.3.5.3 bitset operations:
1550 * @brief Global bitwise operations on bitsets.
1551 * @param __x A bitset.
1552 * @param __y A bitset of the same size as @a __x.
1553 * @return A new bitset.
1555 * These should be self-explanatory.
1557 template<size_t _Nb>
1558 _GLIBCXX23_CONSTEXPR
1560 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1562 bitset<_Nb> __result(__x);
1567 template<size_t _Nb>
1568 _GLIBCXX23_CONSTEXPR
1570 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1572 bitset<_Nb> __result(__x);
1577 template <size_t _Nb>
1578 _GLIBCXX23_CONSTEXPR
1580 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1582 bitset<_Nb> __result(__x);
1591 * @brief Global I/O operators for bitsets.
1593 * Direct I/O between streams and bitsets is supported. Output is
1594 * straightforward. Input will skip whitespace, only accept @a 0 and @a 1
1595 * characters, and will only extract as many digits as the %bitset will
1598 template<class _CharT, class _Traits, size_t _Nb>
1599 std::basic_istream<_CharT, _Traits>&
1600 operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
1602 typedef typename _Traits::char_type char_type;
1603 typedef std::basic_istream<_CharT, _Traits> __istream_type;
1604 typedef typename __istream_type::ios_base __ios_base;
1608 static _GLIBCXX_CONSTEXPR bool _S_use_alloca() { return _Nb <= 256; }
1610 explicit _Buffer(_CharT* __p) : _M_ptr(__p) { }
1614 if _GLIBCXX17_CONSTEXPR (!_S_use_alloca())
1618 _CharT* const _M_ptr;
1621 if _GLIBCXX17_CONSTEXPR (_Buffer::_S_use_alloca())
1622 __ptr = (_CharT*)__builtin_alloca(_Nb);
1624 __ptr = new _CharT[_Nb];
1625 const _Buffer __buf(__ptr);
1627 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1628 // 303. Bitset input operator underspecified
1629 const char_type __zero = __is.widen('0');
1630 const char_type __one = __is.widen('1');
1632 typename __ios_base::iostate __state = __ios_base::goodbit;
1633 typename __istream_type::sentry __sentry(__is);
1638 for (size_t __i = _Nb; __i > 0; --__i)
1640 static typename _Traits::int_type __eof = _Traits::eof();
1642 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
1643 if (_Traits::eq_int_type(__c1, __eof))
1645 __state |= __ios_base::eofbit;
1650 const char_type __c2 = _Traits::to_char_type(__c1);
1651 if (_Traits::eq(__c2, __zero))
1653 else if (_Traits::eq(__c2, __one))
1656 eq_int_type(__is.rdbuf()->sputbackc(__c2),
1659 __state |= __ios_base::failbit;
1665 __catch(__cxxabiv1::__forced_unwind&)
1667 __is._M_setstate(__ios_base::badbit);
1668 __throw_exception_again;
1671 { __is._M_setstate(__ios_base::badbit); }
1674 if _GLIBCXX17_CONSTEXPR (_Nb)
1676 if (size_t __len = __ptr - __buf._M_ptr)
1677 __x.template _M_copy_from_ptr<_CharT, _Traits>(__buf._M_ptr, __len,
1681 __state |= __ios_base::failbit;
1684 __is.setstate(__state);
1688 template <class _CharT, class _Traits, size_t _Nb>
1689 std::basic_ostream<_CharT, _Traits>&
1690 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1691 const bitset<_Nb>& __x)
1693 std::basic_string<_CharT, _Traits> __tmp;
1695 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1696 // 396. what are characters zero and one.
1697 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
1698 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1699 return __os << __tmp;
1704 _GLIBCXX_END_NAMESPACE_CONTAINER
1707 #undef _GLIBCXX_BITSET_WORDS
1708 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1709 #undef _GLIBCXX_BITSET_BITS_PER_ULL
1711 #if __cplusplus >= 201103L
1713 namespace std _GLIBCXX_VISIBILITY(default)
1715 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1718 /// std::hash specialization for bitset.
1719 template<size_t _Nb>
1720 struct hash<_GLIBCXX_STD_C::bitset<_Nb>>
1721 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>>
1724 operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept
1726 const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__;
1727 return std::_Hash_impl::hash(__b._M_getdata(), __clength);
1732 struct hash<_GLIBCXX_STD_C::bitset<0>>
1733 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>>
1736 operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept
1740 _GLIBCXX_END_NAMESPACE_VERSION
1745 #if defined _GLIBCXX_DEBUG && _GLIBCXX_HOSTED
1746 # include <debug/bitset>
1749 #endif /* _GLIBCXX_BITSET */