动态Bitset源代码_JavaScript源代码-C++代码类资源-CSDN文库

共2个文件

cpp：1个

h：1个

c++

std

bitset

需积分: 22 263 浏览量 2017-09-30 17:20:09 上传评论 1 收藏 6KB 7Z 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

在C++的STL中实现由一个bitset类模板，其用法如下： std::bitset<64> bs; 也就是说，这个bs只能支持64位以内的位存储和操作；bs一旦定义就不能动态增长了。本资源附件中实现了一个动态Bitset，和标准bitset兼容。 /** @defgroup Bitset Bitset位集类 * @{ */ //根据std::bitset改写，函数意义和std::bitset保持一致 class CORE_API Bitset: public Serializable { typedef typename uint32_t _Ty; static const int _Bitsperword = (CHAR_BIT * sizeof(_Ty)); _Ty * _Array; //最低位放在[0]位置，每位的默认值为0 int _Bits;//最大有效的Bit个数 private: int calculateWords()const; void tidy(_Ty _Wordval = 0); void trim(); _Ty getWord(size_t _Wpos)const; public: //默认构造 Bitset(); //传入最大的位数,每位默认是0 Bitset(int nBits); virtual ~Bitset(); //直接整数转化成二进制，赋值给Bitset，最高低放在[0]位置 Bitset(unsigned long long _Val); //拷贝构造函数 Bitset(const Bitset & b); Bitset(const char * str); Bitset(const std::string & str, size_t _Pos, size_t _Count); public: size_t size()const; //返回设置为1的位数 size_t count() const; bool subscript(size_t _Pos) const; bool get(size_t pos) const; //设置指定位置为0或1，true表示1，false表示0，如果pos大于数组长度，则自动扩展 void set(size_t _Pos, bool _Val = true); //将位数组转换成整数，最低位放在[0]位置 //例如数组中存放的1011，则返回13，而不是返回11 unsigned long long to_ullong() const; bool test(size_t _Pos) const; bool any() const; bool none() const; bool all() const; std::string to_string() const; public: //直接整数转化成二进制，赋值给Bitset，最高位放在[0]位置 Bitset& operator = (const Bitset& b); //直接整数转化成二进制，赋值给Bitset，最高位放在[0]位置 Bitset& operator = (unsigned long long ull); //返回指定位置的值，如果pos大于位数组长度，自动拓展 bool operator [] (const size_t pos); //测试两个Bitset是否相等 bool operator == (const Bitset & b); bool operator != (const Bitset & b); Bitset operator<<(size_t _Pos) const; Bitset operator>>(size_t _Pos) const; bool operator > (const Bitset & c)const; bool operator < (const Bitset & c)const; Bitset& operator &=(const Bitset& _Right); Bitset& operator|=(const Bitset& _Right); Bitset& operator^=(const Bitset& _Right); Bitset& operator<<=(size_t _Pos); Bitset& operator>>=(size_t _Pos); public: Bitset& flip(size_t _Pos); Bitset& flip(); //将高位与低位互相，如数组存放的是1011，则本函数执行后为1101 Bitset& reverse(); //返回左边n位，构成新的Bitset Bitset left(size_t n) const; //返回右边n位，构成新的Bitset Bitset right(size_t n) const; //判断b包含的位数组是否是本类的位数组的自串，如果是返回开始位置 size_t find (const Bitset & b) const; size_t find(unsigned long long & b) const; size_t find(const char * b) const; size_t find(const std::string & b) const; //判断本类的位数组是否是b的前缀 bool is_prefix(unsigned long long & b) const; bool is_prefix(const char * b) const; bool is_prefix(const std::string & b) const; bool is_prefix(const Bitset & b) const; void clear(); void resize(size_t newSize); void reset(const unsigned char * flags, size_t s); void reset(unsigned long long _Val); void reset(const char * _Str); void reset(const std::string & _Str, size_t _Pos, size_t _Count); //左移动n位，返回新的Bitset //extendBits=false "1101" 左移动2位 "0100"; //extendBits=true "1101" 左移动2位 "110100"; Bitset leftShift(size_t n,bool extendBits=false)const; //右移动n位，返回新的Bitset //extendBits=false "1101" 右移动2位 "0011"; //extendBits=true "1101" 右移动2位 "001101"; Bitset rightShift(size_t n, bool extendBits = false) const; public: virtual uint32_t getByteArraySize(); // returns the size of the required byte array. virtual void loadFromByteArray(const unsigned char * data); // load this object using the byte array. virtual void storeToByteArray(unsigned char ** data, uint32_t& length) ; // store this object in the byte array. };

资源推荐

资源详情

资源评论

收起资源包目录

bitset.7z （2个子文件）

bitset.h 7KB

bitset.cpp 22KB

#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

评论收藏

内容反馈