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