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
73namespace 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>
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 */
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
968 size_t __position = 0)
969 : _Base()
970 {
971 _M_check_initial_position(__s, __position);
972 _M_copy_from_string(__s, __position,
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
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
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
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
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
1053 operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
1054 {
1055 this->_M_do_and(__rhs);
1056 return *this;
1057 }
1058
1059 _GLIBCXX23_CONSTEXPR
1061 operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
1062 {
1063 this->_M_do_or(__rhs);
1064 return *this;
1065 }
1066
1067 _GLIBCXX23_CONSTEXPR
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
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
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
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
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
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
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
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
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
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
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
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
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
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
1296 {
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
1307 to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1308 {
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
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
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
1335 to_string() const
1336 {
1337 return to_string<_CharT, std::char_traits<_CharT>,
1339 }
1340
1341 template<class _CharT>
1342 _GLIBCXX23_CONSTEXPR
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
1353 to_string() const
1354 {
1355 return to_string<char, std::char_traits<char>,
1357 }
1358
1359 _GLIBCXX23_CONSTEXPR
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
1441 operator<<(size_t __position) const _GLIBCXX_NOEXCEPT
1442 { return bitset<_Nb>(*this) <<= __position; }
1443
1444 _GLIBCXX23_CONSTEXPR
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
1495 _CharT, _CharT) const;
1496
1497 template<class _CharT, class _Traits, size_t _Nb2>
1500
1501 template <class _CharT, class _Traits, size_t _Nb2>
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>
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 }
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>
1693 const bitset<_Nb>& __x)
1694 {
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
1715namespace 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 */
constexpr bitset< _Nb > & _Unchecked_reset(size_t __pos) noexcept
Definition bitset:1136
constexpr bitset< _Nb > & _Unchecked_flip(size_t __pos) noexcept
Definition bitset:1144
constexpr size_t _Find_first() const noexcept
Finds the index of the first "on" bit.
Definition bitset:1458
constexpr bool _Unchecked_test(size_t __pos) const noexcept
Definition bitset:1151
constexpr bitset< _Nb > & _Unchecked_set(size_t __pos) noexcept
Definition bitset:1117
constexpr bitset< _Nb > & _Unchecked_set(size_t __pos, int __val) noexcept
Definition bitset:1125
constexpr size_t _Find_next(size_t __prev) const noexcept
Finds the index of the next "on" bit after prev.
Definition bitset:1470
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.
constexpr bitset< _Nb > operator^(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition bitset:1582
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition bitset:1602
std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &__os, const bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition bitset:1692
constexpr bitset< _Nb > operator|(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition bitset:1572
constexpr bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition bitset:1562
_WordT _M_w[_Nw]
0 is the least significant word.
Definition bitset:89
The bitset class represents a fixed-size sequence of bits.
Definition bitset:814
constexpr reference operator[](size_t __position)
Array-indexing support.
Definition bitset:1257
constexpr bitset< _Nb > & operator>>=(size_t __position) noexcept
Definition bitset:1099
constexpr bitset< _Nb > & flip() noexcept
Toggles every bit to its opposite value.
Definition bitset:1214
constexpr bitset< _Nb > & operator&=(const bitset< _Nb > &__rhs) noexcept
Definition bitset:1053
constexpr bitset< _Nb > operator>>(size_t __position) const noexcept
Self-explanatory.
Definition bitset:1446
constexpr unsigned long to_ulong() const
Returns a numerical interpretation of the bitset.
Definition bitset:1273
constexpr bool any() const noexcept
Tests whether any of the bits are on.
Definition bitset:1425
constexpr bitset() noexcept
All bits set to zero.
Definition bitset:941
constexpr bitset< _Nb > & operator^=(const bitset< _Nb > &__rhs) noexcept
Definition bitset:1069
constexpr bool test(size_t __position) const
Tests the value of a bit.
Definition bitset:1402
constexpr bitset< _Nb > operator~() const noexcept
See the no-argument flip().
Definition bitset:1237
constexpr bitset< _Nb > & operator|=(const bitset< _Nb > &__rhs) noexcept
Definition bitset:1061
constexpr bitset< _Nb > & set(size_t __position, bool __val=true)
Sets a given bit to a particular value.
Definition bitset:1177
constexpr size_t count() const noexcept
Returns the number of bits which are set.
Definition bitset:1371
constexpr std::basic_string< _CharT, _Traits, _Alloc > to_string() const
Returns a character interpretation of the bitset.
Definition bitset:1295
constexpr bitset(const _CharT *__str, typename __bitset::__string< _CharT >::size_type __n=__bitset::__string< _CharT >::npos, _CharT __zero=_CharT('0'), _CharT __one=_CharT('1'))
Definition bitset:1025
constexpr bitset< _Nb > & reset() noexcept
Sets every bit to false.
Definition bitset:1188
constexpr bitset< _Nb > & set() noexcept
Sets every bit to true.
Definition bitset:1162
constexpr bitset(const std::basic_string< _CharT, _Traits, _Alloc > &__s, size_t __position=0)
Definition bitset:967
constexpr bitset(const std::basic_string< _CharT, _Traits, _Alloc > &__s, size_t __position, size_t __n)
Definition bitset:989
constexpr bitset(unsigned long long __val) noexcept
Initial bits bitwise-copied from a single word (others set to zero).
Definition bitset:946
constexpr size_t size() const noexcept
Returns the total number of bits.
Definition bitset:1376
constexpr bool all() const noexcept
Tests whether all the bits are on.
Definition bitset:1416
constexpr bitset< _Nb > & reset(size_t __position)
Sets a given bit to false.
Definition bitset:1203
constexpr bool none() const noexcept
Tests whether any of the bits are on.
Definition bitset:1434
constexpr bool operator==(const bitset< _Nb > &__rhs) const noexcept
These comparisons for equality/inequality are, well, bitwise.
Definition bitset:1383
constexpr bool operator[](size_t __position) const
Array-indexing support.
Definition bitset:1261
constexpr bitset< _Nb > & flip(size_t __position)
Toggles a given bit to its opposite value.
Definition bitset:1228
void setstate(iostate __state)
Sets additional flags in the error state.
Definition basic_ios.h:166
char_type widen(char __c) const
Widens characters.
Definition basic_ios.h:464
basic_streambuf< _CharT, _Traits > * rdbuf() const
Accessing the underlying buffer.
Definition basic_ios.h:337
Template class basic_istream.
Definition istream:63
Template class basic_ostream.
Definition ostream:69
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
Managing sequences of characters and character-like objects.
Definition cow_string.h:109
const _CharT * data() const noexcept
Return const pointer to contents.
basic_string & assign(const basic_string &__str)
Set value to contents of another string.
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
Definition cow_string.h:913
Thrown as part of forced unwinding.
locale getloc() const
Locale access.
Definition ios_base.h:841