libstdc++-v3/include/std/bitset

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