libstdc++-v3/include/std/bitset

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