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