libstdc++-v3/include/std/bitset

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