libstdc++
bitset
Go to the documentation of this file.
1 // <bitset> -*- C++ -*-
2 
3 // Copyright (C) 2001-2026 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 /*
26  * Copyright (c) 1998
27  * Silicon Graphics Computer Systems, Inc.
28  *
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.
36  */
37 
38 /** @file include/bitset
39  * This is a Standard C++ Library header.
40  */
41 
42 #ifndef _GLIBCXX_BITSET
43 #define _GLIBCXX_BITSET 1
44 
45 #ifdef _GLIBCXX_SYSHDR
46 #pragma GCC system_header
47 #endif
48 
49 #include <bits/stdexcept_throw.h> // For invalid_argument, out_of_range,
50  // overflow_error
51 #include <bits/stl_algobase.h> // For std::fill
52 
53 #if _GLIBCXX_HOSTED
54 # include <string>
55 # include <iosfwd>
56 # include <bits/cxxabi_forced.h>
57 #endif
58 
59 #if __cplusplus >= 201103L
60 # include <bits/functional_hash.h>
61 #endif
62 
63 #define __glibcxx_want_constexpr_bitset
64 #define __glibcxx_want_bitset // ...construct from string_view
65 #include <bits/version.h>
66 
67 #ifdef __cpp_lib_bitset // ...construct from string_view
68 # include <string_view>
69 #endif
70 
71 #define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * __SIZEOF_LONG__)
72 #define _GLIBCXX_BITSET_WORDS(__n) \
73  ((__n) / _GLIBCXX_BITSET_BITS_PER_WORD + \
74  ((__n) % _GLIBCXX_BITSET_BITS_PER_WORD == 0 ? 0 : 1))
75 
76 #define _GLIBCXX_BITSET_BITS_PER_ULL (__CHAR_BIT__ * __SIZEOF_LONG_LONG__)
77 
78 namespace std _GLIBCXX_VISIBILITY(default)
79 {
80 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
81 
82  /**
83  * Base class, general case. It is a class invariant that _Nw will be
84  * nonnegative.
85  *
86  * See documentation for bitset.
87  */
88  template<size_t _Nw>
89  struct _Base_bitset
90  {
91  typedef unsigned long _WordT;
92 
93  /// 0 is the least significant word.
94  _WordT _M_w[_Nw];
95 
96  _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
97  : _M_w() { }
98 
99 #if __cplusplus >= 201103L
100  constexpr _Base_bitset(unsigned long long __val) noexcept
101  : _M_w{ _WordT(__val)
102 #if __SIZEOF_LONG_LONG__ > __SIZEOF_LONG__
103  , _WordT(__val >> _GLIBCXX_BITSET_BITS_PER_WORD)
104 #endif
105  } { }
106 #else
107  _Base_bitset(unsigned long __val)
108  : _M_w()
109  { _M_w[0] = __val; }
110 #endif
111 
112  static _GLIBCXX_CONSTEXPR size_t
113  _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
114  { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
115 
116  static _GLIBCXX_CONSTEXPR size_t
117  _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
118  { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
119 
120  static _GLIBCXX_CONSTEXPR size_t
121  _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
122  { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
123 
124  static _GLIBCXX_CONSTEXPR _WordT
125  _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
126  { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
127 
128  _GLIBCXX14_CONSTEXPR _WordT&
129  _M_getword(size_t __pos) _GLIBCXX_NOEXCEPT
130  { return _M_w[_S_whichword(__pos)]; }
131 
132  _GLIBCXX_CONSTEXPR _WordT
133  _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT
134  { return _M_w[_S_whichword(__pos)]; }
135 
136 #if __cplusplus >= 201103L
137  constexpr const _WordT*
138  _M_getdata() const noexcept
139  { return _M_w; }
140 #endif
141 
142  _GLIBCXX23_CONSTEXPR _WordT&
143  _M_hiword() _GLIBCXX_NOEXCEPT
144  { return _M_w[_Nw - 1]; }
145 
146  _GLIBCXX_CONSTEXPR _WordT
147  _M_hiword() const _GLIBCXX_NOEXCEPT
148  { return _M_w[_Nw - 1]; }
149 
150  _GLIBCXX23_CONSTEXPR void
151  _M_do_and(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
152  {
153  for (size_t __i = 0; __i < _Nw; __i++)
154  _M_w[__i] &= __x._M_w[__i];
155  }
156 
157  _GLIBCXX14_CONSTEXPR void
158  _M_do_or(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
159  {
160  for (size_t __i = 0; __i < _Nw; __i++)
161  _M_w[__i] |= __x._M_w[__i];
162  }
163 
164  _GLIBCXX14_CONSTEXPR void
165  _M_do_xor(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
166  {
167  for (size_t __i = 0; __i < _Nw; __i++)
168  _M_w[__i] ^= __x._M_w[__i];
169  }
170 
171  _GLIBCXX14_CONSTEXPR void
172  _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT;
173 
174  _GLIBCXX14_CONSTEXPR void
175  _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT;
176 
177  _GLIBCXX14_CONSTEXPR void
178  _M_do_flip() _GLIBCXX_NOEXCEPT
179  {
180  for (size_t __i = 0; __i < _Nw; __i++)
181  _M_w[__i] = ~_M_w[__i];
182  }
183 
184  _GLIBCXX14_CONSTEXPR void
185  _M_do_set() _GLIBCXX_NOEXCEPT
186  {
187 #if __cplusplus >= 201402L
188  if (__builtin_is_constant_evaluated())
189  {
190  for (_WordT& __w : _M_w)
191  __w = ~static_cast<_WordT>(0);;
192  return;
193  }
194 #endif
195  __builtin_memset(_M_w, 0xFF, _Nw * sizeof(_WordT));
196  }
197 
198  _GLIBCXX14_CONSTEXPR void
199  _M_do_reset() _GLIBCXX_NOEXCEPT
200  {
201 #if __cplusplus >= 201402L
202  if (__builtin_is_constant_evaluated())
203  {
204  for (_WordT& __w : _M_w)
205  __w = 0;
206  return;
207  }
208 #endif
209  __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT));
210  }
211 
212  _GLIBCXX14_CONSTEXPR bool
213  _M_is_equal(const _Base_bitset<_Nw>& __x) const _GLIBCXX_NOEXCEPT
214  {
215 #if __cplusplus >= 201402L
216  if (__builtin_is_constant_evaluated())
217  {
218  for (size_t __i = 0; __i < _Nw; ++__i)
219  if (_M_w[__i] != __x._M_w[__i])
220  return false;
221  return true;
222  }
223 #endif
224  return !__builtin_memcmp(_M_w, __x._M_w, _Nw * sizeof(_WordT));
225  }
226 
227  template<size_t _Nb>
228  _GLIBCXX14_CONSTEXPR bool
229  _M_are_all() const _GLIBCXX_NOEXCEPT
230  {
231  for (size_t __i = 0; __i < _Nw - 1; __i++)
232  if (_M_w[__i] != ~static_cast<_WordT>(0))
233  return false;
234  return _M_hiword() == (~static_cast<_WordT>(0)
235  >> (_Nw * _GLIBCXX_BITSET_BITS_PER_WORD
236  - _Nb));
237  }
238 
239  _GLIBCXX14_CONSTEXPR bool
240  _M_is_any() const _GLIBCXX_NOEXCEPT
241  {
242  for (size_t __i = 0; __i < _Nw; __i++)
243  if (_M_w[__i] != static_cast<_WordT>(0))
244  return true;
245  return false;
246  }
247 
248  _GLIBCXX14_CONSTEXPR size_t
249  _M_do_count() const _GLIBCXX_NOEXCEPT
250  {
251  size_t __result = 0;
252  for (size_t __i = 0; __i < _Nw; __i++)
253  __result += __builtin_popcountl(_M_w[__i]);
254  return __result;
255  }
256 
257  _GLIBCXX14_CONSTEXPR unsigned long
258  _M_do_to_ulong() const;
259 
260 #if __cplusplus >= 201103L
261  _GLIBCXX14_CONSTEXPR unsigned long long
262  _M_do_to_ullong() const;
263 #endif
264 
265  // find first "on" bit
266  _GLIBCXX14_CONSTEXPR size_t
267  _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT;
268 
269  // find the next "on" bit that follows "prev"
270  _GLIBCXX14_CONSTEXPR size_t
271  _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT;
272  };
273 
274  // Definitions of non-inline functions from _Base_bitset.
275  template<size_t _Nw>
276  _GLIBCXX14_CONSTEXPR void
277  _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT
278  {
279  if (__builtin_expect(__shift != 0, 1))
280  {
281  const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
282  const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
283 
284  if (__offset == 0)
285  for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
286  _M_w[__n] = _M_w[__n - __wshift];
287  else
288  {
289  const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
290  - __offset);
291  for (size_t __n = _Nw - 1; __n > __wshift; --__n)
292  _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
293  | (_M_w[__n - __wshift - 1] >> __sub_offset));
294  _M_w[__wshift] = _M_w[0] << __offset;
295  }
296 
297  std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
298  }
299  }
300 
301  template<size_t _Nw>
302  _GLIBCXX14_CONSTEXPR void
303  _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT
304  {
305  if (__builtin_expect(__shift != 0, 1))
306  {
307  const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
308  const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
309  const size_t __limit = _Nw - __wshift - 1;
310 
311  if (__offset == 0)
312  for (size_t __n = 0; __n <= __limit; ++__n)
313  _M_w[__n] = _M_w[__n + __wshift];
314  else
315  {
316  const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
317  - __offset);
318  for (size_t __n = 0; __n < __limit; ++__n)
319  _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
320  | (_M_w[__n + __wshift + 1] << __sub_offset));
321  _M_w[__limit] = _M_w[_Nw-1] >> __offset;
322  }
323 
324  std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
325  }
326  }
327 
328  template<size_t _Nw>
329  _GLIBCXX14_CONSTEXPR unsigned long
330  _Base_bitset<_Nw>::_M_do_to_ulong() const
331  {
332  for (size_t __i = 1; __i < _Nw; ++__i)
333  if (_M_w[__i])
334  __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong"));
335  return _M_w[0];
336  }
337 
338 #if __cplusplus >= 201103L
339  template<size_t _Nw>
340  _GLIBCXX14_CONSTEXPR unsigned long long
341  _Base_bitset<_Nw>::_M_do_to_ullong() const
342  {
343 #if __SIZEOF_LONG_LONG__ == __SIZEOF_LONG__
344  return _M_do_to_ulong();
345 #else
346  for (size_t __i = 2; __i < _Nw; ++__i)
347  if (_M_w[__i])
348  __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong"));
349 
350  return _M_w[0] + (static_cast<unsigned long long>(_M_w[1])
351  << _GLIBCXX_BITSET_BITS_PER_WORD);
352 #endif
353  }
354 #endif // C++11
355 
356  template<size_t _Nw>
357  _GLIBCXX14_CONSTEXPR size_t
358  _Base_bitset<_Nw>::
359  _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT
360  {
361  for (size_t __i = 0; __i < _Nw; __i++)
362  {
363  _WordT __thisword = _M_w[__i];
364  if (__thisword != static_cast<_WordT>(0))
365  return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
366  + __builtin_ctzl(__thisword));
367  }
368  // not found, so return an indication of failure.
369  return __not_found;
370  }
371 
372  template<size_t _Nw>
373  _GLIBCXX14_CONSTEXPR size_t
374  _Base_bitset<_Nw>::
375  _M_do_find_next(size_t __prev, size_t __not_found) const _GLIBCXX_NOEXCEPT
376  {
377  // make bound inclusive
378  ++__prev;
379 
380  // check out of bounds
381  if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
382  return __not_found;
383 
384  // search first word
385  size_t __i = _S_whichword(__prev);
386  _WordT __thisword = _M_w[__i];
387 
388  // mask off bits below bound
389  __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
390 
391  if (__thisword != static_cast<_WordT>(0))
392  return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
393  + __builtin_ctzl(__thisword));
394 
395  // check subsequent words
396  __i++;
397  for (; __i < _Nw; __i++)
398  {
399  __thisword = _M_w[__i];
400  if (__thisword != static_cast<_WordT>(0))
401  return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
402  + __builtin_ctzl(__thisword));
403  }
404  // not found, so return an indication of failure.
405  return __not_found;
406  } // end _M_do_find_next
407 
408  /**
409  * Base class, specialization for a single word.
410  *
411  * See documentation for bitset.
412  */
413  template<>
414  struct _Base_bitset<1>
415  {
416  typedef unsigned long _WordT;
417  _WordT _M_w;
418 
419  _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
420  : _M_w(0)
421  { }
422 
423 #if __cplusplus >= 201103L
424  constexpr _Base_bitset(unsigned long long __val) noexcept
425 #else
426  _Base_bitset(unsigned long __val)
427 #endif
428  : _M_w(__val)
429  { }
430 
431  static _GLIBCXX_CONSTEXPR size_t
432  _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
433  { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
434 
435  static _GLIBCXX_CONSTEXPR size_t
436  _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
437  { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
438 
439  static _GLIBCXX_CONSTEXPR size_t
440  _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
441  { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
442 
443  static _GLIBCXX_CONSTEXPR _WordT
444  _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
445  { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
446 
447  _GLIBCXX14_CONSTEXPR _WordT&
448  _M_getword(size_t) _GLIBCXX_NOEXCEPT
449  { return _M_w; }
450 
451  _GLIBCXX_CONSTEXPR _WordT
452  _M_getword(size_t) const _GLIBCXX_NOEXCEPT
453  { return _M_w; }
454 
455 #if __cplusplus >= 201103L
456  constexpr const _WordT*
457  _M_getdata() const noexcept
458  { return &_M_w; }
459 #endif
460 
461  _GLIBCXX14_CONSTEXPR _WordT&
462  _M_hiword() _GLIBCXX_NOEXCEPT
463  { return _M_w; }
464 
465  _GLIBCXX_CONSTEXPR _WordT
466  _M_hiword() const _GLIBCXX_NOEXCEPT
467  { return _M_w; }
468 
469  _GLIBCXX14_CONSTEXPR void
470  _M_do_and(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT
471  { _M_w &= __x._M_w; }
472 
473  _GLIBCXX14_CONSTEXPR void
474  _M_do_or(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT
475  { _M_w |= __x._M_w; }
476 
477  _GLIBCXX14_CONSTEXPR void
478  _M_do_xor(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT
479  { _M_w ^= __x._M_w; }
480 
481  _GLIBCXX14_CONSTEXPR void
482  _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT
483  { _M_w <<= __shift; }
484 
485  _GLIBCXX14_CONSTEXPR void
486  _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT
487  { _M_w >>= __shift; }
488 
489  _GLIBCXX14_CONSTEXPR void
490  _M_do_flip() _GLIBCXX_NOEXCEPT
491  { _M_w = ~_M_w; }
492 
493  _GLIBCXX14_CONSTEXPR void
494  _M_do_set() _GLIBCXX_NOEXCEPT
495  { _M_w = ~static_cast<_WordT>(0); }
496 
497  _GLIBCXX14_CONSTEXPR void
498  _M_do_reset() _GLIBCXX_NOEXCEPT
499  { _M_w = 0; }
500 
501  _GLIBCXX14_CONSTEXPR bool
502  _M_is_equal(const _Base_bitset<1>& __x) const _GLIBCXX_NOEXCEPT
503  { return _M_w == __x._M_w; }
504 
505  template<size_t _Nb>
506  _GLIBCXX14_CONSTEXPR bool
507  _M_are_all() const _GLIBCXX_NOEXCEPT
508  { return _M_w == (~static_cast<_WordT>(0)
509  >> (_GLIBCXX_BITSET_BITS_PER_WORD - _Nb)); }
510 
511  _GLIBCXX14_CONSTEXPR bool
512  _M_is_any() const _GLIBCXX_NOEXCEPT
513  { return _M_w != 0; }
514 
515  _GLIBCXX14_CONSTEXPR size_t
516  _M_do_count() const _GLIBCXX_NOEXCEPT
517  { return __builtin_popcountl(_M_w); }
518 
519  _GLIBCXX14_CONSTEXPR unsigned long
520  _M_do_to_ulong() const _GLIBCXX_NOEXCEPT
521  { return _M_w; }
522 
523 #if __cplusplus >= 201103L
524  constexpr unsigned long long
525  _M_do_to_ullong() const noexcept
526  { return _M_w; }
527 #endif
528 
529  _GLIBCXX14_CONSTEXPR size_t
530  _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT
531  {
532  if (_M_w != 0)
533  return __builtin_ctzl(_M_w);
534  else
535  return __not_found;
536  }
537 
538  // find the next "on" bit that follows "prev"
539  _GLIBCXX14_CONSTEXPR size_t
540  _M_do_find_next(size_t __prev, size_t __not_found) const
541  _GLIBCXX_NOEXCEPT
542  {
543  ++__prev;
544  if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
545  return __not_found;
546 
547  _WordT __x = _M_w >> __prev;
548  if (__x != 0)
549  return __builtin_ctzl(__x) + __prev;
550  else
551  return __not_found;
552  }
553  };
554 
555  /**
556  * Base class, specialization for no storage (zero-length %bitset).
557  *
558  * See documentation for bitset.
559  */
560  template<>
561  struct _Base_bitset<0>
562  {
563  typedef unsigned long _WordT;
564 
565  _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
566  { }
567 
568 #if __cplusplus >= 201103L
569  constexpr _Base_bitset(unsigned long long) noexcept
570 #else
571  _Base_bitset(unsigned long)
572 #endif
573  { }
574 
575  static _GLIBCXX_CONSTEXPR size_t
576  _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
577  { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
578 
579  static _GLIBCXX_CONSTEXPR size_t
580  _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
581  { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
582 
583  static _GLIBCXX_CONSTEXPR size_t
584  _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
585  { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
586 
587  static _GLIBCXX_CONSTEXPR _WordT
588  _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
589  { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
590 
591  // This would normally give access to the data. The bounds-checking
592  // in the bitset class will prevent the user from getting this far,
593  // but this must fail if the user calls _Unchecked_set directly.
594  // Let's not penalize zero-length users unless they actually
595  // make an unchecked call; all the memory ugliness is therefore
596  // localized to this single should-never-get-this-far function.
597  __attribute__((__noreturn__))
598  _WordT&
599  _M_getword(size_t) _GLIBCXX_NOEXCEPT
600  { __throw_out_of_range(__N("_Base_bitset::_M_getword")); }
601 
602  _GLIBCXX_CONSTEXPR _WordT
603  _M_getword(size_t) const _GLIBCXX_NOEXCEPT
604  { return 0; }
605 
606  _GLIBCXX_CONSTEXPR _WordT
607  _M_hiword() const _GLIBCXX_NOEXCEPT
608  { return 0; }
609 
610  _GLIBCXX14_CONSTEXPR void
611  _M_do_and(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT
612  { }
613 
614  _GLIBCXX14_CONSTEXPR void
615  _M_do_or(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT
616  { }
617 
618  _GLIBCXX14_CONSTEXPR void
619  _M_do_xor(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT
620  { }
621 
622  _GLIBCXX14_CONSTEXPR void
623  _M_do_left_shift(size_t) _GLIBCXX_NOEXCEPT
624  { }
625 
626  _GLIBCXX14_CONSTEXPR void
627  _M_do_right_shift(size_t) _GLIBCXX_NOEXCEPT
628  { }
629 
630  _GLIBCXX14_CONSTEXPR void
631  _M_do_flip() _GLIBCXX_NOEXCEPT
632  { }
633 
634  _GLIBCXX14_CONSTEXPR void
635  _M_do_set() _GLIBCXX_NOEXCEPT
636  { }
637 
638  _GLIBCXX14_CONSTEXPR void
639  _M_do_reset() _GLIBCXX_NOEXCEPT
640  { }
641 
642  // Are all empty bitsets equal to each other? Are they equal to
643  // themselves? How to compare a thing which has no state? What is
644  // the sound of one zero-length bitset clapping?
645  _GLIBCXX_CONSTEXPR bool
646  _M_is_equal(const _Base_bitset<0>&) const _GLIBCXX_NOEXCEPT
647  { return true; }
648 
649  template<size_t _Nb>
650  _GLIBCXX_CONSTEXPR bool
651  _M_are_all() const _GLIBCXX_NOEXCEPT
652  { return true; }
653 
654  _GLIBCXX_CONSTEXPR bool
655  _M_is_any() const _GLIBCXX_NOEXCEPT
656  { return false; }
657 
658  _GLIBCXX_CONSTEXPR size_t
659  _M_do_count() const _GLIBCXX_NOEXCEPT
660  { return 0; }
661 
662  _GLIBCXX_CONSTEXPR unsigned long
663  _M_do_to_ulong() const _GLIBCXX_NOEXCEPT
664  { return 0; }
665 
666 #if __cplusplus >= 201103L
667  constexpr unsigned long long
668  _M_do_to_ullong() const noexcept
669  { return 0; }
670 #endif
671 
672  // Normally "not found" is the size, but that could also be
673  // misinterpreted as an index in this corner case. Oh well.
674  _GLIBCXX_CONSTEXPR size_t
675  _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT
676  { return 0; }
677 
678  _GLIBCXX_CONSTEXPR size_t
679  _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT
680  { return 0; }
681  };
682 
683 
684  // Helper class to zero out the unused high-order bits in the highest word.
685  template<size_t _Extrabits>
686  struct _Sanitize
687  {
688  typedef unsigned long _WordT;
689 
690  static _GLIBCXX14_CONSTEXPR void
691  _S_do_sanitize(_WordT& __val) _GLIBCXX_NOEXCEPT
692  { __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); }
693  };
694 
695  template<>
696  struct _Sanitize<0>
697  {
698  typedef unsigned long _WordT;
699 
700  static _GLIBCXX14_CONSTEXPR void
701  _S_do_sanitize(_WordT) _GLIBCXX_NOEXCEPT { }
702  };
703 
704 #if __cplusplus >= 201103L
705  template<size_t _Nb, bool = (_Nb < _GLIBCXX_BITSET_BITS_PER_ULL)>
706  struct _Sanitize_val
707  {
708  static constexpr unsigned long long
709  _S_do_sanitize_val(unsigned long long __val)
710  { return __val; }
711  };
712 
713  template<size_t _Nb>
714  struct _Sanitize_val<_Nb, true>
715  {
716  static constexpr unsigned long long
717  _S_do_sanitize_val(unsigned long long __val)
718  { return __val & ~((~static_cast<unsigned long long>(0)) << _Nb); }
719  };
720 
721  namespace __bitset
722  {
723 #ifdef __cpp_lib_bitset // ...construct from string_view
724  template<typename _CharT>
725  using __string = std::basic_string_view<_CharT>;
726 #elif _GLIBCXX_HOSTED
727  template<typename _CharT>
728  using __string = std::basic_string<_CharT>;
729 #else
730  template<typename _CharT>
731  struct __string
732  {
733  using size_type = size_t;
734  static constexpr size_type npos = size_type(-1);
735 
736  struct traits_type
737  {
738  static _GLIBCXX14_CONSTEXPR size_t
739  length(const _CharT* __s) noexcept
740  {
741  size_t __n = 0;
742  while (__s[__n])
743  __n++;
744  return __n;
745  }
746 
747  static constexpr bool
748  eq(_CharT __l, _CharT __r) noexcept
749  { return __l == __r; }
750  };
751  };
752 #endif // HOSTED
753  } // namespace __bitset
754 #endif // C++11
755 
756  /**
757  * @brief The %bitset class represents a @e fixed-size sequence of bits.
758  * @ingroup utilities
759  *
760  * (Note that %bitset does @e not meet the formal requirements of a
761  * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.)
762  *
763  * The template argument, `Nb`, may be any non-negative number,
764  * specifying the number of bits (e.g., "0", "12", "1024*1024").
765  *
766  * In the general unoptimized case, storage is allocated in word-sized
767  * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B
768  * words will be used for storage. B - Nb%B bits are unused. (They are
769  * the high-order bits in the highest word.) It is a class invariant
770  * that those unused bits are always zero.
771  *
772  * If you think of %bitset as <em>a simple array of bits</em>, be
773  * aware that your mental picture is reversed: a %bitset behaves
774  * the same way as bits in integers do, with the bit at index 0 in
775  * the <em>least significant / right-hand</em> position, and the bit at
776  * index Nb-1 in the <em>most significant / left-hand</em> position.
777  * Thus, unlike other containers, a %bitset's index <em>counts from
778  * right to left</em>, to put it very loosely.
779  *
780  * This behavior is preserved when translating to and from strings. For
781  * example, the first line of the following program probably prints
782  * <em>b(&apos;a&apos;) is 0001100001</em> on a modern ASCII system.
783  *
784  * @code
785  * #include <bitset>
786  * #include <iostream>
787  * #include <sstream>
788  *
789  * using namespace std;
790  *
791  * int main()
792  * {
793  * long a = 'a';
794  * bitset<10> b(a);
795  *
796  * cout << "b('a') is " << b << endl;
797  *
798  * ostringstream s;
799  * s << b;
800  * string str = s.str();
801  * cout << "index 3 in the string is " << str[3] << " but\n"
802  * << "index 3 in the bitset is " << b[3] << endl;
803  * }
804  * @endcode
805  *
806  * Also see:
807  * https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_containers.html
808  * for a description of extensions.
809  *
810  * Most of the actual code isn't contained in %bitset<> itself, but in the
811  * base class _Base_bitset. The base class works with whole words, not with
812  * individual bits. This allows us to specialize _Base_bitset for the
813  * important special case where the %bitset is only a single word.
814  *
815  * Extra confusion can result due to the fact that the storage for
816  * _Base_bitset @e is a regular array, and is indexed as such. This is
817  * carefully encapsulated.
818  */
819  template<size_t _Nb>
820  class bitset
821  : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
822  {
823  private:
824  typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
825  typedef unsigned long _WordT;
826 
827  template<class _Str>
828  _GLIBCXX23_CONSTEXPR void
829  _M_check_initial_position(
830  const _Str& __s, typename _Str::size_type __position) const
831  {
832  if (__position > __s.size())
833  __throw_out_of_range_fmt(
834  __N("bitset::bitset:"
835  " __position (which is %zu) > __s.size() (which is %zu)"),
836  size_t(__position), size_t(__s.size()));
837  }
838 
839  _GLIBCXX23_CONSTEXPR
840  void _M_check(size_t __position, const char *__s) const
841  {
842  if (__position >= _Nb)
843  __throw_out_of_range_fmt(
844  __N("%s: __position (which is %zu) >= _Nb (which is %zu)"),
845  __s, size_t(__position), size_t(_Nb));
846  }
847 
848  _GLIBCXX23_CONSTEXPR
849  void
850  _M_do_sanitize() _GLIBCXX_NOEXCEPT
851  {
852  typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type;
853  __sanitize_type::_S_do_sanitize(this->_M_hiword());
854  }
855 
856 #if __cplusplus >= 201103L
857  friend struct std::hash<bitset>;
858 #endif
859 
860  public:
861  /**
862  * This encapsulates the concept of a single bit. An instance of this
863  * class is a proxy for an actual bit; this way the individual bit
864  * operations are done as faster word-size bitwise instructions.
865  *
866  * Most users will never need to use this class directly; conversions
867  * to and from bool are automatic and should be transparent. Overloaded
868  * operators help to preserve the illusion.
869  *
870  * (On a typical system, this <em>bit %reference</em> is 64
871  * times the size of an actual bit. Ha.)
872  */
873  class reference
874  {
875  friend class bitset;
876 
877  _WordT* _M_wp;
878  size_t _M_bpos;
879 
880  _GLIBCXX23_CONSTEXPR
881  reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT
882  {
883  _M_wp = &__b._M_getword(__pos);
884  _M_bpos = _Base::_S_whichbit(__pos);
885  }
886 
887  public:
888 #if __cplusplus >= 201103L
889  reference(const reference&) = default;
890 #endif
891 
892 #if __cplusplus > 202002L && __cpp_constexpr_dynamic_alloc
893  constexpr
894 #endif
895  ~reference() _GLIBCXX_NOEXCEPT
896  { }
897 
898  // For b[i] = __x;
899  _GLIBCXX23_CONSTEXPR
900  reference&
901  operator=(bool __x) _GLIBCXX_NOEXCEPT
902  {
903  if (__x)
904  *_M_wp |= _Base::_S_maskbit(_M_bpos);
905  else
906  *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
907  return *this;
908  }
909 
910  // For b[i] = b[__j];
911  _GLIBCXX23_CONSTEXPR
912  reference&
913  operator=(const reference& __j) _GLIBCXX_NOEXCEPT
914  {
915  if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
916  *_M_wp |= _Base::_S_maskbit(_M_bpos);
917  else
918  *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
919  return *this;
920  }
921 
922  // Flips the bit
923  _GLIBCXX23_CONSTEXPR
924  bool
925  operator~() const _GLIBCXX_NOEXCEPT
926  { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
927 
928  // For __x = b[i];
929  _GLIBCXX23_CONSTEXPR
930  operator bool() const _GLIBCXX_NOEXCEPT
931  { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
932 
933  // For b[i].flip();
934  _GLIBCXX23_CONSTEXPR
935  reference&
936  flip() _GLIBCXX_NOEXCEPT
937  {
938  *_M_wp ^= _Base::_S_maskbit(_M_bpos);
939  return *this;
940  }
941  };
942  friend class reference;
943 
944  // 23.3.5.1 constructors:
945  /// All bits set to zero.
946  _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT
947  { }
948 
949  /// Initial bits bitwise-copied from a single word (others set to zero).
950 #if __cplusplus >= 201103L
951  constexpr bitset(unsigned long long __val) noexcept
952  : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { }
953 #else
954  bitset(unsigned long __val)
955  : _Base(__val)
956  { _M_do_sanitize(); }
957 #endif
958 
959 #if _GLIBCXX_HOSTED
960  /**
961  * Use a subset of a string.
962  * @param __s A string of `0` and `1` characters.
963  * @param __position Index of the first character in `__s` to use;
964  * defaults to zero.
965  * @throw std::out_of_range If `__position > __s.size()`.
966  * @throw std::invalid_argument If a character appears in the string
967  * which is neither `0` nor `1`.
968  */
969  template<class _CharT, class _Traits, class _Alloc>
970  _GLIBCXX23_CONSTEXPR
971  explicit
972  bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
973  size_t __position = 0)
974  : _Base()
975  {
976  _M_check_initial_position(__s, __position);
977  _M_copy_from_string(__s, __position,
978  std::basic_string<_CharT, _Traits, _Alloc>::npos,
979  _CharT('0'), _CharT('1'));
980  }
981 
982  /**
983  * Use a subset of a string.
984  * @param __s A string of `0` and `1` characters.
985  * @param __position Index of the first character in `__s` to use.
986  * @param __n The number of characters to copy.
987  * @throw std::out_of_range If `__position > __s.size()`.
988  * @throw std::invalid_argument If a character appears in the string
989  * which is neither `0` nor `1`.
990  */
991  template<class _CharT, class _Traits, class _Alloc>
992  _GLIBCXX23_CONSTEXPR
993  bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
994  size_t __position, size_t __n)
995  : _Base()
996  {
997  _M_check_initial_position(__s, __position);
998  _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1'));
999  }
1000 
1001  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1002  // 396. what are characters zero and one.
1003  template<class _CharT, class _Traits, class _Alloc>
1004  _GLIBCXX23_CONSTEXPR
1005  bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
1006  size_t __position, size_t __n,
1007  _CharT __zero, _CharT __one = _CharT('1'))
1008  : _Base()
1009  {
1010  _M_check_initial_position(__s, __position);
1011  _M_copy_from_string(__s, __position, __n, __zero, __one);
1012  }
1013 #endif // HOSTED
1014 
1015 #ifdef __cpp_lib_bitset // C++ >= 23
1016  /**
1017  * Use a subset of a string view.
1018  * @param __s A `string_view` of a sequence of `0` and `1` characters.
1019  * @param __position Index of the first character in `__s` to use.
1020  * @param __n The maximum number of characters from `__s` to use.
1021  * @param __zero The character corresponding to the value 0.
1022  * @param __one The character corresponding to the value 1.
1023  * @throw std::out_of_range If `__position > __s.size()`.
1024  * @throw std::invalid_argument If a character appears in `__s`
1025  * which is neither `0` nor `1`.
1026  */
1027  template<class _CharT, class _Traits>
1028  constexpr explicit
1029  bitset(basic_string_view<_CharT, _Traits> __s,
1030  basic_string_view<_CharT, _Traits>::size_type __position = 0,
1031  basic_string_view<_CharT, _Traits>::size_type __n =
1032  basic_string_view<_CharT, _Traits>::npos,
1033  _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'))
1034  : _Base()
1035  {
1036  _M_check_initial_position(__s, __position);
1037  _M_copy_from_ptr<_CharT, _Traits>(
1038  __s.data(), __s.size(), __position, __n, __zero, __one);
1039  }
1040 #endif
1041 
1042 #if __cplusplus >= 201103L
1043  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1044  // 4294. bitset(const CharT*) constructor needs to be constrained
1045  /**
1046  * Construct from a character %array.
1047  * @param __str An %array of characters `__zero` and `__one`.
1048  * @param __n The number of characters to use.
1049  * @param __zero The character corresponding to the value 0.
1050  * @param __one The character corresponding to the value 1.
1051  * @throw std::invalid_argument If a character appears in the string
1052  * which is neither `__zero` nor `__one`.
1053  */
1054  template<typename _CharT,
1055  typename = _Require<is_trivially_copyable<_CharT>,
1056  is_standard_layout<_CharT>,
1057  is_trivially_default_constructible<_CharT>,
1058  __not_<is_array<_CharT>>>>
1059  [[__gnu__::__nonnull__]]
1060  _GLIBCXX23_CONSTEXPR
1061  explicit
1062  bitset(const _CharT* __str,
1063  typename __bitset::__string<_CharT>::size_type __n
1064  = __bitset::__string<_CharT>::npos,
1065  _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'))
1066  : _Base()
1067  {
1068  if (!__str)
1069  __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)"));
1070  using _Traits = typename __bitset::__string<_CharT>::traits_type;
1071 
1072  if (__n == __bitset::__string<_CharT>::npos)
1073  __n = _Traits::length(__str);
1074  _M_copy_from_ptr<_CharT, _Traits>(__str, __n, 0, __n, __zero, __one);
1075  }
1076 #endif // C++11
1077 
1078  // 23.3.5.2 bitset operations:
1079  ///@{
1080  /**
1081  * Operations on bitsets.
1082  * @param __rhs A same-sized bitset.
1083  *
1084  * These should be self-explanatory.
1085  */
1086  _GLIBCXX23_CONSTEXPR
1087  bitset<_Nb>&
1088  operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
1089  {
1090  this->_M_do_and(__rhs);
1091  return *this;
1092  }
1093 
1094  _GLIBCXX23_CONSTEXPR
1095  bitset<_Nb>&
1096  operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
1097  {
1098  this->_M_do_or(__rhs);
1099  return *this;
1100  }
1101 
1102  _GLIBCXX23_CONSTEXPR
1103  bitset<_Nb>&
1104  operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
1105  {
1106  this->_M_do_xor(__rhs);
1107  return *this;
1108  }
1109  ///@}
1110 
1111  ///@{
1112  /**
1113  * Operations on bitsets.
1114  * @param __position The number of places to shift.
1115  *
1116  * These should be self-explanatory.
1117  */
1118  _GLIBCXX23_CONSTEXPR
1119  bitset<_Nb>&
1120  operator<<=(size_t __position) _GLIBCXX_NOEXCEPT
1121  {
1122  if (__builtin_expect(__position < _Nb, 1))
1123  {
1124  this->_M_do_left_shift(__position);
1125  this->_M_do_sanitize();
1126  }
1127  else
1128  this->_M_do_reset();
1129  return *this;
1130  }
1131 
1132  _GLIBCXX23_CONSTEXPR
1133  bitset<_Nb>&
1134  operator>>=(size_t __position) _GLIBCXX_NOEXCEPT
1135  {
1136  if (__builtin_expect(__position < _Nb, 1))
1137  this->_M_do_right_shift(__position);
1138  else
1139  this->_M_do_reset();
1140  return *this;
1141  }
1142  ///@}
1143 
1144  ///@{
1145  /**
1146  * These versions of single-bit set, reset, flip, and test are
1147  * extensions from the SGI version. They do no range checking.
1148  * @ingroup SGIextensions
1149  */
1150  _GLIBCXX23_CONSTEXPR
1151  bitset<_Nb>&
1152  _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT
1153  {
1154  this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
1155  return *this;
1156  }
1157 
1158  _GLIBCXX23_CONSTEXPR
1159  bitset<_Nb>&
1160  _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT
1161  {
1162  if (__val)
1163  this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
1164  else
1165  this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
1166  return *this;
1167  }
1168 
1169  _GLIBCXX23_CONSTEXPR
1170  bitset<_Nb>&
1171  _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT
1172  {
1173  this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
1174  return *this;
1175  }
1176 
1177  _GLIBCXX23_CONSTEXPR
1178  bitset<_Nb>&
1179  _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT
1180  {
1181  this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
1182  return *this;
1183  }
1184 
1185  _GLIBCXX_CONSTEXPR bool
1186  _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT
1187  { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
1188  != static_cast<_WordT>(0)); }
1189  ///@}
1190 
1191  // Set, reset, and flip.
1192  /**
1193  * @brief Sets every bit to true.
1194  */
1195  _GLIBCXX23_CONSTEXPR
1196  bitset<_Nb>&
1197  set() _GLIBCXX_NOEXCEPT
1198  {
1199  this->_M_do_set();
1200  this->_M_do_sanitize();
1201  return *this;
1202  }
1203 
1204  /**
1205  * @brief Sets a given bit to a particular value.
1206  * @param __position The index of the bit.
1207  * @param __val Either true or false, defaults to true.
1208  * @throw std::out_of_range If @a pos is bigger the size of the %set.
1209  */
1210  _GLIBCXX23_CONSTEXPR
1211  bitset<_Nb>&
1212  set(size_t __position, bool __val = true)
1213  {
1214  this->_M_check(__position, __N("bitset::set"));
1215  return _Unchecked_set(__position, __val);
1216  }
1217 
1218  /**
1219  * @brief Sets every bit to false.
1220  */
1221  _GLIBCXX23_CONSTEXPR
1222  bitset<_Nb>&
1223  reset() _GLIBCXX_NOEXCEPT
1224  {
1225  this->_M_do_reset();
1226  return *this;
1227  }
1228 
1229  /**
1230  * @brief Sets a given bit to false.
1231  * @param __position The index of the bit.
1232  * @throw std::out_of_range If @a pos is bigger the size of the %set.
1233  *
1234  * Same as writing @c set(pos,false).
1235  */
1236  _GLIBCXX23_CONSTEXPR
1237  bitset<_Nb>&
1238  reset(size_t __position)
1239  {
1240  this->_M_check(__position, __N("bitset::reset"));
1241  return _Unchecked_reset(__position);
1242  }
1243 
1244  /**
1245  * @brief Toggles every bit to its opposite value.
1246  */
1247  _GLIBCXX23_CONSTEXPR
1248  bitset<_Nb>&
1249  flip() _GLIBCXX_NOEXCEPT
1250  {
1251  this->_M_do_flip();
1252  this->_M_do_sanitize();
1253  return *this;
1254  }
1255 
1256  /**
1257  * @brief Toggles a given bit to its opposite value.
1258  * @param __position The index of the bit.
1259  * @throw std::out_of_range If @a pos is bigger the size of the %set.
1260  */
1261  _GLIBCXX23_CONSTEXPR
1262  bitset<_Nb>&
1263  flip(size_t __position)
1264  {
1265  this->_M_check(__position, __N("bitset::flip"));
1266  return _Unchecked_flip(__position);
1267  }
1268 
1269  /// See the no-argument flip().
1270  _GLIBCXX23_CONSTEXPR
1271  bitset<_Nb>
1272  operator~() const _GLIBCXX_NOEXCEPT
1273  { return bitset<_Nb>(*this).flip(); }
1274 
1275  ///@{
1276  /**
1277  * @brief Array-indexing support.
1278  * @param __position Index into the %bitset.
1279  * @return A bool for a <em>const %bitset</em>. For non-const
1280  * bitsets, an instance of the reference proxy class.
1281  * @note These operators do no range checking and throw no exceptions,
1282  * as required by DR 11 to the standard.
1283  *
1284  * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
1285  * resolves DR 11 (items 1 and 2), but does not do the range-checking
1286  * required by that DR's resolution. -pme
1287  * The DR has since been changed: range-checking is a precondition
1288  * (users' responsibility), and these functions must not throw. -pme
1289  */
1290  _GLIBCXX23_CONSTEXPR
1291  reference
1292  operator[](size_t __position)
1293  {
1294  __glibcxx_assert(__position < _Nb);
1295  return reference(*this, __position);
1296  }
1297 
1298  _GLIBCXX_CONSTEXPR bool
1299  operator[](size_t __position) const
1300  {
1301 #if __cplusplus != 201103L
1302  __glibcxx_assert(__position < _Nb);
1303  return _Unchecked_test(__position);
1304 #elif defined(_GLIBCXX_ASSERTIONS)
1305  // C++11 forbids a compound stmt in a constexpr function.
1306  return __position < _Nb ? _Unchecked_test(__position)
1307  : (__builtin_trap(), false);
1308 #else
1309  return _Unchecked_test(__position);
1310 #endif
1311  }
1312  ///@}
1313 
1314  /**
1315  * @brief Returns a numerical interpretation of the %bitset.
1316  * @return The integral equivalent of the bits.
1317  * @throw std::overflow_error If there are too many bits to be
1318  * represented in an @c unsigned @c long.
1319  */
1320  _GLIBCXX23_CONSTEXPR
1321  unsigned long
1322  to_ulong() const
1323  { return this->_M_do_to_ulong(); }
1324 
1325 #if __cplusplus >= 201103L
1326  _GLIBCXX23_CONSTEXPR
1327  unsigned long long
1328  to_ullong() const
1329  { return this->_M_do_to_ullong(); }
1330 #endif
1331 
1332 #if _GLIBCXX_HOSTED
1333  /**
1334  * @brief Returns a character interpretation of the %bitset.
1335  * @return The string equivalent of the bits.
1336  *
1337  * Note the ordering of the bits: decreasing character positions
1338  * correspond to increasing bit positions (see the main class notes for
1339  * an example).
1340  */
1341  template<class _CharT, class _Traits, class _Alloc>
1342  _GLIBCXX23_CONSTEXPR
1343  std::basic_string<_CharT, _Traits, _Alloc>
1344  to_string() const
1345  {
1346  std::basic_string<_CharT, _Traits, _Alloc> __result;
1347  _M_copy_to_string(__result, _CharT('0'), _CharT('1'));
1348  return __result;
1349  }
1350 
1351  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1352  // 396. what are characters zero and one.
1353  template<class _CharT, class _Traits, class _Alloc>
1354  _GLIBCXX23_CONSTEXPR
1355  std::basic_string<_CharT, _Traits, _Alloc>
1356  to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1357  {
1358  std::basic_string<_CharT, _Traits, _Alloc> __result;
1359  _M_copy_to_string(__result, __zero, __one);
1360  return __result;
1361  }
1362 
1363  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1364  // 434. bitset::to_string() hard to use.
1365  template<class _CharT, class _Traits>
1366  _GLIBCXX23_CONSTEXPR
1367  std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1368  to_string() const
1369  { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
1370 
1371  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1372  // 853. to_string needs updating with zero and one.
1373  template<class _CharT, class _Traits>
1374  _GLIBCXX23_CONSTEXPR
1375  std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1376  to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1377  { return to_string<_CharT, _Traits,
1378  std::allocator<_CharT> >(__zero, __one); }
1379 
1380  template<class _CharT>
1381  _GLIBCXX23_CONSTEXPR
1382  std::basic_string<_CharT, std::char_traits<_CharT>,
1383  std::allocator<_CharT> >
1384  to_string() const
1385  {
1386  return to_string<_CharT, std::char_traits<_CharT>,
1387  std::allocator<_CharT> >();
1388  }
1389 
1390  template<class _CharT>
1391  _GLIBCXX23_CONSTEXPR
1392  std::basic_string<_CharT, std::char_traits<_CharT>,
1393  std::allocator<_CharT> >
1394  to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1395  {
1396  return to_string<_CharT, std::char_traits<_CharT>,
1397  std::allocator<_CharT> >(__zero, __one);
1398  }
1399 
1400  _GLIBCXX23_CONSTEXPR
1401  std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1402  to_string() const
1403  {
1404  return to_string<char, std::char_traits<char>,
1405  std::allocator<char> >();
1406  }
1407 
1408  _GLIBCXX23_CONSTEXPR
1409  std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1410  to_string(char __zero, char __one = '1') const
1411  {
1412  return to_string<char, std::char_traits<char>,
1413  std::allocator<char> >(__zero, __one);
1414  }
1415 #endif // HOSTED
1416 
1417  /// Returns the number of bits which are set.
1418  _GLIBCXX23_CONSTEXPR
1419  size_t
1420  count() const _GLIBCXX_NOEXCEPT
1421  { return this->_M_do_count(); }
1422 
1423  /// Returns the total number of bits.
1424  _GLIBCXX_CONSTEXPR size_t
1425  size() const _GLIBCXX_NOEXCEPT
1426  { return _Nb; }
1427 
1428  ///@{
1429  /// These comparisons for equality/inequality are, well, @e bitwise.
1430  _GLIBCXX23_CONSTEXPR
1431  bool
1432  operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
1433  { return this->_M_is_equal(__rhs); }
1434 
1435 #if __cpp_impl_three_way_comparison < 201907L
1436  _GLIBCXX23_CONSTEXPR
1437  bool
1438  operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
1439  { return !this->_M_is_equal(__rhs); }
1440 #endif
1441  ///@}
1442 
1443  /**
1444  * @brief Tests the value of a bit.
1445  * @param __position The index of a bit.
1446  * @return The value at @a pos.
1447  * @throw std::out_of_range If @a pos is bigger the size of the %set.
1448  */
1449  _GLIBCXX23_CONSTEXPR
1450  bool
1451  test(size_t __position) const
1452  {
1453  this->_M_check(__position, __N("bitset::test"));
1454  return _Unchecked_test(__position);
1455  }
1456 
1457  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1458  // DR 693. std::bitset::all() missing.
1459  /**
1460  * @brief Tests whether all the bits are on.
1461  * @return True if all the bits are set.
1462  */
1463  _GLIBCXX23_CONSTEXPR
1464  bool
1465  all() const _GLIBCXX_NOEXCEPT
1466  { return this->template _M_are_all<_Nb>(); }
1467 
1468  /**
1469  * @brief Tests whether any of the bits are on.
1470  * @return True if at least one bit is set.
1471  */
1472  _GLIBCXX23_CONSTEXPR
1473  bool
1474  any() const _GLIBCXX_NOEXCEPT
1475  { return this->_M_is_any(); }
1476 
1477  /**
1478  * @brief Tests whether any of the bits are on.
1479  * @return True if none of the bits are set.
1480  */
1481  _GLIBCXX23_CONSTEXPR
1482  bool
1483  none() const _GLIBCXX_NOEXCEPT
1484  { return !this->_M_is_any(); }
1485 
1486  ///@{
1487  /// Self-explanatory.
1488  _GLIBCXX23_CONSTEXPR
1489  bitset<_Nb>
1490  operator<<(size_t __position) const _GLIBCXX_NOEXCEPT
1491  { return bitset<_Nb>(*this) <<= __position; }
1492 
1493  _GLIBCXX23_CONSTEXPR
1494  bitset<_Nb>
1495  operator>>(size_t __position) const _GLIBCXX_NOEXCEPT
1496  { return bitset<_Nb>(*this) >>= __position; }
1497  ///@}
1498 
1499  /**
1500  * @brief Finds the index of the first "on" bit.
1501  * @return The index of the first bit set, or size() if not found.
1502  * @ingroup SGIextensions
1503  * @sa _Find_next
1504  */
1505  _GLIBCXX23_CONSTEXPR
1506  size_t
1507  _Find_first() const _GLIBCXX_NOEXCEPT
1508  { return this->_M_do_find_first(_Nb); }
1509 
1510  /**
1511  * @brief Finds the index of the next "on" bit after prev.
1512  * @return The index of the next bit set, or size() if not found.
1513  * @param __prev Where to start searching.
1514  * @ingroup SGIextensions
1515  * @sa _Find_first
1516  */
1517  _GLIBCXX23_CONSTEXPR
1518  size_t
1519  _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT
1520  { return this->_M_do_find_next(__prev, _Nb); }
1521 
1522  private:
1523  // Helper functions for string operations.
1524  template<class _CharT, class _Traits>
1525  _GLIBCXX23_CONSTEXPR
1526  void
1527  _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
1528  _CharT, _CharT);
1529 
1530 #if _GLIBCXX_HOSTED
1531  template<class _CharT, class _Traits, class _Alloc>
1532  _GLIBCXX23_CONSTEXPR
1533  void
1534  _M_copy_from_string(const std::basic_string<_CharT,
1535  _Traits, _Alloc>& __s, size_t __pos, size_t __n,
1536  _CharT __zero, _CharT __one)
1537  { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n,
1538  __zero, __one); }
1539 
1540  template<class _CharT, class _Traits, class _Alloc>
1541  _GLIBCXX23_CONSTEXPR
1542  void
1543  _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&,
1544  _CharT, _CharT) const;
1545 
1546  template<class _CharT, class _Traits, size_t _Nb2>
1547  friend std::basic_istream<_CharT, _Traits>&
1548  operator>>(std::basic_istream<_CharT, _Traits>&, bitset<_Nb2>&);
1549 
1550  template <class _CharT, class _Traits, size_t _Nb2>
1551  friend std::basic_ostream<_CharT, _Traits>&
1552  operator<<(std::basic_ostream<_CharT, _Traits>&, const bitset<_Nb2>&);
1553 #endif
1554  };
1555 
1556  // Definitions of non-inline member functions.
1557  template<size_t _Nb>
1558  template<class _CharT, class _Traits>
1559  _GLIBCXX23_CONSTEXPR
1560  void
1561  bitset<_Nb>::
1562  _M_copy_from_ptr(const _CharT* __s, size_t __len,
1563  size_t __pos, size_t __n, _CharT __zero, _CharT __one)
1564  {
1565  reset();
1566  const size_t __rlen = std::min(__n, size_t(__len - __pos));
1567  const size_t __nbits = std::min(_Nb, __rlen);
1568  for (size_t __i = __rlen - __nbits; __i > 0; --__i)
1569  {
1570  const _CharT __c = __s[__pos + __rlen - __i];
1571  if (!_Traits::eq(__c, __zero) && !_Traits::eq(__c, __one))
1572  __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
1573  }
1574  for (size_t __i = __nbits; __i > 0; --__i)
1575  {
1576  const _CharT __c = __s[__pos + __nbits - __i];
1577  if (_Traits::eq(__c, __zero))
1578  ;
1579  else if (_Traits::eq(__c, __one))
1580  _Unchecked_set(__i - 1);
1581  else
1582  __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
1583  }
1584  }
1585 
1586 #if _GLIBCXX_HOSTED
1587  template<size_t _Nb>
1588  template<class _CharT, class _Traits, class _Alloc>
1589  _GLIBCXX23_CONSTEXPR
1590  void
1591  bitset<_Nb>::
1592  _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s,
1593  _CharT __zero, _CharT __one) const
1594  {
1595  __s.assign(_Nb, __zero);
1596  size_t __n = this->_Find_first();
1597  while (__n < _Nb)
1598  {
1599  __s[_Nb - __n - 1] = __one;
1600  __n = _Find_next(__n);
1601  }
1602  }
1603 #endif // HOSTED
1604 
1605  // 23.3.5.3 bitset operations:
1606  ///@{
1607  /**
1608  * @brief Global bitwise operations on bitsets.
1609  * @param __x A bitset.
1610  * @param __y A bitset of the same size as @a __x.
1611  * @return A new bitset.
1612  *
1613  * These should be self-explanatory.
1614  */
1615  template<size_t _Nb>
1616  _GLIBCXX23_CONSTEXPR
1617  inline bitset<_Nb>
1618  operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1619  {
1620  bitset<_Nb> __result(__x);
1621  __result &= __y;
1622  return __result;
1623  }
1624 
1625  template<size_t _Nb>
1626  _GLIBCXX23_CONSTEXPR
1627  inline bitset<_Nb>
1628  operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1629  {
1630  bitset<_Nb> __result(__x);
1631  __result |= __y;
1632  return __result;
1633  }
1634 
1635  template <size_t _Nb>
1636  _GLIBCXX23_CONSTEXPR
1637  inline bitset<_Nb>
1638  operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1639  {
1640  bitset<_Nb> __result(__x);
1641  __result ^= __y;
1642  return __result;
1643  }
1644  ///@}
1645 
1646 #if _GLIBCXX_HOSTED
1647  ///@{
1648  /**
1649  * @brief Global I/O operators for bitsets.
1650  *
1651  * Direct I/O between streams and bitsets is supported. Output is
1652  * straightforward. Input will skip whitespace, only accept @a 0 and @a 1
1653  * characters, and will only extract as many digits as the %bitset will
1654  * hold.
1655  */
1656  template<class _CharT, class _Traits, size_t _Nb>
1657  std::basic_istream<_CharT, _Traits>&
1658  operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
1659  {
1660  typedef typename _Traits::char_type char_type;
1661  typedef std::basic_istream<_CharT, _Traits> __istream_type;
1662  typedef typename __istream_type::ios_base __ios_base;
1663 
1664 #pragma GCC diagnostic push
1665 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1666  struct _Buffer
1667  {
1668  static _GLIBCXX_CONSTEXPR bool _S_use_alloca() { return _Nb <= 256; }
1669 
1670  explicit _Buffer(_CharT* __p) : _M_ptr(__p) { }
1671 
1672  ~_Buffer()
1673  {
1674  if _GLIBCXX_CONSTEXPR (!_S_use_alloca())
1675  delete[] _M_ptr;
1676  }
1677 
1678  _CharT* const _M_ptr;
1679  };
1680  _CharT* __ptr;
1681  if _GLIBCXX_CONSTEXPR (_Buffer::_S_use_alloca())
1682  __ptr = (_CharT*)__builtin_alloca(_Nb);
1683  else
1684  __ptr = new _CharT[_Nb];
1685  const _Buffer __buf(__ptr);
1686 #pragma GCC diagnostic pop
1687 
1688  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1689  // 303. Bitset input operator underspecified
1690  const char_type __zero = __is.widen('0');
1691  const char_type __one = __is.widen('1');
1692 
1693  typename __ios_base::iostate __state = __ios_base::goodbit;
1694  typename __istream_type::sentry __sentry(__is);
1695  if (__sentry)
1696  {
1697  __try
1698  {
1699  for (size_t __i = _Nb; __i > 0; --__i)
1700  {
1701  static typename _Traits::int_type __eof = _Traits::eof();
1702 
1703  typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
1704  if (_Traits::eq_int_type(__c1, __eof))
1705  {
1706  __state |= __ios_base::eofbit;
1707  break;
1708  }
1709  else
1710  {
1711  const char_type __c2 = _Traits::to_char_type(__c1);
1712  if (_Traits::eq(__c2, __zero))
1713  *__ptr++ = __zero;
1714  else if (_Traits::eq(__c2, __one))
1715  *__ptr++ = __one;
1716  else if (_Traits::
1717  eq_int_type(__is.rdbuf()->sputbackc(__c2),
1718  __eof))
1719  {
1720  __state |= __ios_base::failbit;
1721  break;
1722  }
1723  }
1724  }
1725  }
1726  __catch(__cxxabiv1::__forced_unwind&)
1727  {
1728  __is._M_setstate(__ios_base::badbit);
1729  __throw_exception_again;
1730  }
1731  __catch(...)
1732  { __is._M_setstate(__ios_base::badbit); }
1733  }
1734 
1735 #pragma GCC diagnostic push
1736 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1737  if _GLIBCXX_CONSTEXPR (_Nb)
1738  {
1739  if (size_t __len = __ptr - __buf._M_ptr)
1740  __x.template _M_copy_from_ptr<_CharT, _Traits>(__buf._M_ptr, __len,
1741  0, __len,
1742  __zero, __one);
1743  else
1744  __state |= __ios_base::failbit;
1745  }
1746 #pragma GCC diagnostic pop
1747  if (__state)
1748  __is.setstate(__state);
1749  return __is;
1750  }
1751 
1752  template <class _CharT, class _Traits, size_t _Nb>
1753  std::basic_ostream<_CharT, _Traits>&
1754  operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1755  const bitset<_Nb>& __x)
1756  {
1757  std::basic_string<_CharT, _Traits> __tmp;
1758 
1759  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1760  // 396. what are characters zero and one.
1761  const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
1762  __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1763  return __os << __tmp;
1764  }
1765  ///@}
1766 #endif // HOSTED
1767 
1768 _GLIBCXX_END_NAMESPACE_CONTAINER
1769 } // namespace std
1770 
1771 #undef _GLIBCXX_BITSET_WORDS
1772 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1773 #undef _GLIBCXX_BITSET_BITS_PER_ULL
1774 
1775 #if __cplusplus >= 201103L
1776 
1777 namespace std _GLIBCXX_VISIBILITY(default)
1778 {
1779 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1780 
1781  // DR 1182.
1782  /// std::hash specialization for bitset.
1783  template<size_t _Nb>
1784  struct hash<_GLIBCXX_STD_C::bitset<_Nb>>
1785  : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>>
1786  {
1787  size_t
1788  operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept
1789  {
1790  const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__;
1791  return std::_Hash_impl::hash(__b._M_getdata(), __clength);
1792  }
1793  };
1794 
1795  template<>
1796  struct hash<_GLIBCXX_STD_C::bitset<0>>
1797  : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>>
1798  {
1799  size_t
1800  operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept
1801  { return 0; }
1802  };
1803 
1804 _GLIBCXX_END_NAMESPACE_VERSION
1805 } // namespace
1806 
1807 #endif // C++11
1808 
1809 #if defined _GLIBCXX_DEBUG && _GLIBCXX_HOSTED
1810 # include <debug/bitset>
1811 #endif
1812 
1813 #endif /* _GLIBCXX_BITSET */
Generated by doxygen 1.9.1