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

source code of include/c++/13/bitset