bitset source code [include/c++/7/bitset]

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