libstdc++
bitset
Go to the documentation of this file.
1// <bitset> -*- C++ -*-
2
3// Copyright (C) 2001-2024 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_want_constexpr_bitset
62#include <bits/version.h>
63
64#define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * __SIZEOF_LONG__)
65#define _GLIBCXX_BITSET_WORDS(__n) \
66 ((__n) / _GLIBCXX_BITSET_BITS_PER_WORD + \
67 ((__n) % _GLIBCXX_BITSET_BITS_PER_WORD == 0 ? 0 : 1))
68
69#define _GLIBCXX_BITSET_BITS_PER_ULL (__CHAR_BIT__ * __SIZEOF_LONG_LONG__)
70
71namespace std _GLIBCXX_VISIBILITY(default)
72{
73_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
74
75 /**
76 * Base class, general case. It is a class invariant that _Nw will be
77 * nonnegative.
78 *
79 * See documentation for bitset.
80 */
81 template<size_t _Nw>
83 {
84 typedef unsigned long _WordT;
85
86 /// 0 is the least significant word.
87 _WordT _M_w[_Nw];
88
89 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
90 : _M_w() { }
91
92#if __cplusplus >= 201103L
93 constexpr _Base_bitset(unsigned long long __val) noexcept
94 : _M_w{ _WordT(__val)
95#if __SIZEOF_LONG_LONG__ > __SIZEOF_LONG__
96 , _WordT(__val >> _GLIBCXX_BITSET_BITS_PER_WORD)
97#endif
98 } { }
99#else
100 _Base_bitset(unsigned long __val)
101 : _M_w()
102 { _M_w[0] = __val; }
103#endif
104
105 static _GLIBCXX_CONSTEXPR size_t
106 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
107 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
108
109 static _GLIBCXX_CONSTEXPR size_t
110 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
111 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
112
113 static _GLIBCXX_CONSTEXPR size_t
114 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
115 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
116
117 static _GLIBCXX_CONSTEXPR _WordT
118 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
119 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
120
121 _GLIBCXX14_CONSTEXPR _WordT&
122 _M_getword(size_t __pos) _GLIBCXX_NOEXCEPT
123 { return _M_w[_S_whichword(__pos)]; }
124
125 _GLIBCXX_CONSTEXPR _WordT
126 _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT
127 { return _M_w[_S_whichword(__pos)]; }
128
129#if __cplusplus >= 201103L
130 constexpr const _WordT*
131 _M_getdata() const noexcept
132 { return _M_w; }
133#endif
134
135 _GLIBCXX23_CONSTEXPR _WordT&
136 _M_hiword() _GLIBCXX_NOEXCEPT
137 { return _M_w[_Nw - 1]; }
138
139 _GLIBCXX_CONSTEXPR _WordT
140 _M_hiword() const _GLIBCXX_NOEXCEPT
141 { return _M_w[_Nw - 1]; }
142
143 _GLIBCXX23_CONSTEXPR void
144 _M_do_and(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
145 {
146 for (size_t __i = 0; __i < _Nw; __i++)
147 _M_w[__i] &= __x._M_w[__i];
148 }
149
150 _GLIBCXX14_CONSTEXPR void
151 _M_do_or(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
152 {
153 for (size_t __i = 0; __i < _Nw; __i++)
154 _M_w[__i] |= __x._M_w[__i];
155 }
156
157 _GLIBCXX14_CONSTEXPR void
158 _M_do_xor(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
159 {
160 for (size_t __i = 0; __i < _Nw; __i++)
161 _M_w[__i] ^= __x._M_w[__i];
162 }
163
164 _GLIBCXX14_CONSTEXPR void
165 _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT;
166
167 _GLIBCXX14_CONSTEXPR void
168 _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT;
169
170 _GLIBCXX14_CONSTEXPR void
171 _M_do_flip() _GLIBCXX_NOEXCEPT
172 {
173 for (size_t __i = 0; __i < _Nw; __i++)
174 _M_w[__i] = ~_M_w[__i];
175 }
176
177 _GLIBCXX14_CONSTEXPR void
178 _M_do_set() _GLIBCXX_NOEXCEPT
179 {
180 for (size_t __i = 0; __i < _Nw; __i++)
181 _M_w[__i] = ~static_cast<_WordT>(0);
182 }
183
184 _GLIBCXX14_CONSTEXPR void
185 _M_do_reset() _GLIBCXX_NOEXCEPT
186 {
187#if __cplusplus >= 201402L
188 if (__builtin_is_constant_evaluated())
189 {
190 for (_WordT& __w : _M_w)
191 __w = 0;
192 return;
193 }
194#endif
195 __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT));
196 }
197
198 _GLIBCXX14_CONSTEXPR bool
199 _M_is_equal(const _Base_bitset<_Nw>& __x) const _GLIBCXX_NOEXCEPT
200 {
201 for (size_t __i = 0; __i < _Nw; ++__i)
202 if (_M_w[__i] != __x._M_w[__i])
203 return false;
204 return true;
205 }
206
207 template<size_t _Nb>
208 _GLIBCXX14_CONSTEXPR bool
209 _M_are_all() const _GLIBCXX_NOEXCEPT
210 {
211 for (size_t __i = 0; __i < _Nw - 1; __i++)
212 if (_M_w[__i] != ~static_cast<_WordT>(0))
213 return false;
214 return _M_hiword() == (~static_cast<_WordT>(0)
215 >> (_Nw * _GLIBCXX_BITSET_BITS_PER_WORD
216 - _Nb));
217 }
218
219 _GLIBCXX14_CONSTEXPR bool
220 _M_is_any() const _GLIBCXX_NOEXCEPT
221 {
222 for (size_t __i = 0; __i < _Nw; __i++)
223 if (_M_w[__i] != static_cast<_WordT>(0))
224 return true;
225 return false;
226 }
227
228 _GLIBCXX14_CONSTEXPR size_t
229 _M_do_count() const _GLIBCXX_NOEXCEPT
230 {
231 size_t __result = 0;
232 for (size_t __i = 0; __i < _Nw; __i++)
233 __result += __builtin_popcountl(_M_w[__i]);
234 return __result;
235 }
236
237 _GLIBCXX14_CONSTEXPR unsigned long
238 _M_do_to_ulong() const;
239
240#if __cplusplus >= 201103L
241 _GLIBCXX14_CONSTEXPR unsigned long long
242 _M_do_to_ullong() const;
243#endif
244
245 // find first "on" bit
246 _GLIBCXX14_CONSTEXPR size_t
247 _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT;
248
249 // find the next "on" bit that follows "prev"
250 _GLIBCXX14_CONSTEXPR size_t
251 _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT;
252 };
253
254 // Definitions of non-inline functions from _Base_bitset.
255 template<size_t _Nw>
256 _GLIBCXX14_CONSTEXPR void
257 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT
258 {
259 if (__builtin_expect(__shift != 0, 1))
260 {
261 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
262 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
263
264 if (__offset == 0)
265 for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
266 _M_w[__n] = _M_w[__n - __wshift];
267 else
268 {
269 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
270 - __offset);
271 for (size_t __n = _Nw - 1; __n > __wshift; --__n)
272 _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
273 | (_M_w[__n - __wshift - 1] >> __sub_offset));
274 _M_w[__wshift] = _M_w[0] << __offset;
275 }
276
277 std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
278 }
279 }
280
281 template<size_t _Nw>
282 _GLIBCXX14_CONSTEXPR void
283 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT
284 {
285 if (__builtin_expect(__shift != 0, 1))
286 {
287 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
288 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
289 const size_t __limit = _Nw - __wshift - 1;
290
291 if (__offset == 0)
292 for (size_t __n = 0; __n <= __limit; ++__n)
293 _M_w[__n] = _M_w[__n + __wshift];
294 else
295 {
296 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
297 - __offset);
298 for (size_t __n = 0; __n < __limit; ++__n)
299 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
300 | (_M_w[__n + __wshift + 1] << __sub_offset));
301 _M_w[__limit] = _M_w[_Nw-1] >> __offset;
302 }
303
304 std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
305 }
306 }
307
308 template<size_t _Nw>
309 _GLIBCXX14_CONSTEXPR unsigned long
310 _Base_bitset<_Nw>::_M_do_to_ulong() const
311 {
312 for (size_t __i = 1; __i < _Nw; ++__i)
313 if (_M_w[__i])
314 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong"));
315 return _M_w[0];
316 }
317
318#if __cplusplus >= 201103L
319 template<size_t _Nw>
320 _GLIBCXX14_CONSTEXPR unsigned long long
321 _Base_bitset<_Nw>::_M_do_to_ullong() const
322 {
323#if __SIZEOF_LONG_LONG__ == __SIZEOF_LONG__
324 return _M_do_to_ulong();
325#else
326 for (size_t __i = 2; __i < _Nw; ++__i)
327 if (_M_w[__i])
328 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong"));
329
330 return _M_w[0] + (static_cast<unsigned long long>(_M_w[1])
331 << _GLIBCXX_BITSET_BITS_PER_WORD);
332#endif
333 }
334#endif // C++11
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(__prev);
366 _WordT __thisword = _M_w[__i];
367
368 // mask off bits below bound
369 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__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 */
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
956 size_t __position = 0)
957 : _Base()
958 {
959 _M_check_initial_position(__s, __position);
960 _M_copy_from_string(__s, __position,
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
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
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
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
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
1041 operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
1042 {
1043 this->_M_do_and(__rhs);
1044 return *this;
1045 }
1046
1047 _GLIBCXX23_CONSTEXPR
1049 operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
1050 {
1051 this->_M_do_or(__rhs);
1052 return *this;
1053 }
1054
1055 _GLIBCXX23_CONSTEXPR
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
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
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
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
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
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
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
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
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
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
1194 reset(size_t __position)
1195 {
1196 this->_M_check(__position, __N("bitset::reset"));
1197 return _Unchecked_reset(__position);
1198 }
1199
1200 /**
1201 * @brief Toggles every bit to its opposite value.
1202 */
1203 _GLIBCXX23_CONSTEXPR
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
1219 flip(size_t __position)
1220 {
1221 this->_M_check(__position, __N("bitset::flip"));
1222 return _Unchecked_flip(__position);
1223 }
1224
1225 /// See the no-argument flip().
1226 _GLIBCXX23_CONSTEXPR
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(__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
1287 {
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
1298 to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1299 {
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
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
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
1326 to_string() const
1327 {
1328 return to_string<_CharT, std::char_traits<_CharT>,
1330 }
1331
1332 template<class _CharT>
1333 _GLIBCXX23_CONSTEXPR
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
1344 to_string() const
1345 {
1346 return to_string<char, std::char_traits<char>,
1348 }
1349
1350 _GLIBCXX23_CONSTEXPR
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(__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
1432 operator<<(size_t __position) const _GLIBCXX_NOEXCEPT
1433 { return bitset<_Nb>(*this) <<= __position; }
1434
1435 _GLIBCXX23_CONSTEXPR
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
1486 _CharT, _CharT) const;
1487
1488 template<class _CharT, class _Traits, size_t _Nb2>
1491
1492 template <class _CharT, class _Traits, size_t _Nb2>
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(_Nb, std::min(__n, 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(__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>
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 }
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>
1684 const bitset<_Nb>& __x)
1685 {
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 */
constexpr bitset< _Nb > & _Unchecked_reset(size_t __pos) noexcept
Definition bitset:1127
constexpr bitset< _Nb > & _Unchecked_flip(size_t __pos) noexcept
Definition bitset:1135
constexpr size_t _Find_first() const noexcept
Finds the index of the first "on" bit.
Definition bitset:1449
constexpr bool _Unchecked_test(size_t __pos) const noexcept
Definition bitset:1142
constexpr bitset< _Nb > & _Unchecked_set(size_t __pos) noexcept
Definition bitset:1108
constexpr bitset< _Nb > & _Unchecked_set(size_t __pos, int __val) noexcept
Definition bitset:1116
constexpr size_t _Find_next(size_t __prev) const noexcept
Finds the index of the next "on" bit after prev.
Definition bitset:1461
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:1573
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition bitset:1593
std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &__os, const bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition bitset:1683
constexpr bitset< _Nb > operator|(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition bitset:1563
constexpr bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition bitset:1553
_WordT _M_w[_Nw]
0 is the least significant word.
Definition bitset:87
The bitset class represents a fixed-size sequence of bits.
Definition bitset:799
constexpr reference operator[](size_t __position)
Array-indexing support.
Definition bitset:1248
constexpr bitset< _Nb > & operator>>=(size_t __position) noexcept
Definition bitset:1087
constexpr bitset< _Nb > & flip() noexcept
Toggles every bit to its opposite value.
Definition bitset:1205
constexpr bitset< _Nb > & operator&=(const bitset< _Nb > &__rhs) noexcept
Definition bitset:1041
constexpr bitset< _Nb > operator>>(size_t __position) const noexcept
Self-explanatory.
Definition bitset:1437
constexpr unsigned long to_ulong() const
Returns a numerical interpretation of the bitset.
Definition bitset:1264
constexpr bool any() const noexcept
Tests whether any of the bits are on.
Definition bitset:1416
constexpr bitset() noexcept
All bits set to zero.
Definition bitset:929
constexpr bitset< _Nb > & operator^=(const bitset< _Nb > &__rhs) noexcept
Definition bitset:1057
constexpr bool test(size_t __position) const
Tests the value of a bit.
Definition bitset:1393
constexpr bitset< _Nb > operator~() const noexcept
See the no-argument flip().
Definition bitset:1228
constexpr bitset< _Nb > & operator|=(const bitset< _Nb > &__rhs) noexcept
Definition bitset:1049
constexpr bitset< _Nb > & set(size_t __position, bool __val=true)
Sets a given bit to a particular value.
Definition bitset:1168
constexpr size_t count() const noexcept
Returns the number of bits which are set.
Definition bitset:1362
constexpr std::basic_string< _CharT, _Traits, _Alloc > to_string() const
Returns a character interpretation of the bitset.
Definition bitset:1286
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:1013
constexpr bitset< _Nb > & reset() noexcept
Sets every bit to false.
Definition bitset:1179
constexpr bitset< _Nb > & set() noexcept
Sets every bit to true.
Definition bitset:1153
constexpr bitset(const std::basic_string< _CharT, _Traits, _Alloc > &__s, size_t __position=0)
Definition bitset:955
constexpr bitset(const std::basic_string< _CharT, _Traits, _Alloc > &__s, size_t __position, size_t __n)
Definition bitset:977
constexpr bitset(unsigned long long __val) noexcept
Initial bits bitwise-copied from a single word (others set to zero).
Definition bitset:934
constexpr size_t size() const noexcept
Returns the total number of bits.
Definition bitset:1367
constexpr bool all() const noexcept
Tests whether all the bits are on.
Definition bitset:1407
constexpr bitset< _Nb > & reset(size_t __position)
Sets a given bit to false.
Definition bitset:1194
constexpr bool none() const noexcept
Tests whether any of the bits are on.
Definition bitset:1425
constexpr bool operator==(const bitset< _Nb > &__rhs) const noexcept
These comparisons for equality/inequality are, well, bitwise.
Definition bitset:1374
constexpr bool operator[](size_t __position) const
Array-indexing support.
Definition bitset:1252
constexpr bitset< _Nb > & flip(size_t __position)
Toggles a given bit to its opposite value.
Definition bitset:1219
void setstate(iostate __state)
Sets additional flags in the error state.
Definition basic_ios.h:161
char_type widen(char __c) const
Widens characters.
Definition basic_ios.h:453
basic_streambuf< _CharT, _Traits > * rdbuf() const
Accessing the underlying buffer.
Definition basic_ios.h:325
Template class basic_istream.
Definition istream:61
Template class basic_ostream.
Definition ostream:67
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:129
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:908
Thrown as part of forced unwinding.
locale getloc() const
Locale access.
Definition ios_base.h:805