// bitset standard header
#ifndef _BITSET_
#define _BITSET_
#include <climits>
#include <istream>
// TEMPLATE CLASS bitset
_STD_BEGIN
template<size_t_N> class bitset {
typedef unsigned long _T;
public:
class reference {
friend class bitset<_N>;
public:
reference& operator=(bool _X)
{_Pbs->set(_Off, _X);
return (*this); }
reference& operator=(const reference& _Bs)
{_Pbs->set(_Off, bool(_Bs));
return (*this); }
reference& flip()
{_Pbs->flip(_Off);
return (*this); }
bool operator~() const
{return (!_Pbs->test(_Off)); }
operator bool() const
{return (_Pbs->test(_Off)); }
private:
reference(bitset<_N>& _X, size_t _P)
: _Pbs(&_X), _Off(_P) {}
bitset<_N> *_Pbs;
size_t _Off;
};
bool at(size_t _P) const
{if (_N <= _P)
_Xran();
return (test(_P)); }
reference at(size_t _P)
{if (_N <= _P)
_Xran();
return (reference(*this, _P)); }
const bool operator[](size_t _P) const
{return (test(_P)); }
reference operator[](size_t _P)
{return (reference(*this, _P)); }
bitset()
{_Tidy(); }
bitset(unsigned long _X)
{_Tidy();
for (size_t _P = 0; _X != 0 && _P < _N; _X >>= 1, ++_P)
if (_X & 1)
set(_P); }
explicit bitset(const string& _S, size_t _P = 0,
size_t _L = (size_t)(-1))
{if (_S.size() < _P)
_Xran();
if (_S.size() - _P < _L)
_L = _S.size() - _P;
if (_N < _L)
_L = _N;
_Tidy(), _P += _L;
for (size_t _I = 0; _I < _L; ++_I)
if (_S[--_P] == '1')
set(_I);
else if (_S[_P] != '0')
_Xinv(); }
bitset<_N>& operator&=(const bitset<_N>& _R)
{for (int _I = _Nw; 0 <= _I; --_I)
_A[_I] &= _R._W(_I);
return (*this); }
bitset<_N>& operator|=(const bitset<_N>& _R)
{for (int _I = _Nw; 0 <= _I; --_I)
_A[_I] |= _R._W(_I);
return (*this); }
bitset<_N>& operator^=(const bitset<_N>& _R)
{for (int _I = _Nw; 0 <= _I; --_I)
_A[_I] ^= _R._W(_I);
return (*this); }
bitset<_N>& operator<<=(size_t _P)
{if (_P < 0)
return (*this >>= -_P);
const int _D = _P / _Nb;
if (_D != 0)
for (int _I = _Nw; 0 <= _I; --_I)
_A[_I] = _D <= _I ? _A[_I - _D] :0;
if ((_P %= _Nb) != 0)
{for (int _I = _NW; 0 < _I; --_I
_A[_I] = (_A[_I] << _P)
| (_A[_I - 1] >> (_Nb - _P));
_A[0] <<= _P, _Trim(); }
return (*this); }
bitset<_N>& operator>>=(size_t _P)
{if (_P < 0)
return (*this <<= -_P);
const int _D = _P / _Nb;
if (_D !=0)
for (int _I = 0; _I <= _Nw; ++_I)
_A[_I] = _D <= _Nw - _I ? _A[_I + _D] : 0;
if ((_P %= _Nb) != 0)
{for (int _I = 0; _I < _Nw; ++_I)
_A[_I] = (_A[_I] >> _P)
| (_A[_I + 1] << (_Nb - _P));
_A[_Nw] >>= _P; }
return (*this); }
bitset<_N>& set()
{_Tidy(~(_T)0);
return (*this); }
bitset<_N>& set(size_t _P, bool _X = true)
{if (_N <= _P)
_Xran();
if (_X)
_A[_P / _Nb] |= (_T)1 << _P % _Nb;
else
_A[_P / _Nb] &= ~((_T)1 << _P % _Nb);
return (*this); }
bitset<_N>& reset()
{_Tidy();
return (*this); }
bitset<_N>& reset(size_t _P)
{return (set(_P, 0)); }
bitset<_N> operator~() const
{return (bitset<_N>(*this).flip()); }
bitset<_N>& flip()
{for (int _I = _Nw; 0 <= _I; --_I)
_A[_I] = ~_A[_I];
_Trim();
return (*this); }
bitset<_N>& flip(size_t _P)
{if (_N <= _P)
_Xran();
_A[_P / _Nb] ^= (_T)1 << _P % _Nb;
return (*this); }
unsigned long to_ulong() const
{enum {_Assertion = 1 /
(sizeof (unsigned long) % sizeof (_T) == 0)};
int _I = _Nw;
for (; sizeof (unsigned long) / sizeof (_T) <= _I; -- _I)
if (_A[_I] != 0)
_Xoflo();
unsigned long _V = _A[_I];
for (; 0<= -- _I; )
_V = _V << _Nb | _A[_I];
return (_V); }
string to_string() const
{string _S;
_S.reserve(_N);
for (size_t_P = N; 0 < _P; )
_S += test(--_P) ? '1' : '0';
return (_S); }
size_t count() const
{size_t_V = 0;
for (int _I = _Nw; 0 <= _I; --_I)
for (_T _X = _A[_I]; X != 0; _X >>= 4)
_V += "\0\1\1\2\1\2\2\3"
"\1\2\2\3\2\3\3\4"[_X & 0xF];
return (_V); }
size_t size() const
{return (_N); }
bool operator==(const bitset<_N>& _R) const
{for (int _I = _Nw; 0 <= _I; --_I)
if(_A[_I] != _R._W(_I))
return (false);
return (true); }
bool operator!=(const bitset<_N>& _R) const
{return (!(*this == _R)); }
bool test(size_t_P) const
{if (_N <= _P)
_Xran();
return ((_A[_P / _Nb] & ((_T)1 << _P % _Nb)) != 0); }
bool any() const
{for (int _I = _Nw; 0 <= _I; --_I)
if (_A[_I] !=0)
return (true);
return (false); }
bool none() const
{return (!any());}
bitset<_N> operator<<(size_t _R) const
{return (bitset<_N>(*this) <<= _R); }
bitset<_N> operator>>(size_t _R) const
{return (bitset<_N>(*this) >>= _R); }
friend bitset<_N> operator&(const bitset<_N>& _L,
const bitset<_N>& _R)
{return (bitset<_N>(_L) &= _R); }
friend bitset<_N> operator|(const bitset<_N>&_L,
const bitset<_N>& _R)
{return (bitset<_N>(_L) |= _R); }
friend bitset<_N> operator^(const bitset<_N>& _L,
const bitset<_N>& _R)
{return (bitset<_N>(_L) ^= _R); }
friend istream& operator>>(istream& _I, bitset<_N>& _R)
{ios_base::iostate _St = ios_base::goodbit;
bool _Chgd = false;
string _X;
size_t _M = _N;
_X.reserve(_M);
if (_M == (size_t)(-1))
--_M;
if (_I.ipfx())
{_TRY_I0_BEGIN
int _Ch;
while (0 < _M)
if ((_Ch = _I.rdbuf()->sbumpc()) == EOF)
{_St |= ios_base::eofbit;
break; }
else if (_Ch != '0' && _Ch != '1')
{_I.rdbuf()->sputbackc(_Ch);
break; }
else
_X += (char)_Ch, _Chgd = true, --_M;
_CATCH_I0_(I); }
if (!_Chgd)
_St |= ios_base::failbit;
_I.isfx();
if (_St)
_I.setstate(_St);
_R = _X;
return (_I); }
friend ostream& operator<<(ostream& _0, const bitset<_N>& _R)
{return (_0 << _R.to_string()); }
_T _W(size_t _I) const
{return (_A[_I]); }
private:
enum {_Nb = CHAR_BITS * sizeof (_T),
_Nw = _N == 0 ? 0 : (_N - 1) / _Nb};
void _Tidy(_T _X = 0)
{for (int _I = _Nw; 0 <= _I; --_I)
_A[_I] = _X;
if (_X != 0)
_Trim(); }
void _Trim()
{if (_N % _Nb != 0)
_A[_Nw] &= ((_T)1 << _N % _Nb) - 1; }
void _Xinv() const
{invalid_argument("invalid bitset<N> char")._Raise(); }
void _Xoflo() const
{overflow_error(
"bitset<N> conversion overflow")._Raise(); }
void _Xran() const
{out_of_range("invalid bitset<N> position")._Raise(); }
_T _A[_Nw + 1];
};
_STD_END
#endif /* _BITSET */