std_bitset.h

gcc-you can use this code to learn something about gcc, and inquire further into linux,

      _M_do_left_shift(size_t __shift) { _M_w <<= __shift; }

      void
      _M_do_right_shift(size_t __shift) { _M_w >>= __shift; }

      void
      _M_do_flip() { _M_w = ~_M_w; }

      void
      _M_do_set() { _M_w = ~static_cast<_WordT>(0); }

      void
      _M_do_reset() { _M_w = 0; }

      bool
      _M_is_equal(const _Base_bitset<1>& __x) const
      { return _M_w == __x._M_w; }

      bool
      _M_is_any() const { return _M_w != 0; }

      size_t
      _M_do_count() const
      {
	size_t __result = 0;
	const unsigned char* __byte_ptr = (const unsigned char*)&_M_w;
	const unsigned char* __end_ptr
	  = ((const unsigned char*)&_M_w)+sizeof(_M_w);
	while ( __byte_ptr < __end_ptr )
	  {
	    __result += _S_bit_count[*__byte_ptr];
	    __byte_ptr++;
	  }
	return __result;
      }

      unsigned long
      _M_do_to_ulong() const { return _M_w; }

      size_t
      _M_do_find_first(size_t __not_found) const;

      // find the next "on" bit that follows "prev"
      size_t
      _M_do_find_next(size_t __prev, size_t __not_found) const;
    };


  /**
   *  @if maint
   *  Base class, specialization for no storage (zero-length %bitset).
   *
   *  See documentation for bitset.
   *  @endif
  */
  template<>
    struct _Base_bitset<0>
    {
      typedef unsigned long _WordT;

      _Base_bitset() {}
      _Base_bitset(unsigned long) {}

      static size_t
      _S_whichword(size_t __pos )
      { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; }

      static size_t
      _S_whichbyte(size_t __pos )
      { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; }

      static size_t
      _S_whichbit(size_t __pos )
      {  return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; }

      static _WordT
      _S_maskbit(size_t __pos )
      { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }

      // This would normally give access to the data.  The bounds-checking
      // in the bitset class will prevent the user from getting this far,
      // but (1) it must still return an lvalue to compile, and (2) the
      // user might call _Unchecked_set directly, in which case this /needs/
      // to fail.  Let's not penalize zero-length users unless they actually
      // make an unchecked call; all the memory ugliness is therefore
      // localized to this single should-never-get-this-far function.
      _WordT&
      _M_getword(size_t) const
      { __throw_out_of_range("bitset -- zero-length"); return *new _WordT; }

      _WordT
      _M_hiword() const { return 0; }

      void
      _M_do_and(const _Base_bitset<0>&) { }

      void
      _M_do_or(const _Base_bitset<0>&)  { }

      void
      _M_do_xor(const _Base_bitset<0>&) { }

      void
      _M_do_left_shift(size_t) { }

      void
      _M_do_right_shift(size_t) { }

      void
      _M_do_flip() { }

      void
      _M_do_set() { }

      void
      _M_do_reset() { }

      // Are all empty bitsets equal to each other?  Are they equal to
      // themselves?  How to compare a thing which has no state?  What is
      // the sound of one zero-length bitset clapping?
      bool
      _M_is_equal(const _Base_bitset<0>&) const { return true; }

      bool
      _M_is_any() const { return false; }

      size_t
      _M_do_count() const { return 0; }

      unsigned long
      _M_do_to_ulong() const { return 0; }

      // Normally "not found" is the size, but that could also be
      // misinterpreted as an index in this corner case.  Oh well.
      size_t
      _M_do_find_first(size_t) const { return 0; }

      size_t
      _M_do_find_next(size_t, size_t) const { return 0; }
    };


  // Helper class to zero out the unused high-order bits in the highest word.
  template<size_t _Extrabits>
    struct _Sanitize
    {
      static void _S_do_sanitize(unsigned long& __val)
      { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
    };

  template<>
    struct _Sanitize<0>
    { static void _S_do_sanitize(unsigned long) { } };


  /**
   *  @brief  The %bitset class represents a @e fixed-size sequence of bits.
   *
   *  @ingroup Containers
   *
   *  (Note that %bitset does @e not meet the formal requirements of a
   *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
   *
   *  The template argument, @a Nb, may be any non-negative number,
   *  specifying the number of bits (e.g., "0", "12", "1024*1024").
   *
   *  In the general unoptimized case, storage is allocated in word-sized
   *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
   *  words will be used for storage.  B - Nb%B bits are unused.  (They are
   *  the high-order bits in the highest word.)  It is a class invariant
   *  that those unused bits are always zero.
   *
   *  If you think of %bitset as "a simple array of bits," be aware that
   *  your mental picture is reversed:  a %bitset behaves the same way as
   *  bits in integers do, with the bit at index 0 in the "least significant
   *  / right-hand" position, and the bit at index Nb-1 in the "most
   *  significant / left-hand" position.  Thus, unlike other containers, a
   *  %bitset's index "counts from right to left," to put it very loosely.
   *
   *  This behavior is preserved when translating to and from strings.  For
   *  example, the first line of the following program probably prints
   *  "b('a') is 0001100001" on a modern ASCII system.
   *
   *  @code
   *     #include <bitset>
   *     #include <iostream>
   *     #include <sstream>
   *
   *     using namespace std;
   *
   *     int main()
   *     {
   *         long         a = 'a';
   *         bitset<10>   b(a);
   *
   *         cout << "b('a') is " << b << endl;
   *
   *         ostringstream s;
   *         s << b;
   *         string  str = s.str();
   *         cout << "index 3 in the string is " << str[3] << " but\n"
   *              << "index 3 in the bitset is " << b[3] << endl;
   *     }
   *  @endcode
   *
   *  Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23
   *  for a description of extensions.
   *
   *  @if maint
   *  Most of the actual code isn't contained in %bitset<> itself, but in the
   *  base class _Base_bitset.  The base class works with whole words, not with
   *  individual bits.  This allows us to specialize _Base_bitset for the
   *  important special case where the %bitset is only a single word.
   *
   *  Extra confusion can result due to the fact that the storage for
   *  _Base_bitset @e is a regular array, and is indexed as such.  This is
   *  carefully encapsulated.
   *  @endif
  */
  template<size_t _Nb>
    class bitset : private _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)>
  {
  private:
    typedef _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> _Base;
    typedef unsigned long _WordT;

    void
    _M_do_sanitize()
    {
      _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>::
          _S_do_sanitize(this->_M_hiword());
    }

  public:
    /**
     *  This encapsulates the concept of a single bit.  An instance of this
     *  class is a proxy for an actual bit; this way the individual bit
     *  operations are done as faster word-size bitwise instructions.
     *
     *  Most users will never need to use this class directly; conversions
     *  to and from bool are automatic and should be transparent.  Overloaded
     *  operators help to preserve the illusion.
     *
     *  (On a typical system, this "bit %reference" is 64 times the size of
     *  an actual bit.  Ha.)
    */
    class reference
    {
      friend class bitset;

      _WordT *_M_wp;
      size_t _M_bpos;

      // left undefined
      reference();

    public:
      reference(bitset& __b, size_t __pos)
      {
	_M_wp = &__b._M_getword(__pos);
	_M_bpos = _Base::_S_whichbit(__pos);
      }

      ~reference() { }

      // for b[i] = __x;
      reference&
      operator=(bool __x)
      {
	if ( __x )
	  *_M_wp |= _Base::_S_maskbit(_M_bpos);
	else
	  *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
	return *this;
      }

      // for b[i] = b[__j];
      reference&
      operator=(const reference& __j)
      {
	if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) )
	  *_M_wp |= _Base::_S_maskbit(_M_bpos);
	else
	  *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
	return *this;
      }

      // flips the bit
      bool
      operator~() const
      { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }

      // for __x = b[i];
      operator bool() const
      { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }

      // for b[i].flip();
      reference&
      flip()
      {
	*_M_wp ^= _Base::_S_maskbit(_M_bpos);
	return *this;
      }
    };
    friend class reference;

    // 23.3.5.1 constructors:
    /// All bits set to zero.
    bitset() { }

    /// Initial bits bitwise-copied from a single word (others set to zero).
    bitset(unsigned long __val) : _Base(__val)
    { _M_do_sanitize(); }

    /**
     *  @brief  Use a subset of a string.
     *  @param  s  A string of '0' and '1' characters.
     *  @param  pos  Index of the first character in @a s to use; defaults
     *               to zero.
     *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
     *  @throw  std::invalid_argument  If a character appears in the string
     *                                 which is neither '0' nor '1'.
    */
    template<class _CharT, class _Traits, class _Alloc>
      explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
		      size_t __pos = 0) : _Base()
      {
	if (__pos > __s.size())
	  __throw_out_of_range("bitset -- initial position is larger than "
	                       "the string itself");
	_M_copy_from_string(__s, __pos,
			    basic_string<_CharT, _Traits, _Alloc>::npos);
      }

    /**
     *  @brief  Use a subset of a string.
     *  @param  s  A string of '0' and '1' characters.
     *  @param  pos  Index of the first character in @a s to use.
     *  @param  n    The number of characters to copy.
     *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
     *  @throw  std::invalid_argument  If a character appears in the string
     *                                 which is neither '0' nor '1'.
    */
    template<class _CharT, class _Traits, class _Alloc>
      bitset(const basic_string<_CharT, _Traits, _Alloc>& __s,
	     size_t __pos, size_t __n) : _Base()
      {
	if (__pos > __s.size())
	  __throw_out_of_range("bitset -- initial position is larger than "
	                       "the string itself");
	_M_copy_from_string(__s, __pos, __n);
      }

    // 23.3.5.2 bitset operations:
    //@{
    /**
     *  @brief  Operations on bitsets.
     *  @param  rhs  A same-sized bitset.
     *
     *  These should be self-explanatory.
    */
    bitset<_Nb>&
    operator&=(const bitset<_Nb>& __rhs)
    {
      this->_M_do_and(__rhs);
      return *this;
    }

    bitset<_Nb>&
    operator|=(const bitset<_Nb>& __rhs)
    {
      this->_M_do_or(__rhs);
      return *this;
    }

    bitset<_Nb>&
    operator^=(const bitset<_Nb>& __rhs)
    {
      this->_M_do_xor(__rhs);
      return *this;
    }
    //@}

    //@{
    /**
     *  @brief  Operations on bitsets.
     *  @param  pos  The number of places to shift.
     *
     *  These should be self-explanatory.
    */
    bitset<_Nb>&
    operator<<=(size_t __pos)
    {
      if (__builtin_expect(__pos < _Nb, 1))
        {
          this->_M_do_left_shift(__pos);
          this->_M_do_sanitize();
        }
      else
	this->_M_do_reset();
      return *this;
    }

    bitset<_Nb>&
    operator>>=(size_t __pos)
    {
      if (__builtin_expect(__pos < _Nb, 1))
        {
          this->_M_do_right_shift(__pos);
          this->_M_do_sanitize();
        }
      else
	this->_M_do_reset();
      return *this;
    }
    //@}

    //@{