libstdc++
bitset
Go to the documentation of this file.
00001 // <bitset> -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  * Copyright (c) 1998
00027  * Silicon Graphics Computer Systems, Inc.
00028  *
00029  * Permission to use, copy, modify, distribute and sell this software
00030  * and its documentation for any purpose is hereby granted without fee,
00031  * provided that the above copyright notice appear in all copies and
00032  * that both that copyright notice and this permission notice appear
00033  * in supporting documentation.  Silicon Graphics makes no
00034  * representations about the suitability of this software for any
00035  * purpose.  It is provided "as is" without express or implied warranty.
00036  */
00037 
00038 /** @file include/bitset
00039  *  This is a Standard C++ Library header.
00040  */
00041 
00042 #ifndef _GLIBCXX_BITSET
00043 #define _GLIBCXX_BITSET 1
00044 
00045 #pragma GCC system_header
00046 
00047 #include <string>
00048 #include <bits/functexcept.h>   // For invalid_argument, out_of_range,
00049                                 // overflow_error
00050 #include <iosfwd>
00051 #include <bits/cxxabi_forced.h>
00052 
00053 #define _GLIBCXX_BITSET_BITS_PER_WORD  (__CHAR_BIT__ * __SIZEOF_LONG__)
00054 #define _GLIBCXX_BITSET_WORDS(__n) \
00055   ((__n) / _GLIBCXX_BITSET_BITS_PER_WORD + \
00056    ((__n) % _GLIBCXX_BITSET_BITS_PER_WORD == 0 ? 0 : 1))
00057 
00058 #define _GLIBCXX_BITSET_BITS_PER_ULL (__CHAR_BIT__ * __SIZEOF_LONG_LONG__)
00059 
00060 namespace std _GLIBCXX_VISIBILITY(default)
00061 {
00062 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00063 
00064   /**
00065    *  Base class, general case.  It is a class invariant that _Nw will be
00066    *  nonnegative.
00067    *
00068    *  See documentation for bitset.
00069   */
00070   template<size_t _Nw>
00071     struct _Base_bitset
00072     {
00073       typedef unsigned long _WordT;
00074 
00075       /// 0 is the least significant word.
00076       _WordT            _M_w[_Nw];
00077 
00078       _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
00079       : _M_w() { }
00080 
00081 #if __cplusplus >= 201103L
00082       constexpr _Base_bitset(unsigned long long __val) noexcept
00083       : _M_w{ _WordT(__val)
00084 #if __SIZEOF_LONG_LONG__ > __SIZEOF_LONG__
00085                , _WordT(__val >> _GLIBCXX_BITSET_BITS_PER_WORD)
00086 #endif
00087        } { }
00088 #else
00089       _Base_bitset(unsigned long __val)
00090       : _M_w()
00091       { _M_w[0] = __val; }
00092 #endif
00093 
00094       static _GLIBCXX_CONSTEXPR size_t
00095       _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
00096       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
00097 
00098       static _GLIBCXX_CONSTEXPR size_t
00099       _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
00100       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
00101 
00102       static _GLIBCXX_CONSTEXPR size_t
00103       _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
00104       { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
00105 
00106       static _GLIBCXX_CONSTEXPR _WordT
00107       _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
00108       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00109 
00110       _WordT&
00111       _M_getword(size_t __pos) _GLIBCXX_NOEXCEPT
00112       { return _M_w[_S_whichword(__pos)]; }
00113 
00114       _GLIBCXX_CONSTEXPR _WordT
00115       _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT
00116       { return _M_w[_S_whichword(__pos)]; }
00117 
00118 #if __cplusplus >= 201103L
00119       const _WordT*
00120       _M_getdata() const noexcept
00121       { return _M_w; }
00122 #endif
00123 
00124       _WordT&
00125       _M_hiword() _GLIBCXX_NOEXCEPT
00126       { return _M_w[_Nw - 1]; }
00127 
00128       _GLIBCXX_CONSTEXPR _WordT
00129       _M_hiword() const _GLIBCXX_NOEXCEPT
00130       { return _M_w[_Nw - 1]; }
00131 
00132       void
00133       _M_do_and(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
00134       {
00135         for (size_t __i = 0; __i < _Nw; __i++)
00136           _M_w[__i] &= __x._M_w[__i];
00137       }
00138 
00139       void
00140       _M_do_or(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
00141       {
00142         for (size_t __i = 0; __i < _Nw; __i++)
00143           _M_w[__i] |= __x._M_w[__i];
00144       }
00145 
00146       void
00147       _M_do_xor(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT
00148       {
00149         for (size_t __i = 0; __i < _Nw; __i++)
00150           _M_w[__i] ^= __x._M_w[__i];
00151       }
00152 
00153       void
00154       _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT;
00155 
00156       void
00157       _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT;
00158 
00159       void
00160       _M_do_flip() _GLIBCXX_NOEXCEPT
00161       {
00162         for (size_t __i = 0; __i < _Nw; __i++)
00163           _M_w[__i] = ~_M_w[__i];
00164       }
00165 
00166       void
00167       _M_do_set() _GLIBCXX_NOEXCEPT
00168       {
00169         for (size_t __i = 0; __i < _Nw; __i++)
00170           _M_w[__i] = ~static_cast<_WordT>(0);
00171       }
00172 
00173       void
00174       _M_do_reset() _GLIBCXX_NOEXCEPT
00175       { __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT)); }
00176 
00177       bool
00178       _M_is_equal(const _Base_bitset<_Nw>& __x) const _GLIBCXX_NOEXCEPT
00179       {
00180         for (size_t __i = 0; __i < _Nw; ++__i)
00181           if (_M_w[__i] != __x._M_w[__i])
00182             return false;
00183         return true;
00184       }
00185 
00186       template<size_t _Nb>
00187         bool
00188         _M_are_all() const _GLIBCXX_NOEXCEPT
00189         {
00190           for (size_t __i = 0; __i < _Nw - 1; __i++)
00191             if (_M_w[__i] != ~static_cast<_WordT>(0))
00192               return false;
00193           return _M_hiword() == (~static_cast<_WordT>(0)
00194                                  >> (_Nw * _GLIBCXX_BITSET_BITS_PER_WORD
00195                                      - _Nb));
00196         }
00197 
00198       bool
00199       _M_is_any() const _GLIBCXX_NOEXCEPT
00200       {
00201         for (size_t __i = 0; __i < _Nw; __i++)
00202           if (_M_w[__i] != static_cast<_WordT>(0))
00203             return true;
00204         return false;
00205       }
00206 
00207       size_t
00208       _M_do_count() const _GLIBCXX_NOEXCEPT
00209       {
00210         size_t __result = 0;
00211         for (size_t __i = 0; __i < _Nw; __i++)
00212           __result += __builtin_popcountl(_M_w[__i]);
00213         return __result;
00214       }
00215 
00216       unsigned long
00217       _M_do_to_ulong() const;
00218 
00219 #if __cplusplus >= 201103L
00220       unsigned long long
00221       _M_do_to_ullong() const;
00222 #endif
00223 
00224       // find first "on" bit
00225       size_t
00226       _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT;
00227 
00228       // find the next "on" bit that follows "prev"
00229       size_t
00230       _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT;
00231     };
00232 
00233   // Definitions of non-inline functions from _Base_bitset.
00234   template<size_t _Nw>
00235     void
00236     _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT
00237     {
00238       if (__builtin_expect(__shift != 0, 1))
00239         {
00240           const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
00241           const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
00242 
00243           if (__offset == 0)
00244             for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
00245               _M_w[__n] = _M_w[__n - __wshift];
00246           else
00247             {
00248               const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 
00249                                            - __offset);
00250               for (size_t __n = _Nw - 1; __n > __wshift; --__n)
00251                 _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
00252                              | (_M_w[__n - __wshift - 1] >> __sub_offset));
00253               _M_w[__wshift] = _M_w[0] << __offset;
00254             }
00255 
00256           std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
00257         }
00258     }
00259 
00260   template<size_t _Nw>
00261     void
00262     _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT
00263     {
00264       if (__builtin_expect(__shift != 0, 1))
00265         {
00266           const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
00267           const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
00268           const size_t __limit = _Nw - __wshift - 1;
00269 
00270           if (__offset == 0)
00271             for (size_t __n = 0; __n <= __limit; ++__n)
00272               _M_w[__n] = _M_w[__n + __wshift];
00273           else
00274             {
00275               const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
00276                                            - __offset);
00277               for (size_t __n = 0; __n < __limit; ++__n)
00278                 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
00279                              | (_M_w[__n + __wshift + 1] << __sub_offset));
00280               _M_w[__limit] = _M_w[_Nw-1] >> __offset;
00281             }
00282           
00283           std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
00284         }
00285     }
00286 
00287   template<size_t _Nw>
00288     unsigned long
00289     _Base_bitset<_Nw>::_M_do_to_ulong() const
00290     {
00291       for (size_t __i = 1; __i < _Nw; ++__i)
00292         if (_M_w[__i])
00293           __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong"));
00294       return _M_w[0];
00295     }
00296 
00297 #if __cplusplus >= 201103L
00298   template<size_t _Nw>
00299     unsigned long long
00300     _Base_bitset<_Nw>::_M_do_to_ullong() const
00301     {
00302       const bool __dw = sizeof(unsigned long long) > sizeof(unsigned long);
00303       for (size_t __i = 1 + __dw; __i < _Nw; ++__i)
00304         if (_M_w[__i])
00305           __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong"));
00306 
00307       if (__dw)
00308         return _M_w[0] + (static_cast<unsigned long long>(_M_w[1])
00309                           << _GLIBCXX_BITSET_BITS_PER_WORD);
00310       return _M_w[0];
00311     }
00312 #endif
00313 
00314   template<size_t _Nw>
00315     size_t
00316     _Base_bitset<_Nw>::
00317     _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT
00318     {
00319       for (size_t __i = 0; __i < _Nw; __i++)
00320         {
00321           _WordT __thisword = _M_w[__i];
00322           if (__thisword != static_cast<_WordT>(0))
00323             return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
00324                     + __builtin_ctzl(__thisword));
00325         }
00326       // not found, so return an indication of failure.
00327       return __not_found;
00328     }
00329 
00330   template<size_t _Nw>
00331     size_t
00332     _Base_bitset<_Nw>::
00333     _M_do_find_next(size_t __prev, size_t __not_found) const _GLIBCXX_NOEXCEPT
00334     {
00335       // make bound inclusive
00336       ++__prev;
00337 
00338       // check out of bounds
00339       if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
00340         return __not_found;
00341 
00342       // search first word
00343       size_t __i = _S_whichword(__prev);
00344       _WordT __thisword = _M_w[__i];
00345 
00346       // mask off bits below bound
00347       __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
00348 
00349       if (__thisword != static_cast<_WordT>(0))
00350         return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
00351                 + __builtin_ctzl(__thisword));
00352 
00353       // check subsequent words
00354       __i++;
00355       for (; __i < _Nw; __i++)
00356         {
00357           __thisword = _M_w[__i];
00358           if (__thisword != static_cast<_WordT>(0))
00359             return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
00360                     + __builtin_ctzl(__thisword));
00361         }
00362       // not found, so return an indication of failure.
00363       return __not_found;
00364     } // end _M_do_find_next
00365 
00366   /**
00367    *  Base class, specialization for a single word.
00368    *
00369    *  See documentation for bitset.
00370   */
00371   template<>
00372     struct _Base_bitset<1>
00373     {
00374       typedef unsigned long _WordT;
00375       _WordT _M_w;
00376 
00377       _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
00378       : _M_w(0)
00379       { }
00380 
00381 #if __cplusplus >= 201103L
00382       constexpr _Base_bitset(unsigned long long __val) noexcept
00383 #else
00384       _Base_bitset(unsigned long __val)
00385 #endif
00386       : _M_w(__val)
00387       { }
00388 
00389       static _GLIBCXX_CONSTEXPR size_t
00390       _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
00391       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
00392 
00393       static _GLIBCXX_CONSTEXPR size_t
00394       _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
00395       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
00396 
00397       static _GLIBCXX_CONSTEXPR size_t
00398       _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
00399       {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
00400 
00401       static _GLIBCXX_CONSTEXPR _WordT
00402       _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
00403       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00404 
00405       _WordT&
00406       _M_getword(size_t) _GLIBCXX_NOEXCEPT
00407       { return _M_w; }
00408 
00409       _GLIBCXX_CONSTEXPR _WordT
00410       _M_getword(size_t) const _GLIBCXX_NOEXCEPT
00411       { return _M_w; }
00412 
00413 #if __cplusplus >= 201103L
00414       const _WordT*
00415       _M_getdata() const noexcept
00416       { return &_M_w; }
00417 #endif
00418 
00419       _WordT&
00420       _M_hiword() _GLIBCXX_NOEXCEPT
00421       { return _M_w; }
00422 
00423       _GLIBCXX_CONSTEXPR _WordT
00424       _M_hiword() const _GLIBCXX_NOEXCEPT
00425       { return _M_w; }
00426 
00427       void
00428       _M_do_and(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT
00429       { _M_w &= __x._M_w; }
00430 
00431       void
00432       _M_do_or(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT
00433       { _M_w |= __x._M_w; }
00434 
00435       void
00436       _M_do_xor(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT
00437       { _M_w ^= __x._M_w; }
00438 
00439       void
00440       _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT
00441       { _M_w <<= __shift; }
00442 
00443       void
00444       _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT
00445       { _M_w >>= __shift; }
00446 
00447       void
00448       _M_do_flip() _GLIBCXX_NOEXCEPT
00449       { _M_w = ~_M_w; }
00450 
00451       void
00452       _M_do_set() _GLIBCXX_NOEXCEPT
00453       { _M_w = ~static_cast<_WordT>(0); }
00454 
00455       void
00456       _M_do_reset() _GLIBCXX_NOEXCEPT
00457       { _M_w = 0; }
00458 
00459       bool
00460       _M_is_equal(const _Base_bitset<1>& __x) const _GLIBCXX_NOEXCEPT
00461       { return _M_w == __x._M_w; }
00462 
00463       template<size_t _Nb>
00464         bool
00465         _M_are_all() const _GLIBCXX_NOEXCEPT
00466         { return _M_w == (~static_cast<_WordT>(0)
00467                           >> (_GLIBCXX_BITSET_BITS_PER_WORD - _Nb)); }
00468 
00469       bool
00470       _M_is_any() const _GLIBCXX_NOEXCEPT
00471       { return _M_w != 0; }
00472 
00473       size_t
00474       _M_do_count() const _GLIBCXX_NOEXCEPT
00475       { return __builtin_popcountl(_M_w); }
00476 
00477       unsigned long
00478       _M_do_to_ulong() const _GLIBCXX_NOEXCEPT
00479       { return _M_w; }
00480 
00481 #if __cplusplus >= 201103L
00482       unsigned long long
00483       _M_do_to_ullong() const noexcept
00484       { return _M_w; }
00485 #endif
00486 
00487       size_t
00488       _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT
00489       {
00490         if (_M_w != 0)
00491           return __builtin_ctzl(_M_w);
00492         else
00493           return __not_found;
00494       }
00495 
00496       // find the next "on" bit that follows "prev"
00497       size_t
00498       _M_do_find_next(size_t __prev, size_t __not_found) const
00499         _GLIBCXX_NOEXCEPT
00500       {
00501         ++__prev;
00502         if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
00503           return __not_found;
00504 
00505         _WordT __x = _M_w >> __prev;
00506         if (__x != 0)
00507           return __builtin_ctzl(__x) + __prev;
00508         else
00509           return __not_found;
00510       }
00511     };
00512 
00513   /**
00514    *  Base class, specialization for no storage (zero-length %bitset).
00515    *
00516    *  See documentation for bitset.
00517   */
00518   template<>
00519     struct _Base_bitset<0>
00520     {
00521       typedef unsigned long _WordT;
00522 
00523       _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT
00524       { }
00525 
00526 #if __cplusplus >= 201103L
00527       constexpr _Base_bitset(unsigned long long) noexcept
00528 #else
00529       _Base_bitset(unsigned long)
00530 #endif
00531       { }
00532 
00533       static _GLIBCXX_CONSTEXPR size_t
00534       _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT
00535       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
00536 
00537       static _GLIBCXX_CONSTEXPR size_t
00538       _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT
00539       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
00540 
00541       static _GLIBCXX_CONSTEXPR size_t
00542       _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT
00543       {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
00544 
00545       static _GLIBCXX_CONSTEXPR _WordT
00546       _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT
00547       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
00548 
00549       // This would normally give access to the data.  The bounds-checking
00550       // in the bitset class will prevent the user from getting this far,
00551       // but (1) it must still return an lvalue to compile, and (2) the
00552       // user might call _Unchecked_set directly, in which case this /needs/
00553       // to fail.  Let's not penalize zero-length users unless they actually
00554       // make an unchecked call; all the memory ugliness is therefore
00555       // localized to this single should-never-get-this-far function.
00556       _WordT&
00557       _M_getword(size_t) _GLIBCXX_NOEXCEPT
00558       {
00559         __throw_out_of_range(__N("_Base_bitset::_M_getword")); 
00560         return *new _WordT;
00561       }
00562 
00563       _GLIBCXX_CONSTEXPR _WordT
00564       _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT
00565       { return 0; }
00566 
00567       _GLIBCXX_CONSTEXPR _WordT
00568       _M_hiword() const _GLIBCXX_NOEXCEPT
00569       { return 0; }
00570 
00571       void
00572       _M_do_and(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT
00573       { }
00574 
00575       void
00576       _M_do_or(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT
00577       { }
00578 
00579       void
00580       _M_do_xor(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT
00581       { }
00582 
00583       void
00584       _M_do_left_shift(size_t) _GLIBCXX_NOEXCEPT
00585       { }
00586 
00587       void
00588       _M_do_right_shift(size_t) _GLIBCXX_NOEXCEPT
00589       { }
00590 
00591       void
00592       _M_do_flip() _GLIBCXX_NOEXCEPT
00593       { }
00594 
00595       void
00596       _M_do_set() _GLIBCXX_NOEXCEPT
00597       { }
00598 
00599       void
00600       _M_do_reset() _GLIBCXX_NOEXCEPT
00601       { }
00602 
00603       // Are all empty bitsets equal to each other?  Are they equal to
00604       // themselves?  How to compare a thing which has no state?  What is
00605       // the sound of one zero-length bitset clapping?
00606       bool
00607       _M_is_equal(const _Base_bitset<0>&) const _GLIBCXX_NOEXCEPT
00608       { return true; }
00609 
00610       template<size_t _Nb>
00611         bool
00612         _M_are_all() const _GLIBCXX_NOEXCEPT
00613         { return true; }
00614 
00615       bool
00616       _M_is_any() const _GLIBCXX_NOEXCEPT
00617       { return false; }
00618 
00619       size_t
00620       _M_do_count() const _GLIBCXX_NOEXCEPT
00621       { return 0; }
00622 
00623       unsigned long
00624       _M_do_to_ulong() const _GLIBCXX_NOEXCEPT
00625       { return 0; }
00626 
00627 #if __cplusplus >= 201103L
00628       unsigned long long
00629       _M_do_to_ullong() const noexcept
00630       { return 0; }
00631 #endif
00632 
00633       // Normally "not found" is the size, but that could also be
00634       // misinterpreted as an index in this corner case.  Oh well.
00635       size_t
00636       _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT
00637       { return 0; }
00638 
00639       size_t
00640       _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT
00641       { return 0; }
00642     };
00643 
00644 
00645   // Helper class to zero out the unused high-order bits in the highest word.
00646   template<size_t _Extrabits>
00647     struct _Sanitize
00648     {
00649       typedef unsigned long _WordT;
00650 
00651       static void
00652       _S_do_sanitize(_WordT& __val) _GLIBCXX_NOEXCEPT
00653       { __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); }
00654     };
00655 
00656   template<>
00657     struct _Sanitize<0>
00658     {
00659       typedef unsigned long _WordT;
00660 
00661       static void
00662       _S_do_sanitize(_WordT) _GLIBCXX_NOEXCEPT { } 
00663     };
00664 
00665 #if __cplusplus >= 201103L
00666   template<size_t _Nb, bool = (_Nb < _GLIBCXX_BITSET_BITS_PER_ULL)>
00667     struct _Sanitize_val
00668     {
00669       static constexpr unsigned long long
00670       _S_do_sanitize_val(unsigned long long __val)
00671       { return __val; }
00672     };
00673 
00674   template<size_t _Nb>
00675     struct _Sanitize_val<_Nb, true>
00676     {
00677       static constexpr unsigned long long
00678       _S_do_sanitize_val(unsigned long long __val)
00679       { return __val & ~((~static_cast<unsigned long long>(0)) << _Nb); }
00680     };
00681 #endif
00682 
00683   /**
00684    *  @brief The %bitset class represents a @e fixed-size sequence of bits.
00685    *  @ingroup utilities
00686    *
00687    *  (Note that %bitset does @e not meet the formal requirements of a
00688    *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
00689    *
00690    *  The template argument, @a Nb, may be any non-negative number,
00691    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
00692    *
00693    *  In the general unoptimized case, storage is allocated in word-sized
00694    *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
00695    *  words will be used for storage.  B - Nb%B bits are unused.  (They are
00696    *  the high-order bits in the highest word.)  It is a class invariant
00697    *  that those unused bits are always zero.
00698    *
00699    *  If you think of %bitset as <em>a simple array of bits</em>, be
00700    *  aware that your mental picture is reversed: a %bitset behaves
00701    *  the same way as bits in integers do, with the bit at index 0 in
00702    *  the <em>least significant / right-hand</em> position, and the bit at
00703    *  index Nb-1 in the <em>most significant / left-hand</em> position.
00704    *  Thus, unlike other containers, a %bitset's index <em>counts from
00705    *  right to left</em>, to put it very loosely.
00706    *
00707    *  This behavior is preserved when translating to and from strings.  For
00708    *  example, the first line of the following program probably prints
00709    *  <em>b(&apos;a&apos;) is 0001100001</em> on a modern ASCII system.
00710    *
00711    *  @code
00712    *     #include <bitset>
00713    *     #include <iostream>
00714    *     #include <sstream>
00715    *
00716    *     using namespace std;
00717    *
00718    *     int main()
00719    *     {
00720    *         long         a = 'a';
00721    *         bitset<10>   b(a);
00722    *
00723    *         cout << "b('a') is " << b << endl;
00724    *
00725    *         ostringstream s;
00726    *         s << b;
00727    *         string  str = s.str();
00728    *         cout << "index 3 in the string is " << str[3] << " but\n"
00729    *              << "index 3 in the bitset is " << b[3] << endl;
00730    *     }
00731    *  @endcode
00732    *
00733    *  Also see:
00734    *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_containers.html
00735    *  for a description of extensions.
00736    *
00737    *  Most of the actual code isn't contained in %bitset<> itself, but in the
00738    *  base class _Base_bitset.  The base class works with whole words, not with
00739    *  individual bits.  This allows us to specialize _Base_bitset for the
00740    *  important special case where the %bitset is only a single word.
00741    *
00742    *  Extra confusion can result due to the fact that the storage for
00743    *  _Base_bitset @e is a regular array, and is indexed as such.  This is
00744    *  carefully encapsulated.
00745   */
00746   template<size_t _Nb>
00747     class bitset
00748     : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
00749     {
00750     private:
00751       typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
00752       typedef unsigned long _WordT;
00753 
00754       template<class _CharT, class _Traits, class _Alloc>
00755       void
00756       _M_check_initial_position(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
00757                                 size_t __position) const
00758       {
00759         if (__position > __s.size())
00760           __throw_out_of_range_fmt(__N("bitset::bitset: __position "
00761                                        "(which is %zu) > __s.size() "
00762                                        "(which is %zu)"),
00763                                    __position, __s.size());
00764       }
00765 
00766       void _M_check(size_t __position, const char *__s) const
00767       {
00768         if (__position >= _Nb)
00769           __throw_out_of_range_fmt(__N("%s: __position (which is %zu) "
00770                                        ">= _Nb (which is %zu)"),
00771                                    __s, __position, _Nb);
00772       }
00773 
00774       void
00775       _M_do_sanitize() _GLIBCXX_NOEXCEPT
00776       { 
00777         typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type;
00778         __sanitize_type::_S_do_sanitize(this->_M_hiword());
00779       }
00780 
00781 #if __cplusplus >= 201103L
00782       template<typename> friend struct hash;
00783 #endif
00784 
00785     public:
00786       /**
00787        *  This encapsulates the concept of a single bit.  An instance of this
00788        *  class is a proxy for an actual bit; this way the individual bit
00789        *  operations are done as faster word-size bitwise instructions.
00790        *
00791        *  Most users will never need to use this class directly; conversions
00792        *  to and from bool are automatic and should be transparent.  Overloaded
00793        *  operators help to preserve the illusion.
00794        *
00795        *  (On a typical system, this <em>bit %reference</em> is 64
00796        *  times the size of an actual bit.  Ha.)
00797        */
00798       class reference
00799       {
00800         friend class bitset;
00801 
00802         _WordT* _M_wp;
00803         size_t  _M_bpos;
00804         
00805         // left undefined
00806         reference();
00807         
00808       public:
00809         reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT
00810         {
00811           _M_wp = &__b._M_getword(__pos);
00812           _M_bpos = _Base::_S_whichbit(__pos);
00813         }
00814 
00815         ~reference() _GLIBCXX_NOEXCEPT
00816         { }
00817 
00818         // For b[i] = __x;
00819         reference&
00820         operator=(bool __x) _GLIBCXX_NOEXCEPT
00821         {
00822           if (__x)
00823             *_M_wp |= _Base::_S_maskbit(_M_bpos);
00824           else
00825             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
00826           return *this;
00827         }
00828 
00829         // For b[i] = b[__j];
00830         reference&
00831         operator=(const reference& __j) _GLIBCXX_NOEXCEPT
00832         {
00833           if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
00834             *_M_wp |= _Base::_S_maskbit(_M_bpos);
00835           else
00836             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
00837           return *this;
00838         }
00839 
00840         // Flips the bit
00841         bool
00842         operator~() const _GLIBCXX_NOEXCEPT
00843         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
00844 
00845         // For __x = b[i];
00846         operator bool() const _GLIBCXX_NOEXCEPT
00847         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
00848 
00849         // For b[i].flip();
00850         reference&
00851         flip() _GLIBCXX_NOEXCEPT
00852         {
00853           *_M_wp ^= _Base::_S_maskbit(_M_bpos);
00854           return *this;
00855         }
00856       };
00857       friend class reference;
00858 
00859       // 23.3.5.1 constructors:
00860       /// All bits set to zero.
00861       _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT
00862       { }
00863 
00864       /// Initial bits bitwise-copied from a single word (others set to zero).
00865 #if __cplusplus >= 201103L
00866       constexpr bitset(unsigned long long __val) noexcept
00867       : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { }
00868 #else
00869       bitset(unsigned long __val)
00870       : _Base(__val)
00871       { _M_do_sanitize(); }
00872 #endif
00873 
00874       /**
00875        *  Use a subset of a string.
00876        *  @param  __s  A string of @a 0 and @a 1 characters.
00877        *  @param  __position  Index of the first character in @a __s to use;
00878        *                    defaults to zero.
00879        *  @throw  std::out_of_range  If @a pos is bigger the size of @a __s.
00880        *  @throw  std::invalid_argument  If a character appears in the string
00881        *                                 which is neither @a 0 nor @a 1.
00882        */
00883       template<class _CharT, class _Traits, class _Alloc>
00884         explicit
00885         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
00886                size_t __position = 0)
00887         : _Base()
00888         {
00889           _M_check_initial_position(__s, __position);
00890           _M_copy_from_string(__s, __position,
00891                               std::basic_string<_CharT, _Traits, _Alloc>::npos,
00892                               _CharT('0'), _CharT('1'));
00893         }
00894 
00895       /**
00896        *  Use a subset of a string.
00897        *  @param  __s  A string of @a 0 and @a 1 characters.
00898        *  @param  __position  Index of the first character in @a __s to use.
00899        *  @param  __n    The number of characters to copy.
00900        *  @throw std::out_of_range If @a __position is bigger the size
00901        *  of @a __s.
00902        *  @throw  std::invalid_argument  If a character appears in the string
00903        *                                 which is neither @a 0 nor @a 1.
00904        */
00905       template<class _CharT, class _Traits, class _Alloc>
00906         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
00907                size_t __position, size_t __n)
00908         : _Base()
00909         {
00910           _M_check_initial_position(__s, __position);
00911           _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1'));
00912         }
00913 
00914       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00915       // 396. what are characters zero and one.
00916       template<class _CharT, class _Traits, class _Alloc>
00917         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
00918                size_t __position, size_t __n,
00919                _CharT __zero, _CharT __one = _CharT('1'))
00920         : _Base()
00921         {
00922           _M_check_initial_position(__s, __position);
00923           _M_copy_from_string(__s, __position, __n, __zero, __one);
00924         }
00925 
00926 #if __cplusplus >= 201103L
00927       /**
00928        *  Construct from a character %array.
00929        *  @param  __str  An %array of characters @a zero and @a one.
00930        *  @param  __n    The number of characters to use.
00931        *  @param  __zero The character corresponding to the value 0.
00932        *  @param  __one  The character corresponding to the value 1.
00933        *  @throw  std::invalid_argument If a character appears in the string
00934        *                                which is neither @a __zero nor @a __one.
00935        */
00936       template<typename _CharT>
00937         explicit
00938         bitset(const _CharT* __str,
00939                typename std::basic_string<_CharT>::size_type __n
00940                = std::basic_string<_CharT>::npos,
00941                _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'))
00942         : _Base()
00943         {
00944           if (!__str)
00945             __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)"));
00946 
00947           if (__n == std::basic_string<_CharT>::npos)
00948             __n = std::char_traits<_CharT>::length(__str);
00949           _M_copy_from_ptr<_CharT, std::char_traits<_CharT>>(__str, __n, 0,
00950                                                              __n, __zero,
00951                                                              __one);
00952         }
00953 #endif
00954 
00955       // 23.3.5.2 bitset operations:
00956       //@{
00957       /**
00958        *  Operations on bitsets.
00959        *  @param  __rhs  A same-sized bitset.
00960        *
00961        *  These should be self-explanatory.
00962        */
00963       bitset<_Nb>&
00964       operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
00965       {
00966         this->_M_do_and(__rhs);
00967         return *this;
00968       }
00969 
00970       bitset<_Nb>&
00971       operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
00972       {
00973         this->_M_do_or(__rhs);
00974         return *this;
00975       }
00976 
00977       bitset<_Nb>&
00978       operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
00979       {
00980         this->_M_do_xor(__rhs);
00981         return *this;
00982       }
00983       //@}
00984       
00985       //@{
00986       /**
00987        *  Operations on bitsets.
00988        *  @param  __position  The number of places to shift.
00989        *
00990        *  These should be self-explanatory.
00991        */
00992       bitset<_Nb>&
00993       operator<<=(size_t __position) _GLIBCXX_NOEXCEPT
00994       {
00995         if (__builtin_expect(__position < _Nb, 1))
00996           {
00997             this->_M_do_left_shift(__position);
00998             this->_M_do_sanitize();
00999           }
01000         else
01001           this->_M_do_reset();
01002         return *this;
01003       }
01004 
01005       bitset<_Nb>&
01006       operator>>=(size_t __position) _GLIBCXX_NOEXCEPT
01007       {
01008         if (__builtin_expect(__position < _Nb, 1))
01009           {
01010             this->_M_do_right_shift(__position);
01011             this->_M_do_sanitize();
01012           }
01013         else
01014           this->_M_do_reset();
01015         return *this;
01016       }
01017       //@}
01018       
01019       //@{
01020       /**
01021        *  These versions of single-bit set, reset, flip, and test are
01022        *  extensions from the SGI version.  They do no range checking.
01023        *  @ingroup SGIextensions
01024        */
01025       bitset<_Nb>&
01026       _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT
01027       {
01028         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
01029         return *this;
01030       }
01031 
01032       bitset<_Nb>&
01033       _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT
01034       {
01035         if (__val)
01036           this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
01037         else
01038           this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
01039         return *this;
01040       }
01041 
01042       bitset<_Nb>&
01043       _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT
01044       {
01045         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
01046         return *this;
01047       }
01048 
01049       bitset<_Nb>&
01050       _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT
01051       {
01052         this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
01053         return *this;
01054       }
01055 
01056       _GLIBCXX_CONSTEXPR bool
01057       _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT
01058       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
01059                 != static_cast<_WordT>(0)); }
01060       //@}
01061       
01062       // Set, reset, and flip.
01063       /**
01064        *  @brief Sets every bit to true.
01065        */
01066       bitset<_Nb>&
01067       set() _GLIBCXX_NOEXCEPT
01068       {
01069         this->_M_do_set();
01070         this->_M_do_sanitize();
01071         return *this;
01072       }
01073 
01074       /**
01075        *  @brief Sets a given bit to a particular value.
01076        *  @param  __position  The index of the bit.
01077        *  @param  __val  Either true or false, defaults to true.
01078        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
01079        */
01080       bitset<_Nb>&
01081       set(size_t __position, bool __val = true)
01082       {
01083         this->_M_check(__position, __N("bitset::set"));
01084         return _Unchecked_set(__position, __val);
01085       }
01086 
01087       /**
01088        *  @brief Sets every bit to false.
01089        */
01090       bitset<_Nb>&
01091       reset() _GLIBCXX_NOEXCEPT
01092       {
01093         this->_M_do_reset();
01094         return *this;
01095       }
01096 
01097       /**
01098        *  @brief Sets a given bit to false.
01099        *  @param  __position  The index of the bit.
01100        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
01101        *
01102        *  Same as writing @c set(pos,false).
01103        */
01104       bitset<_Nb>&
01105       reset(size_t __position)
01106       {
01107         this->_M_check(__position, __N("bitset::reset"));
01108         return _Unchecked_reset(__position);
01109       }
01110       
01111       /**
01112        *  @brief Toggles every bit to its opposite value.
01113        */
01114       bitset<_Nb>&
01115       flip() _GLIBCXX_NOEXCEPT
01116       {
01117         this->_M_do_flip();
01118         this->_M_do_sanitize();
01119         return *this;
01120       }
01121 
01122       /**
01123        *  @brief Toggles a given bit to its opposite value.
01124        *  @param  __position  The index of the bit.
01125        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
01126        */
01127       bitset<_Nb>&
01128       flip(size_t __position)
01129       {
01130         this->_M_check(__position, __N("bitset::flip"));
01131         return _Unchecked_flip(__position);
01132       }
01133       
01134       /// See the no-argument flip().
01135       bitset<_Nb>
01136       operator~() const _GLIBCXX_NOEXCEPT
01137       { return bitset<_Nb>(*this).flip(); }
01138 
01139       //@{
01140       /**
01141        *  @brief  Array-indexing support.
01142        *  @param  __position  Index into the %bitset.
01143        *  @return A bool for a <em>const %bitset</em>.  For non-const
01144        *           bitsets, an instance of the reference proxy class.
01145        *  @note  These operators do no range checking and throw no exceptions,
01146        *         as required by DR 11 to the standard.
01147        *
01148        *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
01149        *  resolves DR 11 (items 1 and 2), but does not do the range-checking
01150        *  required by that DR's resolution.  -pme
01151        *  The DR has since been changed:  range-checking is a precondition
01152        *  (users' responsibility), and these functions must not throw.  -pme
01153        */
01154       reference
01155       operator[](size_t __position)
01156       { return reference(*this, __position); }
01157 
01158       _GLIBCXX_CONSTEXPR bool
01159       operator[](size_t __position) const
01160       { return _Unchecked_test(__position); }
01161       //@}
01162       
01163       /**
01164        *  @brief Returns a numerical interpretation of the %bitset.
01165        *  @return  The integral equivalent of the bits.
01166        *  @throw  std::overflow_error  If there are too many bits to be
01167        *                               represented in an @c unsigned @c long.
01168        */
01169       unsigned long
01170       to_ulong() const
01171       { return this->_M_do_to_ulong(); }
01172 
01173 #if __cplusplus >= 201103L
01174       unsigned long long
01175       to_ullong() const
01176       { return this->_M_do_to_ullong(); }
01177 #endif
01178 
01179       /**
01180        *  @brief Returns a character interpretation of the %bitset.
01181        *  @return  The string equivalent of the bits.
01182        *
01183        *  Note the ordering of the bits:  decreasing character positions
01184        *  correspond to increasing bit positions (see the main class notes for
01185        *  an example).
01186        */
01187       template<class _CharT, class _Traits, class _Alloc>
01188         std::basic_string<_CharT, _Traits, _Alloc>
01189         to_string() const
01190         {
01191           std::basic_string<_CharT, _Traits, _Alloc> __result;
01192           _M_copy_to_string(__result, _CharT('0'), _CharT('1'));
01193           return __result;
01194         }
01195 
01196       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01197       // 396. what are characters zero and one.
01198       template<class _CharT, class _Traits, class _Alloc>
01199         std::basic_string<_CharT, _Traits, _Alloc>
01200         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
01201         {
01202           std::basic_string<_CharT, _Traits, _Alloc> __result;
01203           _M_copy_to_string(__result, __zero, __one);
01204           return __result;
01205         }
01206 
01207       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01208       // 434. bitset::to_string() hard to use.
01209       template<class _CharT, class _Traits>
01210         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
01211         to_string() const
01212         { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
01213 
01214       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01215       // 853. to_string needs updating with zero and one.
01216       template<class _CharT, class _Traits>
01217         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
01218         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
01219         { return to_string<_CharT, _Traits,
01220                            std::allocator<_CharT> >(__zero, __one); }
01221 
01222       template<class _CharT>
01223         std::basic_string<_CharT, std::char_traits<_CharT>,
01224                           std::allocator<_CharT> >
01225         to_string() const
01226         {
01227           return to_string<_CharT, std::char_traits<_CharT>,
01228                            std::allocator<_CharT> >();
01229         }
01230 
01231       template<class _CharT>
01232         std::basic_string<_CharT, std::char_traits<_CharT>,
01233                           std::allocator<_CharT> >
01234         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
01235         {
01236           return to_string<_CharT, std::char_traits<_CharT>,
01237                            std::allocator<_CharT> >(__zero, __one);
01238         }
01239 
01240       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
01241       to_string() const
01242       {
01243         return to_string<char, std::char_traits<char>,
01244                          std::allocator<char> >();
01245       }
01246 
01247       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
01248       to_string(char __zero, char __one = '1') const
01249       {
01250         return to_string<char, std::char_traits<char>,
01251                          std::allocator<char> >(__zero, __one);
01252       }
01253 
01254       // Helper functions for string operations.
01255       template<class _CharT, class _Traits>
01256         void
01257         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
01258                          _CharT, _CharT);
01259 
01260       template<class _CharT, class _Traits, class _Alloc>
01261         void
01262         _M_copy_from_string(const std::basic_string<_CharT,
01263                             _Traits, _Alloc>& __s, size_t __pos, size_t __n,
01264                             _CharT __zero, _CharT __one)
01265         { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n,
01266                                             __zero, __one); }
01267 
01268       template<class _CharT, class _Traits, class _Alloc>
01269         void
01270         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&,
01271                           _CharT, _CharT) const;
01272 
01273       // NB: Backward compat.
01274       template<class _CharT, class _Traits, class _Alloc>
01275         void
01276         _M_copy_from_string(const std::basic_string<_CharT,
01277                             _Traits, _Alloc>& __s, size_t __pos, size_t __n)
01278         { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); }
01279 
01280       template<class _CharT, class _Traits, class _Alloc>
01281         void
01282         _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const
01283         { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); }
01284 
01285       /// Returns the number of bits which are set.
01286       size_t
01287       count() const _GLIBCXX_NOEXCEPT
01288       { return this->_M_do_count(); }
01289 
01290       /// Returns the total number of bits.
01291       _GLIBCXX_CONSTEXPR size_t
01292       size() const _GLIBCXX_NOEXCEPT
01293       { return _Nb; }
01294 
01295       //@{
01296       /// These comparisons for equality/inequality are, well, @e bitwise.
01297       bool
01298       operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
01299       { return this->_M_is_equal(__rhs); }
01300 
01301       bool
01302       operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
01303       { return !this->_M_is_equal(__rhs); }
01304       //@}
01305       
01306       /**
01307        *  @brief Tests the value of a bit.
01308        *  @param  __position  The index of a bit.
01309        *  @return  The value at @a pos.
01310        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
01311        */
01312       bool
01313       test(size_t __position) const
01314       {
01315         this->_M_check(__position, __N("bitset::test"));
01316         return _Unchecked_test(__position);
01317       }
01318 
01319       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01320       // DR 693. std::bitset::all() missing.
01321       /**
01322        *  @brief Tests whether all the bits are on.
01323        *  @return  True if all the bits are set.
01324        */
01325       bool
01326       all() const _GLIBCXX_NOEXCEPT
01327       { return this->template _M_are_all<_Nb>(); }
01328 
01329       /**
01330        *  @brief Tests whether any of the bits are on.
01331        *  @return  True if at least one bit is set.
01332        */
01333       bool
01334       any() const _GLIBCXX_NOEXCEPT
01335       { return this->_M_is_any(); }
01336 
01337       /**
01338        *  @brief Tests whether any of the bits are on.
01339        *  @return  True if none of the bits are set.
01340        */
01341       bool
01342       none() const _GLIBCXX_NOEXCEPT
01343       { return !this->_M_is_any(); }
01344 
01345       //@{
01346       /// Self-explanatory.
01347       bitset<_Nb>
01348       operator<<(size_t __position) const _GLIBCXX_NOEXCEPT
01349       { return bitset<_Nb>(*this) <<= __position; }
01350 
01351       bitset<_Nb>
01352       operator>>(size_t __position) const _GLIBCXX_NOEXCEPT
01353       { return bitset<_Nb>(*this) >>= __position; }
01354       //@}
01355       
01356       /**
01357        *  @brief  Finds the index of the first "on" bit.
01358        *  @return  The index of the first bit set, or size() if not found.
01359        *  @ingroup SGIextensions
01360        *  @sa  _Find_next
01361        */
01362       size_t
01363       _Find_first() const _GLIBCXX_NOEXCEPT
01364       { return this->_M_do_find_first(_Nb); }
01365 
01366       /**
01367        *  @brief  Finds the index of the next "on" bit after prev.
01368        *  @return  The index of the next bit set, or size() if not found.
01369        *  @param  __prev  Where to start searching.
01370        *  @ingroup SGIextensions
01371        *  @sa  _Find_first
01372        */
01373       size_t
01374       _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT
01375       { return this->_M_do_find_next(__prev, _Nb); }
01376     };
01377 
01378   // Definitions of non-inline member functions.
01379   template<size_t _Nb>
01380     template<class _CharT, class _Traits>
01381       void
01382       bitset<_Nb>::
01383       _M_copy_from_ptr(const _CharT* __s, size_t __len,
01384                        size_t __pos, size_t __n, _CharT __zero, _CharT __one)
01385       {
01386         reset();
01387         const size_t __nbits = std::min(_Nb, std::min(__n, size_t(__len - __pos)));
01388         for (size_t __i = __nbits; __i > 0; --__i)
01389           {
01390             const _CharT __c = __s[__pos + __nbits - __i];
01391             if (_Traits::eq(__c, __zero))
01392               ;
01393             else if (_Traits::eq(__c, __one))
01394               _Unchecked_set(__i - 1);
01395             else
01396               __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
01397           }
01398       }
01399 
01400   template<size_t _Nb>
01401     template<class _CharT, class _Traits, class _Alloc>
01402       void
01403       bitset<_Nb>::
01404       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s,
01405                         _CharT __zero, _CharT __one) const
01406       {
01407         __s.assign(_Nb, __zero);
01408         for (size_t __i = _Nb; __i > 0; --__i)
01409           if (_Unchecked_test(__i - 1))
01410             _Traits::assign(__s[_Nb - __i], __one);
01411       }
01412 
01413   // 23.3.5.3 bitset operations:
01414   //@{
01415   /**
01416    *  @brief  Global bitwise operations on bitsets.
01417    *  @param  __x  A bitset.
01418    *  @param  __y  A bitset of the same size as @a __x.
01419    *  @return  A new bitset.
01420    *
01421    *  These should be self-explanatory.
01422   */
01423   template<size_t _Nb>
01424     inline bitset<_Nb>
01425     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
01426     {
01427       bitset<_Nb> __result(__x);
01428       __result &= __y;
01429       return __result;
01430     }
01431 
01432   template<size_t _Nb>
01433     inline bitset<_Nb>
01434     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
01435     {
01436       bitset<_Nb> __result(__x);
01437       __result |= __y;
01438       return __result;
01439     }
01440 
01441   template <size_t _Nb>
01442     inline bitset<_Nb>
01443     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
01444     {
01445       bitset<_Nb> __result(__x);
01446       __result ^= __y;
01447       return __result;
01448     }
01449   //@}
01450 
01451   //@{
01452   /**
01453    *  @brief Global I/O operators for bitsets.
01454    *
01455    *  Direct I/O between streams and bitsets is supported.  Output is
01456    *  straightforward.  Input will skip whitespace, only accept @a 0 and @a 1
01457    *  characters, and will only extract as many digits as the %bitset will
01458    *  hold.
01459   */
01460   template<class _CharT, class _Traits, size_t _Nb>
01461     std::basic_istream<_CharT, _Traits>&
01462     operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
01463     {
01464       typedef typename _Traits::char_type          char_type;
01465       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
01466       typedef typename __istream_type::ios_base    __ios_base;
01467 
01468       std::basic_string<_CharT, _Traits> __tmp;
01469       __tmp.reserve(_Nb);
01470 
01471       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01472       // 303. Bitset input operator underspecified
01473       const char_type __zero = __is.widen('0');
01474       const char_type __one = __is.widen('1');
01475 
01476       typename __ios_base::iostate __state = __ios_base::goodbit;
01477       typename __istream_type::sentry __sentry(__is);
01478       if (__sentry)
01479         {
01480           __try
01481             {
01482               for (size_t __i = _Nb; __i > 0; --__i)
01483                 {
01484                   static typename _Traits::int_type __eof = _Traits::eof();
01485                   
01486                   typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
01487                   if (_Traits::eq_int_type(__c1, __eof))
01488                     {
01489                       __state |= __ios_base::eofbit;
01490                       break;
01491                     }
01492                   else
01493                     {
01494                       const char_type __c2 = _Traits::to_char_type(__c1);
01495                       if (_Traits::eq(__c2, __zero))
01496                         __tmp.push_back(__zero);
01497                       else if (_Traits::eq(__c2, __one))
01498                         __tmp.push_back(__one);
01499                       else if (_Traits::
01500                                eq_int_type(__is.rdbuf()->sputbackc(__c2),
01501                                            __eof))
01502                         {
01503                           __state |= __ios_base::failbit;
01504                           break;
01505                         }
01506                     }
01507                 }
01508             }
01509           __catch(__cxxabiv1::__forced_unwind&)
01510             {
01511               __is._M_setstate(__ios_base::badbit);             
01512               __throw_exception_again;
01513             }
01514           __catch(...)
01515             { __is._M_setstate(__ios_base::badbit); }
01516         }
01517 
01518       if (__tmp.empty() && _Nb)
01519         __state |= __ios_base::failbit;
01520       else
01521         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb,
01522                                 __zero, __one);
01523       if (__state)
01524         __is.setstate(__state);
01525       return __is;
01526     }
01527 
01528   template <class _CharT, class _Traits, size_t _Nb>
01529     std::basic_ostream<_CharT, _Traits>&
01530     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
01531                const bitset<_Nb>& __x)
01532     {
01533       std::basic_string<_CharT, _Traits> __tmp;
01534 
01535       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01536       // 396. what are characters zero and one.
01537       const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
01538       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
01539       return __os << __tmp;
01540     }
01541   //@}
01542 
01543 _GLIBCXX_END_NAMESPACE_CONTAINER
01544 } // namespace std
01545 
01546 #undef _GLIBCXX_BITSET_WORDS
01547 #undef _GLIBCXX_BITSET_BITS_PER_WORD
01548 #undef _GLIBCXX_BITSET_BITS_PER_ULL
01549 
01550 #if __cplusplus >= 201103L
01551 
01552 #include <bits/functional_hash.h>
01553 
01554 namespace std _GLIBCXX_VISIBILITY(default)
01555 {
01556 _GLIBCXX_BEGIN_NAMESPACE_VERSION
01557 
01558   // DR 1182.
01559   /// std::hash specialization for bitset.
01560   template<size_t _Nb>
01561     struct hash<_GLIBCXX_STD_C::bitset<_Nb>>
01562     : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>>
01563     {
01564       size_t
01565       operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept
01566       {
01567         const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__;
01568         return std::_Hash_impl::hash(__b._M_getdata(), __clength);
01569       }
01570     };
01571 
01572   template<>
01573     struct hash<_GLIBCXX_STD_C::bitset<0>>
01574     : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>>
01575     {
01576       size_t
01577       operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept
01578       { return 0; }
01579     };
01580 
01581 _GLIBCXX_END_NAMESPACE_VERSION
01582 } // namespace
01583 
01584 #endif // C++11
01585 
01586 #ifdef _GLIBCXX_DEBUG
01587 # include <debug/bitset>
01588 #endif
01589 
01590 #ifdef _GLIBCXX_PROFILE
01591 # include <profile/bitset>
01592 #endif
01593 
01594 #endif /* _GLIBCXX_BITSET */