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