#include "bitset.h"
begin_gtl_namespace
begin_gdb_namespace
//默认构造
Bitset::Bitset() {
_Array = 0;
_Bits = _Bitsperword;//默认为32
int words = calculateWords() + 1;
_Array = new _Ty[words];
for (int i = 0; i < words; ++i)
_Array[i] = 0;
}
//传入最大的位数,每位默认是0
Bitset::Bitset(int nBits) {
_Bits = nBits;
_Array = 0;
int words = calculateWords() + 1;
_Array = new _Ty[words];
for (int i = 0; i < words; ++i)
_Array[i] = 0;
}
Bitset::~Bitset() {
_Bits = 0;
if (_Array)
delete[] _Array;
}
//直接整数转化成二进制,赋值给Bitset,最高低放在[0]位置
Bitset::Bitset(unsigned long long _Val) {
_Array = 0;
reset(_Val);
}
//拷贝构造函数
Bitset::Bitset(const Bitset & b) {
_Bits = b._Bits;//最大有效的Bit个数
int words = calculateWords() + 1;
_Array = new _Ty[words];
memcpy(_Array, b._Array, words * sizeof(_Ty));
}
Bitset::Bitset(const std::string & str, size_t _Pos, size_t _Count) {
_Bits = 0;
_Array = 0;
reset(str, _Pos, _Count);
}
Bitset::Bitset(const char * str) {
_Bits = 0;
_Array = 0;
reset(str);
}
int Bitset::calculateWords() const {//return number of words - 1
return (_Bits == 0 ? 0 : (_Bits - 1) / _Bitsperword);
}
void Bitset::tidy(Bitset::_Ty _Wordval ) { // set all words to _Wordval
ptrdiff_t _Words = calculateWords();
if (_Array) delete[] _Array;
_Array = new _Ty[_Words + 1];
for (ptrdiff_t _Wpos = _Words; 0 <= _Wpos; --_Wpos)
_Array[_Wpos] = _Wordval;
if (_Wordval != 0)
trim();
}
void Bitset::trim() { // clear any trailing bits in last word
if (_Bits == 0 || _Bits % _Bitsperword != 0) {
ptrdiff_t _Words = calculateWords();
_Array[_Words] &= ((_Ty)1 << _Bits % _Bitsperword) - 1;
}
}
Bitset::_Ty Bitset::getWord(size_t _Wpos) const { // get word at _Wpos
return (_Array[_Wpos]);
}
size_t Bitset::size() const { // return size of bitset
return (_Bits);
}
//返回设置的位数
size_t Bitset::count() const { // count number of set bits
const char *const _Bitsperbyte =
"\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4"
"\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
"\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
"\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
"\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
"\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
"\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
"\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
"\1\2\2\3\2\3\3\4\2\3\3\4\3\4\4\5"
"\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
"\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
"\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
"\2\3\3\4\3\4\4\5\3\4\4\5\4\5\5\6"
"\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
"\3\4\4\5\4\5\5\6\4\5\5\6\5\6\6\7"
"\4\5\5\6\5\6\6\7\5\6\6\7\6\7\7\x8";
const unsigned char *_Ptr =
(const unsigned char *)(const void *)_Array;
const unsigned char *const _End = _Ptr + sizeof(_Array);
size_t _Val = 0;
for (; _Ptr != _End; ++_Ptr)
_Val += _Bitsperbyte[*_Ptr];
return (_Val);
}
bool Bitset::subscript(size_t _Pos) const { // subscript nonmutable sequence
return ((_Array[_Pos / _Bitsperword]
& ((_Ty)1 << _Pos % _Bitsperword)) != 0);
}
bool Bitset::get(size_t pos) const {
return subscript(pos);
}
//设置指定位置为0或1,true表示1,false表示0,如果pos大于数组长度,则自动扩展
void Bitset::set(size_t _Pos, bool _Val ) {
if (_Bits <= _Pos) {
/*int oldWords = calculateWords() + 1;
_Bits = _Pos + 1;
int newWords = calculateWords() + 1;
if (oldWords < newWords) {
_Ty * newArray = new _Ty[newWords];
memcpy(newArray, _Array, sizeof(_Ty)*oldWords);
for (int i = oldWords; i < newWords; ++i)
newArray[i] = 0;
delete[] _Array;
_Array = newArray;
}*/
resize(_Pos + 1);
}
if (_Val)
_Array[_Pos / _Bitsperword] |= (_Ty)1 << _Pos % _Bitsperword;
else
_Array[_Pos / _Bitsperword] &= ~((_Ty)1 << _Pos % _Bitsperword);
}
//将位数组转换成整数,最低位放在[0]位置
//例如数组中存放的1011,则返回13,而不是返回11
unsigned long long Bitset::to_ullong() const { // convert bitset to unsigned long long
static_assert(sizeof(unsigned long long) % sizeof(_Ty) == 0,
"unsigned long long not multiple of _Ty");
ptrdiff_t _Wpos = calculateWords();
for (; (ptrdiff_t)(sizeof(unsigned long long) / sizeof(_Ty)) <= _Wpos;
--_Wpos)
if (_Array[_Wpos] != 0)
_Xoverflow_error("Bitset overflow"); // fail if any high-order words are nonzero
unsigned long long _Val = _Array[_Wpos];
for (; 0 <= --_Wpos; )
_Val = ((_Val << (_Bitsperword - 1)) << 1) | _Array[_Wpos];
return (_Val);
}
bool Bitset::test(size_t _Pos) const { // test if bit at _Pos is set
if (_Bits <= _Pos)
_Xoverflow_error("Bitset overflow"); // _Pos off end
return (subscript(_Pos));
}
bool Bitset::any() const { // test if any bits are set
ptrdiff_t _Words = calculateWords();
for (ptrdiff_t _Wpos = _Words; 0 <= _Wpos; --_Wpos)
if (_Array[_Wpos] != 0)
return (true);
return (false);
}
bool Bitset::none() const { // test if no bits are set
return (!any());
}
bool Bitset::all() const { // test if all bits set
return (count() == size());
}
std::string Bitset::to_string() const { // convert bitset to string
std::string _Str;
typename std::string::size_type _Pos;
_Str.reserve(_Bits);
for (_Pos = _Bits; 0 < _Pos; )
if (test(--_Pos))
_Str += '1';
else
_Str += '0';
return (_Str);
}
//直接整数转化成二进制,赋值给Bitset,最高位放在[0]位置
Bitset& Bitset::operator = (const Bitset& b) {
if (_Bits != b._Bits)//最大有效的Bit个数
resize(b._Bits);
int words = calculateWords() + 1;
memcpy(_Array, b._Array, words * sizeof(_Ty));
return *this;
}
//直接整数转化成二进制,赋值给Bitset,最高位放在[0]位置
Bitset& Bitset::operator = (unsigned long long ull) {
reset(ull);
return *this;
}
//返回指定位置的值,如果pos大于位数组长度,自动拓展
bool Bitset::operator [] (const size_t pos) {
return subscript(pos);
}
//测试两个Bitset是否相等
bool Bitset::operator == (const Bitset & b) {
if (_Bits == b._Bits) {
return memcmp(_Array, b._Array, (calculateWords()+1)*sizeof(_Ty))==0;
}
return false;
}
bool Bitset::operator != (const Bitset & b) {
if (_Bits == b._Bits) {
return memcmp(_Array, b._Array, (calculateWords() + 1) * sizeof(_Ty)) != 0;
}
return true;
}
Bitset Bitset::operator<<(size_t _Pos) const { // return bitset shifted left by _Pos
return (Bitset(*this) <<= _Pos);
}
Bitset Bitset::operator>>(size_t _Pos) const { // return bitset shifted right by _Pos
return (Bitset(*this) >>= _Pos);
}
bool Bitset::operator > (const Bitset & c)const {
if (_Bits <= sizeof(unsigned long long)
&&
c._Bits <= sizeof(unsigned long long)) {
return to_ullong() > c.to_ullong();
}
else {
std::string s1 = to_string();
std::string s2 = c.to_string();
return s1 > s2;
}
}
bool Bitset::operator < (const Bitset & c)const {
if (_Bits <= sizeof(unsigned long long)
&&
c._Bits <= sizeof(unsigned long long)) {
return to_ullong() < c.to_ullong();
}
else {
std::string s1 = to_string();
std::string s2 = c.to_string();
return s1 < s2;
}
}
Bitset& Bitset::operator &=(const Bitset& _Right) { // AND in _Right
ptrdiff_t _Words = calculateWords();
for (ptrdiff_t _Wpos = _Words; 0 <= _Wpos; --_Wpos)
_Array[_Wpos] &= _Right.getWord(_Wpos);
return (*this);
}
Bitset& Bitset::operator|=(const Bitset& _Right) { // OR in _Right
ptrdiff_t _Words = calculateWords();
for (ptrdiff_t _Wpos = _Words; 0 <= _Wpos; --_Wpos)
_Array[_Wpos] |= _Right.getWord(_Wpos);
return (*this);
}
Bitset& Bitset::operator^=(const Bitset& _Right) { // XOR in _Right
ptrdiff_t _Words = calculateWords();
for (ptrdiff_t _Wpos = _Words; 0 <= _Wpos; --_Wpos)
_Array[_Wpos] ^= _Right.getWord(_Wpos);
return (*this);
}
Bitset& Bitset::operator<<=(size_t _Pos) { // shift left by _Pos
ptrdiff_t _Words = calculateWords();
const ptrdiff_t _Wordshift = (ptrdiff_t)(_Pos / _Bitsperword);
if (_Wordshift != 0)
for (ptrdiff_t _Wpos = _Words; 0 <= _Wpos; --_Wpos)
_A