43 #ifndef _GLIBCXX_BITSET
44 #define _GLIBCXX_BITSET 1
46 #pragma GCC system_header
53 #include <cxxabi-forced.h>
55 #define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * sizeof(unsigned long))
56 #define _GLIBCXX_BITSET_WORDS(__n) \
57 ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \
58 / _GLIBCXX_BITSET_BITS_PER_WORD)
60 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
71 typedef unsigned long _WordT;
79 _Base_bitset(
unsigned long __val)
86 _S_whichword(
size_t __pos )
87 {
return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
90 _S_whichbyte(
size_t __pos )
91 {
return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
94 _S_whichbit(
size_t __pos )
95 {
return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
98 _S_maskbit(
size_t __pos )
99 {
return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
102 _M_getword(
size_t __pos)
103 {
return _M_w[_S_whichword(__pos)]; }
106 _M_getword(
size_t __pos)
const
107 {
return _M_w[_S_whichword(__pos)]; }
111 {
return _M_w[_Nw - 1]; }
115 {
return _M_w[_Nw - 1]; }
118 _M_do_and(
const _Base_bitset<_Nw>& __x)
120 for (
size_t __i = 0; __i < _Nw; __i++)
121 _M_w[__i] &= __x._M_w[__i];
125 _M_do_or(
const _Base_bitset<_Nw>& __x)
127 for (
size_t __i = 0; __i < _Nw; __i++)
128 _M_w[__i] |= __x._M_w[__i];
132 _M_do_xor(
const _Base_bitset<_Nw>& __x)
134 for (
size_t __i = 0; __i < _Nw; __i++)
135 _M_w[__i] ^= __x._M_w[__i];
139 _M_do_left_shift(
size_t __shift);
142 _M_do_right_shift(
size_t __shift);
147 for (
size_t __i = 0; __i < _Nw; __i++)
148 _M_w[__i] = ~_M_w[__i];
154 for (
size_t __i = 0; __i < _Nw; __i++)
155 _M_w[__i] = ~static_cast<_WordT>(0);
160 { __builtin_memset(_M_w, 0, _Nw *
sizeof(_WordT)); }
163 _M_is_equal(
const _Base_bitset<_Nw>& __x)
const
165 for (
size_t __i = 0; __i < _Nw; ++__i)
166 if (_M_w[__i] != __x._M_w[__i])
172 _M_are_all_aux()
const
174 for (
size_t __i = 0; __i < _Nw - 1; __i++)
175 if (_M_w[__i] != ~static_cast<_WordT>(0))
177 return ((_Nw - 1) * _GLIBCXX_BITSET_BITS_PER_WORD
178 + __builtin_popcountl(_M_hiword()));
184 for (
size_t __i = 0; __i < _Nw; __i++)
185 if (_M_w[__i] != static_cast<_WordT>(0))
194 for (
size_t __i = 0; __i < _Nw; __i++)
195 __result += __builtin_popcountl(_M_w[__i]);
200 _M_do_to_ulong()
const;
204 _M_do_find_first(
size_t __not_found)
const;
208 _M_do_find_next(
size_t __prev,
size_t __not_found)
const;
214 _Base_bitset<_Nw>::_M_do_left_shift(
size_t __shift)
216 if (__builtin_expect(__shift != 0, 1))
218 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
219 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
222 for (
size_t __n = _Nw - 1; __n >= __wshift; --__n)
223 _M_w[__n] = _M_w[__n - __wshift];
226 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
228 for (
size_t __n = _Nw - 1; __n > __wshift; --__n)
229 _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
230 | (_M_w[__n - __wshift - 1] >> __sub_offset));
231 _M_w[__wshift] = _M_w[0] << __offset;
234 std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
240 _Base_bitset<_Nw>::_M_do_right_shift(
size_t __shift)
242 if (__builtin_expect(__shift != 0, 1))
244 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
245 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
246 const size_t __limit = _Nw - __wshift - 1;
249 for (
size_t __n = 0; __n <= __limit; ++__n)
250 _M_w[__n] = _M_w[__n + __wshift];
253 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
255 for (
size_t __n = 0; __n < __limit; ++__n)
256 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
257 | (_M_w[__n + __wshift + 1] << __sub_offset));
258 _M_w[__limit] = _M_w[_Nw-1] >> __offset;
261 std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
267 _Base_bitset<_Nw>::_M_do_to_ulong()
const
269 for (
size_t __i = 1; __i < _Nw; ++__i)
271 __throw_overflow_error(__N(
"_Base_bitset::_M_do_to_ulong"));
277 _Base_bitset<_Nw>::_M_do_find_first(
size_t __not_found)
const
279 for (
size_t __i = 0; __i < _Nw; __i++)
281 _WordT __thisword = _M_w[__i];
282 if (__thisword != static_cast<_WordT>(0))
283 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
284 + __builtin_ctzl(__thisword));
292 _Base_bitset<_Nw>::_M_do_find_next(
size_t __prev,
size_t __not_found)
const
298 if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
302 size_t __i = _S_whichword(__prev);
303 _WordT __thisword = _M_w[__i];
306 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
308 if (__thisword != static_cast<_WordT>(0))
309 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
310 + __builtin_ctzl(__thisword));
314 for (; __i < _Nw; __i++)
316 __thisword = _M_w[__i];
317 if (__thisword != static_cast<_WordT>(0))
318 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
319 + __builtin_ctzl(__thisword));
331 struct _Base_bitset<1>
333 typedef unsigned long _WordT;
340 _Base_bitset(
unsigned long __val)
345 _S_whichword(
size_t __pos )
346 {
return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
349 _S_whichbyte(
size_t __pos )
350 {
return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
353 _S_whichbit(
size_t __pos )
354 {
return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
357 _S_maskbit(
size_t __pos )
358 {
return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
365 _M_getword(
size_t)
const
378 { _M_w &= __x._M_w; }
382 { _M_w |= __x._M_w; }
386 { _M_w ^= __x._M_w; }
389 _M_do_left_shift(
size_t __shift)
390 { _M_w <<= __shift; }
393 _M_do_right_shift(
size_t __shift)
394 { _M_w >>= __shift; }
402 { _M_w = ~static_cast<_WordT>(0); }
410 {
return _M_w == __x._M_w; }
413 _M_are_all_aux()
const
414 {
return __builtin_popcountl(_M_w); }
418 {
return _M_w != 0; }
422 {
return __builtin_popcountl(_M_w); }
425 _M_do_to_ulong()
const
429 _M_do_find_first(
size_t __not_found)
const
432 return __builtin_ctzl(_M_w);
439 _M_do_find_next(
size_t __prev,
size_t __not_found)
const
442 if (__prev >= ((
size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
445 _WordT __x = _M_w >> __prev;
447 return __builtin_ctzl(__x) + __prev;
459 struct _Base_bitset<0>
461 typedef unsigned long _WordT;
466 _Base_bitset(
unsigned long)
470 _S_whichword(
size_t __pos )
471 {
return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
474 _S_whichbyte(
size_t __pos )
475 {
return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
478 _S_whichbit(
size_t __pos )
479 {
return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
482 _S_maskbit(
size_t __pos )
483 {
return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
493 _M_getword(
size_t)
const
495 __throw_out_of_range(__N(
"_Base_bitset::_M_getword"));
516 _M_do_left_shift(
size_t)
520 _M_do_right_shift(
size_t)
543 _M_are_all_aux()
const
555 _M_do_to_ulong()
const
561 _M_do_find_first(
size_t)
const
565 _M_do_find_next(
size_t,
size_t)
const
571 template<
size_t _Extrabits>
574 static void _S_do_sanitize(
unsigned long& __val)
575 { __val &= ~((~static_cast<
unsigned long>(0)) << _Extrabits); }
580 {
static void _S_do_sanitize(
unsigned long) {} };
647 :
private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
651 typedef unsigned long _WordT;
656 _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>::
657 _S_do_sanitize(this->_M_hiword());
686 _M_wp = &__b._M_getword(__pos);
687 _M_bpos = _Base::_S_whichbit(__pos);
698 *_M_wp |= _Base::_S_maskbit(_M_bpos);
700 *_M_wp &= ~
_Base::_S_maskbit(_M_bpos);
708 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
709 *_M_wp |= _Base::_S_maskbit(_M_bpos);
711 *_M_wp &= ~
_Base::_S_maskbit(_M_bpos);
718 {
return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
721 operator bool()
const
722 {
return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
728 *_M_wp ^= _Base::_S_maskbit(_M_bpos);
742 { _M_do_sanitize(); }
753 template<
class _CharT,
class _Traits,
class _Alloc>
756 size_t __position = 0)
759 if (__position > __s.
size())
760 __throw_out_of_range(__N(
"bitset::bitset initial position "
762 _M_copy_from_string(__s, __position,
764 _CharT(
'0'), _CharT(
'1'));
776 template<
class _CharT,
class _Traits,
class _Alloc>
778 size_t __position,
size_t __n)
781 if (__position > __s.
size())
782 __throw_out_of_range(__N(
"bitset::bitset initial position "
784 _M_copy_from_string(__s, __position, __n, _CharT(
'0'), _CharT(
'1'));
789 template<
class _CharT,
class _Traits,
class _Alloc>
791 size_t __position,
size_t __n,
792 _CharT __zero, _CharT __one = _CharT(
'1'))
795 if (__position > __s.
size())
796 __throw_out_of_range(__N(
"bitset::bitset initial position "
798 _M_copy_from_string(__s, __position, __n, __zero, __one);
812 this->_M_do_and(__rhs);
819 this->_M_do_or(__rhs);
826 this->_M_do_xor(__rhs);
839 operator<<=(
size_t __position)
841 if (__builtin_expect(__position < _Nb, 1))
843 this->_M_do_left_shift(__position);
844 this->_M_do_sanitize();
854 if (__builtin_expect(__position < _Nb, 1))
856 this->_M_do_right_shift(__position);
857 this->_M_do_sanitize();
874 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
882 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
884 this->_M_getword(__pos) &= ~
_Base::_S_maskbit(__pos);
891 this->_M_getword(__pos) &= ~
_Base::_S_maskbit(__pos);
898 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
904 {
return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
905 != static_cast<_WordT>(0)); }
916 this->_M_do_sanitize();
927 set(
size_t __position,
bool __val =
true)
929 if (__position >= _Nb)
930 __throw_out_of_range(__N(
"bitset::set"));
931 return _Unchecked_set(__position, __val);
954 if (__position >= _Nb)
955 __throw_out_of_range(__N(
"bitset::reset"));
956 return _Unchecked_reset(__position);
966 this->_M_do_sanitize();
978 if (__position >= _Nb)
979 __throw_out_of_range(__N(
"bitset::flip"));
980 return _Unchecked_flip(__position);
1005 {
return reference(*
this,__position); }
1009 {
return _Unchecked_test(__position); }
1020 {
return this->_M_do_to_ulong(); }
1030 template<
class _CharT,
class _Traits,
class _Alloc>
1035 _M_copy_to_string(__result, _CharT(
'0'), _CharT(
'1'));
1041 template<
class _CharT,
class _Traits,
class _Alloc>
1043 to_string(_CharT __zero, _CharT __one = _CharT(
'1'))
const
1046 _M_copy_to_string(__result, __zero, __one);
1052 template<
class _CharT,
class _Traits>
1055 {
return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
1059 template<
class _CharT,
class _Traits>
1061 to_string(_CharT __zero, _CharT __one = _CharT(
'1'))
const
1062 {
return to_string<_CharT, _Traits,
1065 template<
class _CharT>
1070 return to_string<_CharT, std::char_traits<_CharT>,
1074 template<
class _CharT>
1077 to_string(_CharT __zero, _CharT __one = _CharT(
'1'))
const
1079 return to_string<_CharT, std::char_traits<_CharT>,
1086 return to_string<char, std::char_traits<char>,
1091 to_string(
char __zero,
char __one =
'1')
const
1093 return to_string<char, std::char_traits<char>,
1098 template<
class _CharT,
class _Traits>
1100 _M_copy_from_ptr(
const _CharT*,
size_t,
size_t,
size_t,
1103 template<
class _CharT,
class _Traits,
class _Alloc>
1106 _Traits, _Alloc>& __s,
size_t __pos,
size_t __n,
1107 _CharT __zero, _CharT __one)
1108 { _M_copy_from_ptr<_CharT, _Traits>(__s.
data(), __s.
size(), __pos, __n,
1111 template<
class _CharT,
class _Traits,
class _Alloc>
1114 _CharT, _CharT)
const;
1117 template<
class _CharT,
class _Traits,
class _Alloc>
1120 _Traits, _Alloc>& __s,
size_t __pos,
size_t __n)
1121 { _M_copy_from_string(__s, __pos, __n, _CharT(
'0'), _CharT(
'1')); }
1123 template<
class _CharT,
class _Traits,
class _Alloc>
1126 { _M_copy_to_string(__s, _CharT(
'0'), _CharT(
'1')); }
1131 {
return this->_M_do_count(); }
1142 {
return this->_M_is_equal(__rhs); }
1146 {
return !this->_M_is_equal(__rhs); }
1158 if (__position >= _Nb)
1159 __throw_out_of_range(__N(
"bitset::test"));
1160 return _Unchecked_test(__position);
1171 {
return this->_M_are_all_aux() == _Nb; }
1179 {
return this->_M_is_any(); }
1187 {
return !this->_M_is_any(); }
1208 {
return this->_M_do_find_first(_Nb); }
1219 {
return this->_M_do_find_next(__prev, _Nb); }
1223 template<
size_t _Nb>
1224 template<
class _CharT,
class _Traits>
1227 _M_copy_from_ptr(
const _CharT* __s,
size_t __len,
1228 size_t __pos,
size_t __n, _CharT __zero, _CharT __one)
1232 for (
size_t __i = __nbits; __i > 0; --__i)
1234 const _CharT __c = __s[__pos + __nbits - __i];
1235 if (_Traits::eq(__c, __zero))
1237 else if (_Traits::eq(__c, __one))
1238 _Unchecked_set(__i - 1);
1240 __throw_invalid_argument(__N(
"bitset::_M_copy_from_ptr"));
1244 template<
size_t _Nb>
1245 template<
class _CharT,
class _Traits,
class _Alloc>
1249 _CharT __zero, _CharT __one)
const
1252 for (
size_t __i = _Nb; __i > 0; --__i)
1253 if (_Unchecked_test(__i - 1))
1254 _Traits::assign(__s[_Nb - __i], __one);
1267 template<
size_t _Nb>
1276 template<
size_t _Nb>
1285 template <
size_t _Nb>
1304 template<
class _CharT,
class _Traits,
size_t _Nb>
1308 typedef typename _Traits::char_type char_type;
1310 typedef typename __istream_type::ios_base __ios_base;
1317 const char_type __zero = __is.
widen(
'0');
1318 const char_type __one = __is.
widen(
'1');
1320 typename __ios_base::iostate __state = __ios_base::goodbit;
1321 typename __istream_type::sentry __sentry(__is);
1326 for (
size_t __i = _Nb; __i > 0; --__i)
1328 static typename _Traits::int_type __eof = _Traits::eof();
1330 typename _Traits::int_type __c1 = __is.
rdbuf()->sbumpc();
1331 if (_Traits::eq_int_type(__c1, __eof))
1333 __state |= __ios_base::eofbit;
1338 const char_type __c2 = _Traits::to_char_type(__c1);
1339 if (_Traits::eq(__c2, __zero))
1341 else if (_Traits::eq(__c2, __one))
1344 eq_int_type(__is.
rdbuf()->sputbackc(__c2),
1347 __state |= __ios_base::failbit;
1355 __is._M_setstate(__ios_base::badbit);
1356 __throw_exception_again;
1359 { __is._M_setstate(__ios_base::badbit); }
1362 if (__tmp.
empty() && _Nb)
1363 __state |= __ios_base::failbit;
1365 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb,
1372 template <
class _CharT,
class _Traits,
size_t _Nb>
1374 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1381 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
1382 __x._M_copy_to_string(__tmp, __ct.
widen(
'0'), __ct.
widen(
'1'));
1383 return __os << __tmp;
1387 _GLIBCXX_END_NESTED_NAMESPACE
1389 #undef _GLIBCXX_BITSET_WORDS
1390 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1392 #ifdef _GLIBCXX_DEBUG
bool none() const
Tests whether any of the bits are on.
size_t _Find_first() const
Finds the index of the first "on" bit.
bitset< _Nb > & reset()
Sets every bit to false.
reference operator[](size_t __position)
Array-indexing support.
basic_string & assign(const basic_string &__str)
Set value to contents of another string.
size_t count() const
Returns the number of bits which are set.
bitset< _Nb > & flip()
Toggles every bit to its opposite value.
bitset< _Nb > & operator|=(const bitset< _Nb > &__rhs)
Operations on bitsets.
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, bitset< _Nb > &__x)
Global I/O operators for bitsets.
bitset< _Nb > & operator>>=(size_t __position)
Operations on bitsets.
bitset< _Nb > operator^(const bitset< _Nb > &__x, const bitset< _Nb > &__y)
Global bitwise operations on bitsets.
bitset(const std::basic_string< _CharT, _Traits, _Alloc > &__s, size_t __position, size_t __n)
Use a subset of a string.
bitset(const std::basic_string< _CharT, _Traits, _Alloc > &__s, size_t __position=0)
Use a subset of a string.
bool operator!=(const bitset< _Nb > &__rhs) const
These comparisons for equality/inequality are, well, bitwise.
bitset< _Nb > & _Unchecked_set(size_t __pos, int __val)
void reserve(size_type __res_arg=0)
Attempt to preallocate enough memory for specified number of characters.
size_t size() const
Returns the total number of bits.
The bitset class represents a fixed-size sequence of bits.
unsigned long to_ulong() const
Returns a numerical interpretation of the bitset.
void setstate(iostate __state)
Sets additional flags in the error state.
size_t _Find_next(size_t __prev) const
Finds the index of the next "on" bit after prev.
char_type widen(char __c) const
Widens characters.
bool any() const
Tests whether any of the bits are on.
bitset< _Nb > operator~() const
See the no-argument flip().
const _CharT * data() const
Return const pointer to contents.
bitset< _Nb > operator|(const bitset< _Nb > &__x, const bitset< _Nb > &__y)
Global bitwise operations on bitsets.
bitset< _Nb > & reset(size_t __position)
Sets a given bit to false.
Thrown as part of forced unwinding.A magic placeholder class that can be caught by reference to recog...
The "standard" allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manu...
bitset< _Nb > & _Unchecked_set(size_t __pos)
bool operator==(const bitset< _Nb > &__rhs) const
These comparisons for equality/inequality are, well, bitwise.
bitset< _Nb > & flip(size_t __position)
Toggles a given bit to its opposite value.
size_type size() const
Returns the number of characters in the string, not including any null-termination.
bool _Unchecked_test(size_t __pos) const
char_type widen(char __c) const
Widen char to char_type.
bitset< _Nb > & _Unchecked_reset(size_t __pos)
bitset< _Nb > & set(size_t __position, bool __val=true)
Sets a given bit to a particular value.
Controlling output.This is the base class for all output streams. It provides text formatting of all ...
bool all() const
Tests whether all the bits are on.
void push_back(_CharT __c)
Append a single character.
bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y)
Global bitwise operations on bitsets.
bitset< _Nb > & _Unchecked_flip(size_t __pos)
bool test(size_t __position) const
Tests the value of a bit.
basic_streambuf< _CharT, _Traits > * rdbuf() const
Accessing the underlying buffer.
const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
bitset(unsigned long __val)
Initial bits bitwise-copied from a single word (others set to zero).
bitset< _Nb > & set()
Sets every bit to true.
bool operator[](size_t __position) const
Array-indexing support.
bitset()
All bits set to zero.
std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &__os, const bitset< _Nb > &__x)
Global I/O operators for bitsets.
bitset< _Nb > & operator&=(const bitset< _Nb > &__rhs)
Operations on bitsets.
bitset< _Nb > & operator^=(const bitset< _Nb > &__rhs)
Operations on bitsets.
Controlling input.This is the base class for all input streams. It provides text formatting of all bu...
bitset< _Nb > operator>>(size_t __position) const
Self-explanatory.
Managing sequences of characters and character-like objects.
std::basic_string< _CharT, _Traits, _Alloc > to_string() const
Returns a character interpretation of the bitset.