Home | History | Annotate | Download | only in include
      1 // <bitset> -*- C++ -*-
      2 
      3 // Copyright (C) 2001-2014 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    *  The %bitset class represents a @e fixed-size sequence of bits.
    685    *
    686    *  @ingroup containers
    687    *
    688    *  (Note that %bitset does @e not meet the formal requirements of a
    689    *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
    690    *
    691    *  The template argument, @a Nb, may be any non-negative number,
    692    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
    693    *
    694    *  In the general unoptimized case, storage is allocated in word-sized
    695    *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
    696    *  words will be used for storage.  B - Nb%B bits are unused.  (They are
    697    *  the high-order bits in the highest word.)  It is a class invariant
    698    *  that those unused bits are always zero.
    699    *
    700    *  If you think of %bitset as <em>a simple array of bits</em>, be
    701    *  aware that your mental picture is reversed: a %bitset behaves
    702    *  the same way as bits in integers do, with the bit at index 0 in
    703    *  the <em>least significant / right-hand</em> position, and the bit at
    704    *  index Nb-1 in the <em>most significant / left-hand</em> position.
    705    *  Thus, unlike other containers, a %bitset's index <em>counts from
    706    *  right to left</em>, to put it very loosely.
    707    *
    708    *  This behavior is preserved when translating to and from strings.  For
    709    *  example, the first line of the following program probably prints
    710    *  <em>b(&apos;a&apos;) is 0001100001</em> on a modern ASCII system.
    711    *
    712    *  @code
    713    *     #include <bitset>
    714    *     #include <iostream>
    715    *     #include <sstream>
    716    *
    717    *     using namespace std;
    718    *
    719    *     int main()
    720    *     {
    721    *         long         a = 'a';
    722    *         bitset<10>   b(a);
    723    *
    724    *         cout << "b('a') is " << b << endl;
    725    *
    726    *         ostringstream s;
    727    *         s << b;
    728    *         string  str = s.str();
    729    *         cout << "index 3 in the string is " << str[3] << " but\n"
    730    *              << "index 3 in the bitset is " << b[3] << endl;
    731    *     }
    732    *  @endcode
    733    *
    734    *  Also see:
    735    *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html
    736    *  for a description of extensions.
    737    *
    738    *  Most of the actual code isn't contained in %bitset<> itself, but in the
    739    *  base class _Base_bitset.  The base class works with whole words, not with
    740    *  individual bits.  This allows us to specialize _Base_bitset for the
    741    *  important special case where the %bitset is only a single word.
    742    *
    743    *  Extra confusion can result due to the fact that the storage for
    744    *  _Base_bitset @e is a regular array, and is indexed as such.  This is
    745    *  carefully encapsulated.
    746   */
    747   template<size_t _Nb>
    748     class bitset
    749     : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
    750     {
    751     private:
    752       typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
    753       typedef unsigned long _WordT;
    754 
    755       template<class _CharT, class _Traits, class _Alloc>
    756       void
    757       _M_check_initial_position(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
    758 				size_t __position) const
    759       {
    760 	if (__position > __s.size())
    761 	  __throw_out_of_range_fmt(__N("bitset::bitset: __position "
    762 				       "(which is %zu) > __s.size() "
    763 				       "(which is %zu)"),
    764 				   __position, __s.size());
    765       }
    766 
    767       void _M_check(size_t __position, const char *__s) const
    768       {
    769 	if (__position >= _Nb)
    770 	  __throw_out_of_range_fmt(__N("%s: __position (which is %zu) "
    771 				       ">= _Nb (which is %zu)"),
    772 				   __s, __position, _Nb);
    773       }
    774 
    775       void
    776       _M_do_sanitize() _GLIBCXX_NOEXCEPT
    777       { 
    778 	typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type;
    779 	__sanitize_type::_S_do_sanitize(this->_M_hiword());
    780       }
    781 
    782 #if __cplusplus >= 201103L
    783       template<typename> friend struct hash;
    784 #endif
    785 
    786     public:
    787       /**
    788        *  This encapsulates the concept of a single bit.  An instance of this
    789        *  class is a proxy for an actual bit; this way the individual bit
    790        *  operations are done as faster word-size bitwise instructions.
    791        *
    792        *  Most users will never need to use this class directly; conversions
    793        *  to and from bool are automatic and should be transparent.  Overloaded
    794        *  operators help to preserve the illusion.
    795        *
    796        *  (On a typical system, this <em>bit %reference</em> is 64
    797        *  times the size of an actual bit.  Ha.)
    798        */
    799       class reference
    800       {
    801 	friend class bitset;
    802 
    803 	_WordT*	_M_wp;
    804 	size_t 	_M_bpos;
    805 	
    806 	// left undefined
    807 	reference();
    808 	
    809       public:
    810 	reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT
    811 	{
    812 	  _M_wp = &__b._M_getword(__pos);
    813 	  _M_bpos = _Base::_S_whichbit(__pos);
    814 	}
    815 
    816 	~reference() _GLIBCXX_NOEXCEPT
    817 	{ }
    818 
    819 	// For b[i] = __x;
    820 	reference&
    821 	operator=(bool __x) _GLIBCXX_NOEXCEPT
    822 	{
    823 	  if (__x)
    824 	    *_M_wp |= _Base::_S_maskbit(_M_bpos);
    825 	  else
    826 	    *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
    827 	  return *this;
    828 	}
    829 
    830 	// For b[i] = b[__j];
    831 	reference&
    832 	operator=(const reference& __j) _GLIBCXX_NOEXCEPT
    833 	{
    834 	  if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
    835 	    *_M_wp |= _Base::_S_maskbit(_M_bpos);
    836 	  else
    837 	    *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
    838 	  return *this;
    839 	}
    840 
    841 	// Flips the bit
    842 	bool
    843 	operator~() const _GLIBCXX_NOEXCEPT
    844 	{ return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
    845 
    846 	// For __x = b[i];
    847 	operator bool() const _GLIBCXX_NOEXCEPT
    848 	{ return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
    849 
    850 	// For b[i].flip();
    851 	reference&
    852 	flip() _GLIBCXX_NOEXCEPT
    853 	{
    854 	  *_M_wp ^= _Base::_S_maskbit(_M_bpos);
    855 	  return *this;
    856 	}
    857       };
    858       friend class reference;
    859 
    860       // 23.3.5.1 constructors:
    861       /// All bits set to zero.
    862       _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT
    863       { }
    864 
    865       /// Initial bits bitwise-copied from a single word (others set to zero).
    866 #if __cplusplus >= 201103L
    867       constexpr bitset(unsigned long long __val) noexcept
    868       : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { }
    869 #else
    870       bitset(unsigned long __val)
    871       : _Base(__val)
    872       { _M_do_sanitize(); }
    873 #endif
    874 
    875       /**
    876        *  Use a subset of a string.
    877        *  @param  __s  A string of @a 0 and @a 1 characters.
    878        *  @param  __position  Index of the first character in @a __s to use;
    879        *                    defaults to zero.
    880        *  @throw  std::out_of_range  If @a pos is bigger the size of @a __s.
    881        *  @throw  std::invalid_argument  If a character appears in the string
    882        *                                 which is neither @a 0 nor @a 1.
    883        */
    884       template<class _CharT, class _Traits, class _Alloc>
    885 	explicit
    886 	bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
    887 	       size_t __position = 0)
    888 	: _Base()
    889 	{
    890 	  _M_check_initial_position(__s, __position);
    891 	  _M_copy_from_string(__s, __position,
    892 			      std::basic_string<_CharT, _Traits, _Alloc>::npos,
    893 			      _CharT('0'), _CharT('1'));
    894 	}
    895 
    896       /**
    897        *  Use a subset of a string.
    898        *  @param  __s  A string of @a 0 and @a 1 characters.
    899        *  @param  __position  Index of the first character in @a __s to use.
    900        *  @param  __n    The number of characters to copy.
    901        *  @throw std::out_of_range If @a __position is bigger the size
    902        *  of @a __s.
    903        *  @throw  std::invalid_argument  If a character appears in the string
    904        *                                 which is neither @a 0 nor @a 1.
    905        */
    906       template<class _CharT, class _Traits, class _Alloc>
    907 	bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
    908 	       size_t __position, size_t __n)
    909 	: _Base()
    910 	{
    911 	  _M_check_initial_position(__s, __position);
    912 	  _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1'));
    913 	}
    914 
    915       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    916       // 396. what are characters zero and one.
    917       template<class _CharT, class _Traits, class _Alloc>
    918 	bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
    919 	       size_t __position, size_t __n,
    920 	       _CharT __zero, _CharT __one = _CharT('1'))
    921 	: _Base()
    922 	{
    923 	  _M_check_initial_position(__s, __position);
    924 	  _M_copy_from_string(__s, __position, __n, __zero, __one);
    925 	}
    926 
    927 #if __cplusplus >= 201103L
    928       /**
    929        *  Construct from a character %array.
    930        *  @param  __str  An %array of characters @a zero and @a one.
    931        *  @param  __n    The number of characters to use.
    932        *  @param  __zero The character corresponding to the value 0.
    933        *  @param  __one  The character corresponding to the value 1.
    934        *  @throw  std::invalid_argument If a character appears in the string
    935        *                                which is neither @a __zero nor @a __one.
    936        */
    937       template<typename _CharT>
    938         explicit
    939         bitset(const _CharT* __str,
    940 	       typename std::basic_string<_CharT>::size_type __n
    941 	       = std::basic_string<_CharT>::npos,
    942 	       _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'))
    943         : _Base()
    944         {
    945 	  if (!__str)
    946 	    __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)"));
    947 
    948 	  if (__n == std::basic_string<_CharT>::npos)
    949 	    __n = std::char_traits<_CharT>::length(__str);
    950 	  _M_copy_from_ptr<_CharT, std::char_traits<_CharT>>(__str, __n, 0,
    951 							     __n, __zero,
    952 							     __one);
    953 	}
    954 #endif
    955 
    956       // 23.3.5.2 bitset operations:
    957       //@{
    958       /**
    959        *  Operations on bitsets.
    960        *  @param  __rhs  A same-sized bitset.
    961        *
    962        *  These should be self-explanatory.
    963        */
    964       bitset<_Nb>&
    965       operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
    966       {
    967 	this->_M_do_and(__rhs);
    968 	return *this;
    969       }
    970 
    971       bitset<_Nb>&
    972       operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
    973       {
    974 	this->_M_do_or(__rhs);
    975 	return *this;
    976       }
    977 
    978       bitset<_Nb>&
    979       operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
    980       {
    981 	this->_M_do_xor(__rhs);
    982 	return *this;
    983       }
    984       //@}
    985       
    986       //@{
    987       /**
    988        *  Operations on bitsets.
    989        *  @param  __position  The number of places to shift.
    990        *
    991        *  These should be self-explanatory.
    992        */
    993       bitset<_Nb>&
    994       operator<<=(size_t __position) _GLIBCXX_NOEXCEPT
    995       {
    996 	if (__builtin_expect(__position < _Nb, 1))
    997 	  {
    998 	    this->_M_do_left_shift(__position);
    999 	    this->_M_do_sanitize();
   1000 	  }
   1001 	else
   1002 	  this->_M_do_reset();
   1003 	return *this;
   1004       }
   1005 
   1006       bitset<_Nb>&
   1007       operator>>=(size_t __position) _GLIBCXX_NOEXCEPT
   1008       {
   1009 	if (__builtin_expect(__position < _Nb, 1))
   1010 	  {
   1011 	    this->_M_do_right_shift(__position);
   1012 	    this->_M_do_sanitize();
   1013 	  }
   1014 	else
   1015 	  this->_M_do_reset();
   1016 	return *this;
   1017       }
   1018       //@}
   1019       
   1020       //@{
   1021       /**
   1022        *  These versions of single-bit set, reset, flip, and test are
   1023        *  extensions from the SGI version.  They do no range checking.
   1024        *  @ingroup SGIextensions
   1025        */
   1026       bitset<_Nb>&
   1027       _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT
   1028       {
   1029 	this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
   1030 	return *this;
   1031       }
   1032 
   1033       bitset<_Nb>&
   1034       _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT
   1035       {
   1036 	if (__val)
   1037 	  this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
   1038 	else
   1039 	  this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
   1040 	return *this;
   1041       }
   1042 
   1043       bitset<_Nb>&
   1044       _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT
   1045       {
   1046 	this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
   1047 	return *this;
   1048       }
   1049 
   1050       bitset<_Nb>&
   1051       _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT
   1052       {
   1053 	this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
   1054 	return *this;
   1055       }
   1056 
   1057       _GLIBCXX_CONSTEXPR bool
   1058       _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT
   1059       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
   1060 		!= static_cast<_WordT>(0)); }
   1061       //@}
   1062       
   1063       // Set, reset, and flip.
   1064       /**
   1065        *  @brief Sets every bit to true.
   1066        */
   1067       bitset<_Nb>&
   1068       set() _GLIBCXX_NOEXCEPT
   1069       {
   1070 	this->_M_do_set();
   1071 	this->_M_do_sanitize();
   1072 	return *this;
   1073       }
   1074 
   1075       /**
   1076        *  @brief Sets a given bit to a particular value.
   1077        *  @param  __position  The index of the bit.
   1078        *  @param  __val  Either true or false, defaults to true.
   1079        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
   1080        */
   1081       bitset<_Nb>&
   1082       set(size_t __position, bool __val = true)
   1083       {
   1084 	this->_M_check(__position, __N("bitset::set"));
   1085 	return _Unchecked_set(__position, __val);
   1086       }
   1087 
   1088       /**
   1089        *  @brief Sets every bit to false.
   1090        */
   1091       bitset<_Nb>&
   1092       reset() _GLIBCXX_NOEXCEPT
   1093       {
   1094 	this->_M_do_reset();
   1095 	return *this;
   1096       }
   1097 
   1098       /**
   1099        *  @brief Sets a given bit to false.
   1100        *  @param  __position  The index of the bit.
   1101        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
   1102        *
   1103        *  Same as writing @c set(pos,false).
   1104        */
   1105       bitset<_Nb>&
   1106       reset(size_t __position)
   1107       {
   1108 	this->_M_check(__position, __N("bitset::reset"));
   1109 	return _Unchecked_reset(__position);
   1110       }
   1111       
   1112       /**
   1113        *  @brief Toggles every bit to its opposite value.
   1114        */
   1115       bitset<_Nb>&
   1116       flip() _GLIBCXX_NOEXCEPT
   1117       {
   1118 	this->_M_do_flip();
   1119 	this->_M_do_sanitize();
   1120 	return *this;
   1121       }
   1122 
   1123       /**
   1124        *  @brief Toggles a given bit to its opposite value.
   1125        *  @param  __position  The index of the bit.
   1126        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
   1127        */
   1128       bitset<_Nb>&
   1129       flip(size_t __position)
   1130       {
   1131 	this->_M_check(__position, __N("bitset::flip"));
   1132 	return _Unchecked_flip(__position);
   1133       }
   1134       
   1135       /// See the no-argument flip().
   1136       bitset<_Nb>
   1137       operator~() const _GLIBCXX_NOEXCEPT
   1138       { return bitset<_Nb>(*this).flip(); }
   1139 
   1140       //@{
   1141       /**
   1142        *  @brief  Array-indexing support.
   1143        *  @param  __position  Index into the %bitset.
   1144        *  @return A bool for a <em>const %bitset</em>.  For non-const
   1145        *           bitsets, an instance of the reference proxy class.
   1146        *  @note  These operators do no range checking and throw no exceptions,
   1147        *         as required by DR 11 to the standard.
   1148        *
   1149        *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
   1150        *  resolves DR 11 (items 1 and 2), but does not do the range-checking
   1151        *  required by that DR's resolution.  -pme
   1152        *  The DR has since been changed:  range-checking is a precondition
   1153        *  (users' responsibility), and these functions must not throw.  -pme
   1154        */
   1155       reference
   1156       operator[](size_t __position)
   1157       { return reference(*this, __position); }
   1158 
   1159       _GLIBCXX_CONSTEXPR bool
   1160       operator[](size_t __position) const
   1161       { return _Unchecked_test(__position); }
   1162       //@}
   1163       
   1164       /**
   1165        *  @brief Returns a numerical interpretation of the %bitset.
   1166        *  @return  The integral equivalent of the bits.
   1167        *  @throw  std::overflow_error  If there are too many bits to be
   1168        *                               represented in an @c unsigned @c long.
   1169        */
   1170       unsigned long
   1171       to_ulong() const
   1172       { return this->_M_do_to_ulong(); }
   1173 
   1174 #if __cplusplus >= 201103L
   1175       unsigned long long
   1176       to_ullong() const
   1177       { return this->_M_do_to_ullong(); }
   1178 #endif
   1179 
   1180       /**
   1181        *  @brief Returns a character interpretation of the %bitset.
   1182        *  @return  The string equivalent of the bits.
   1183        *
   1184        *  Note the ordering of the bits:  decreasing character positions
   1185        *  correspond to increasing bit positions (see the main class notes for
   1186        *  an example).
   1187        */
   1188       template<class _CharT, class _Traits, class _Alloc>
   1189 	std::basic_string<_CharT, _Traits, _Alloc>
   1190 	to_string() const
   1191 	{
   1192 	  std::basic_string<_CharT, _Traits, _Alloc> __result;
   1193 	  _M_copy_to_string(__result, _CharT('0'), _CharT('1'));
   1194 	  return __result;
   1195 	}
   1196 
   1197       // _GLIBCXX_RESOLVE_LIB_DEFECTS
   1198       // 396. what are characters zero and one.
   1199       template<class _CharT, class _Traits, class _Alloc>
   1200 	std::basic_string<_CharT, _Traits, _Alloc>
   1201 	to_string(_CharT __zero, _CharT __one = _CharT('1')) const
   1202 	{
   1203 	  std::basic_string<_CharT, _Traits, _Alloc> __result;
   1204 	  _M_copy_to_string(__result, __zero, __one);
   1205 	  return __result;
   1206 	}
   1207 
   1208       // _GLIBCXX_RESOLVE_LIB_DEFECTS
   1209       // 434. bitset::to_string() hard to use.
   1210       template<class _CharT, class _Traits>
   1211 	std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
   1212 	to_string() const
   1213 	{ return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
   1214 
   1215       // _GLIBCXX_RESOLVE_LIB_DEFECTS
   1216       // 853. to_string needs updating with zero and one.
   1217       template<class _CharT, class _Traits>
   1218 	std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
   1219 	to_string(_CharT __zero, _CharT __one = _CharT('1')) const
   1220 	{ return to_string<_CharT, _Traits,
   1221 	                   std::allocator<_CharT> >(__zero, __one); }
   1222 
   1223       template<class _CharT>
   1224 	std::basic_string<_CharT, std::char_traits<_CharT>,
   1225 	                  std::allocator<_CharT> >
   1226 	to_string() const
   1227 	{
   1228 	  return to_string<_CharT, std::char_traits<_CharT>,
   1229 	                   std::allocator<_CharT> >();
   1230 	}
   1231 
   1232       template<class _CharT>
   1233 	std::basic_string<_CharT, std::char_traits<_CharT>,
   1234 	                  std::allocator<_CharT> >
   1235 	to_string(_CharT __zero, _CharT __one = _CharT('1')) const
   1236 	{
   1237 	  return to_string<_CharT, std::char_traits<_CharT>,
   1238 	                   std::allocator<_CharT> >(__zero, __one);
   1239 	}
   1240 
   1241       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
   1242       to_string() const
   1243       {
   1244 	return to_string<char, std::char_traits<char>,
   1245 	                 std::allocator<char> >();
   1246       }
   1247 
   1248       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
   1249       to_string(char __zero, char __one = '1') const
   1250       {
   1251 	return to_string<char, std::char_traits<char>,
   1252 	                 std::allocator<char> >(__zero, __one);
   1253       }
   1254 
   1255       // Helper functions for string operations.
   1256       template<class _CharT, class _Traits>
   1257         void
   1258         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
   1259 			 _CharT, _CharT);
   1260 
   1261       template<class _CharT, class _Traits, class _Alloc>
   1262 	void
   1263 	_M_copy_from_string(const std::basic_string<_CharT,
   1264 			    _Traits, _Alloc>& __s, size_t __pos, size_t __n,
   1265 			    _CharT __zero, _CharT __one)
   1266 	{ _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n,
   1267 					    __zero, __one); }
   1268 
   1269       template<class _CharT, class _Traits, class _Alloc>
   1270 	void
   1271         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&,
   1272 			  _CharT, _CharT) const;
   1273 
   1274       // NB: Backward compat.
   1275       template<class _CharT, class _Traits, class _Alloc>
   1276 	void
   1277 	_M_copy_from_string(const std::basic_string<_CharT,
   1278 			    _Traits, _Alloc>& __s, size_t __pos, size_t __n)
   1279 	{ _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); }
   1280 
   1281       template<class _CharT, class _Traits, class _Alloc>
   1282 	void
   1283         _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const
   1284 	{ _M_copy_to_string(__s, _CharT('0'), _CharT('1')); }
   1285 
   1286       /// Returns the number of bits which are set.
   1287       size_t
   1288       count() const _GLIBCXX_NOEXCEPT
   1289       { return this->_M_do_count(); }
   1290 
   1291       /// Returns the total number of bits.
   1292       _GLIBCXX_CONSTEXPR size_t
   1293       size() const _GLIBCXX_NOEXCEPT
   1294       { return _Nb; }
   1295 
   1296       //@{
   1297       /// These comparisons for equality/inequality are, well, @e bitwise.
   1298       bool
   1299       operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
   1300       { return this->_M_is_equal(__rhs); }
   1301 
   1302       bool
   1303       operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
   1304       { return !this->_M_is_equal(__rhs); }
   1305       //@}
   1306       
   1307       /**
   1308        *  @brief Tests the value of a bit.
   1309        *  @param  __position  The index of a bit.
   1310        *  @return  The value at @a pos.
   1311        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
   1312        */
   1313       bool
   1314       test(size_t __position) const
   1315       {
   1316 	this->_M_check(__position, __N("bitset::test"));
   1317 	return _Unchecked_test(__position);
   1318       }
   1319 
   1320       // _GLIBCXX_RESOLVE_LIB_DEFECTS
   1321       // DR 693. std::bitset::all() missing.
   1322       /**
   1323        *  @brief Tests whether all the bits are on.
   1324        *  @return  True if all the bits are set.
   1325        */
   1326       bool
   1327       all() const _GLIBCXX_NOEXCEPT
   1328       { return this->template _M_are_all<_Nb>(); }
   1329 
   1330       /**
   1331        *  @brief Tests whether any of the bits are on.
   1332        *  @return  True if at least one bit is set.
   1333        */
   1334       bool
   1335       any() const _GLIBCXX_NOEXCEPT
   1336       { return this->_M_is_any(); }
   1337 
   1338       /**
   1339        *  @brief Tests whether any of the bits are on.
   1340        *  @return  True if none of the bits are set.
   1341        */
   1342       bool
   1343       none() const _GLIBCXX_NOEXCEPT
   1344       { return !this->_M_is_any(); }
   1345 
   1346       //@{
   1347       /// Self-explanatory.
   1348       bitset<_Nb>
   1349       operator<<(size_t __position) const _GLIBCXX_NOEXCEPT
   1350       { return bitset<_Nb>(*this) <<= __position; }
   1351 
   1352       bitset<_Nb>
   1353       operator>>(size_t __position) const _GLIBCXX_NOEXCEPT
   1354       { return bitset<_Nb>(*this) >>= __position; }
   1355       //@}
   1356       
   1357       /**
   1358        *  @brief  Finds the index of the first "on" bit.
   1359        *  @return  The index of the first bit set, or size() if not found.
   1360        *  @ingroup SGIextensions
   1361        *  @sa  _Find_next
   1362        */
   1363       size_t
   1364       _Find_first() const _GLIBCXX_NOEXCEPT
   1365       { return this->_M_do_find_first(_Nb); }
   1366 
   1367       /**
   1368        *  @brief  Finds the index of the next "on" bit after prev.
   1369        *  @return  The index of the next bit set, or size() if not found.
   1370        *  @param  __prev  Where to start searching.
   1371        *  @ingroup SGIextensions
   1372        *  @sa  _Find_first
   1373        */
   1374       size_t
   1375       _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT
   1376       { return this->_M_do_find_next(__prev, _Nb); }
   1377     };
   1378 
   1379   // Definitions of non-inline member functions.
   1380   template<size_t _Nb>
   1381     template<class _CharT, class _Traits>
   1382       void
   1383       bitset<_Nb>::
   1384       _M_copy_from_ptr(const _CharT* __s, size_t __len,
   1385 		       size_t __pos, size_t __n, _CharT __zero, _CharT __one)
   1386       {
   1387 	reset();
   1388 	const size_t __nbits = std::min(_Nb, std::min(__n, size_t(__len - __pos)));
   1389 	for (size_t __i = __nbits; __i > 0; --__i)
   1390 	  {
   1391 	    const _CharT __c = __s[__pos + __nbits - __i];
   1392 	    if (_Traits::eq(__c, __zero))
   1393 	      ;
   1394 	    else if (_Traits::eq(__c, __one))
   1395 	      _Unchecked_set(__i - 1);
   1396 	    else
   1397 	      __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
   1398 	  }
   1399       }
   1400 
   1401   template<size_t _Nb>
   1402     template<class _CharT, class _Traits, class _Alloc>
   1403       void
   1404       bitset<_Nb>::
   1405       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s,
   1406 			_CharT __zero, _CharT __one) const
   1407       {
   1408 	__s.assign(_Nb, __zero);
   1409 	for (size_t __i = _Nb; __i > 0; --__i)
   1410 	  if (_Unchecked_test(__i - 1))
   1411 	    _Traits::assign(__s[_Nb - __i], __one);
   1412       }
   1413 
   1414   // 23.3.5.3 bitset operations:
   1415   //@{
   1416   /**
   1417    *  @brief  Global bitwise operations on bitsets.
   1418    *  @param  __x  A bitset.
   1419    *  @param  __y  A bitset of the same size as @a __x.
   1420    *  @return  A new bitset.
   1421    *
   1422    *  These should be self-explanatory.
   1423   */
   1424   template<size_t _Nb>
   1425     inline bitset<_Nb>
   1426     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
   1427     {
   1428       bitset<_Nb> __result(__x);
   1429       __result &= __y;
   1430       return __result;
   1431     }
   1432 
   1433   template<size_t _Nb>
   1434     inline bitset<_Nb>
   1435     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
   1436     {
   1437       bitset<_Nb> __result(__x);
   1438       __result |= __y;
   1439       return __result;
   1440     }
   1441 
   1442   template <size_t _Nb>
   1443     inline bitset<_Nb>
   1444     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
   1445     {
   1446       bitset<_Nb> __result(__x);
   1447       __result ^= __y;
   1448       return __result;
   1449     }
   1450   //@}
   1451 
   1452   //@{
   1453   /**
   1454    *  @brief Global I/O operators for bitsets.
   1455    *
   1456    *  Direct I/O between streams and bitsets is supported.  Output is
   1457    *  straightforward.  Input will skip whitespace, only accept @a 0 and @a 1
   1458    *  characters, and will only extract as many digits as the %bitset will
   1459    *  hold.
   1460   */
   1461   template<class _CharT, class _Traits, size_t _Nb>
   1462     std::basic_istream<_CharT, _Traits>&
   1463     operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
   1464     {
   1465       typedef typename _Traits::char_type          char_type;
   1466       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
   1467       typedef typename __istream_type::ios_base    __ios_base;
   1468 
   1469       std::basic_string<_CharT, _Traits> __tmp;
   1470       __tmp.reserve(_Nb);
   1471 
   1472       // _GLIBCXX_RESOLVE_LIB_DEFECTS
   1473       // 303. Bitset input operator underspecified
   1474       const char_type __zero = __is.widen('0');
   1475       const char_type __one = __is.widen('1');
   1476 
   1477       typename __ios_base::iostate __state = __ios_base::goodbit;
   1478       typename __istream_type::sentry __sentry(__is);
   1479       if (__sentry)
   1480 	{
   1481 	  __try
   1482 	    {
   1483 	      for (size_t __i = _Nb; __i > 0; --__i)
   1484 		{
   1485 		  static typename _Traits::int_type __eof = _Traits::eof();
   1486 		  
   1487 		  typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
   1488 		  if (_Traits::eq_int_type(__c1, __eof))
   1489 		    {
   1490 		      __state |= __ios_base::eofbit;
   1491 		      break;
   1492 		    }
   1493 		  else
   1494 		    {
   1495 		      const char_type __c2 = _Traits::to_char_type(__c1);
   1496 		      if (_Traits::eq(__c2, __zero))
   1497 			__tmp.push_back(__zero);
   1498 		      else if (_Traits::eq(__c2, __one))
   1499 			__tmp.push_back(__one);
   1500 		      else if (_Traits::
   1501 			       eq_int_type(__is.rdbuf()->sputbackc(__c2),
   1502 					   __eof))
   1503 			{
   1504 			  __state |= __ios_base::failbit;
   1505 			  break;
   1506 			}
   1507 		    }
   1508 		}
   1509 	    }
   1510 	  __catch(__cxxabiv1::__forced_unwind&)
   1511 	    {
   1512 	      __is._M_setstate(__ios_base::badbit);		
   1513 	      __throw_exception_again;
   1514 	    }
   1515 	  __catch(...)
   1516 	    { __is._M_setstate(__ios_base::badbit); }
   1517 	}
   1518 
   1519       if (__tmp.empty() && _Nb)
   1520 	__state |= __ios_base::failbit;
   1521       else
   1522 	__x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb,
   1523 				__zero, __one);
   1524       if (__state)
   1525 	__is.setstate(__state);
   1526       return __is;
   1527     }
   1528 
   1529   template <class _CharT, class _Traits, size_t _Nb>
   1530     std::basic_ostream<_CharT, _Traits>&
   1531     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   1532 	       const bitset<_Nb>& __x)
   1533     {
   1534       std::basic_string<_CharT, _Traits> __tmp;
   1535 
   1536       // _GLIBCXX_RESOLVE_LIB_DEFECTS
   1537       // 396. what are characters zero and one.
   1538       const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
   1539       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
   1540       return __os << __tmp;
   1541     }
   1542   //@}
   1543 
   1544 _GLIBCXX_END_NAMESPACE_CONTAINER
   1545 } // namespace std
   1546 
   1547 #undef _GLIBCXX_BITSET_WORDS
   1548 #undef _GLIBCXX_BITSET_BITS_PER_WORD
   1549 #undef _GLIBCXX_BITSET_BITS_PER_ULL
   1550 
   1551 #if __cplusplus >= 201103L
   1552 
   1553 #include <bits/functional_hash.h>
   1554 
   1555 namespace std _GLIBCXX_VISIBILITY(default)
   1556 {
   1557 _GLIBCXX_BEGIN_NAMESPACE_VERSION
   1558 
   1559   // DR 1182.
   1560   /// std::hash specialization for bitset.
   1561   template<size_t _Nb>
   1562     struct hash<_GLIBCXX_STD_C::bitset<_Nb>>
   1563     : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>>
   1564     {
   1565       size_t
   1566       operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept
   1567       {
   1568 	const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__;
   1569 	return std::_Hash_impl::hash(__b._M_getdata(), __clength);
   1570       }
   1571     };
   1572 
   1573   template<>
   1574     struct hash<_GLIBCXX_STD_C::bitset<0>>
   1575     : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>>
   1576     {
   1577       size_t
   1578       operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept
   1579       { return 0; }
   1580     };
   1581 
   1582 _GLIBCXX_END_NAMESPACE_VERSION
   1583 } // namespace
   1584 
   1585 #endif // C++11
   1586 
   1587 #ifdef _GLIBCXX_DEBUG
   1588 # include <debug/bitset>
   1589 #endif
   1590 
   1591 #ifdef _GLIBCXX_PROFILE
   1592 # include <profile/bitset>
   1593 #endif
   1594 
   1595 #endif /* _GLIBCXX_BITSET */
   1596