位图实际上就是一个指定比特位个数的连续内存空间,所以可以用STL内置的容器vector管理,除此之外,理论上任何类型都可以作为元素的类型,只不过为了容易理解,它的每个元素的类型被设定为char。
创新互联公司是一家集网站建设,青阳企业网站建设,青阳品牌网站建设,网站定制,青阳网站建设报价,网络营销,网络优化,青阳网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。template// N个比特位
class bitset
{private:
vector_bits; // 以char为单位管理
};
1. bitset接口
1.1 构造函数构造一个有N位的位图,并将所有位初始化为0。
由于申请空间时的最小单位是char(1字节),也就是8个比特位。那么对于N个比特位,需要申请N/8+1个char型空间,因为N可能不是8的整数倍。
申请N=20个比特位,需要20/8+1=3个char。
bitset()
{_bits.resize(N / 8 + 1, 0);
}
1.2 set要把某个比特位变成1,首先要知道这个比特位在哪个位置。
void set(size_t pos)
{assert(pos< N);
size_t x = pos / 8; // 在x个char
size_t y = pos % 8; // 在这个char的第y个比特位
_bits[x] |= (1<< y); // 将这个比特位设为1
}
1.3 reset要把某个比特位清空,即恢复到0状态,首先要找到它的位置,和set的操作是一样的,只有最后一步不同:
注意:
使用~
对左移后的1按位取反,而不是逻辑取反!
。
void reset(size_t pos)
{assert(pos< N);
size_t x = pos / 8; // 在x个char
size_t y = pos % 8; // 在这个char的第y个比特位
_bits[x] &= (~(1<< y)); // 将这个比特位设为0
}
1.4 flip要把某个比特位取反,首先要找到它的位置:
void flip(size_t pos)
{assert(pos< N);
size_t x = pos / 8; // 在x个char
size_t y = pos % 8; // 在这个char的第y个比特位
_bits[x] ^= (1<< y); // 将这个比特位取反
}
1.5 test同样地:
void test(size_t pos)
{assert(pos< N);
size_t x = pos / 8; // 在x个char
size_t y = pos % 8; // 在这个char的第y个比特位
if (_bits[x] & (1<< y)) // 该位已被设置
return true;
else
return false;
}
1.6 size、count直接返回模板参数N。
size_t size()
{return N;
}
要知道位图中被设置为1的位的个数,就是遍历整个位图,统计1的个数。
原因是每进行一次操作1,都会将数x最右端的1消去。那么在x不为0之前,进行了几次消1操作就是位图中1个个数。
size_t count()
{size_t count = 0;
for (auto e : _bits)
{char num = e;
while (num)
{num &= num - 1;
count++;
}
}
return count;
}
1.7 any、none、all只需要遍历位图中所有的比特位,一旦有1则返回true,否则返回0。但也可以不用这么干,因为一个char里只要有一个不为0,整个char就是其他字符。ASCII=0对应的字符时'\0'
,但是它一般用在字符串处理中,个人认为在这里还是将0强转为char比较合适。
bool any()
{for (auto e : _bits)
{if (e != (char)0)
return true;
}
return false;
}
直接复用any的代码,它们是互斥的。
bool none()
{return !any();
}
判断全部位置都被设置为1,分为两步:
同样地,第一步中可以判断这个char是否等于比特位全为1对应的字符,也就是(char)127
,遍历剩下的比特位是否为1即可。
bool all()
{size_t size = _bits.size();
for (size_t i = 0; i< size - 1; i++) // 前size-1个完整的char
{if (_bits[i] != (char)127)
return false;
}
for (size_t i = 0; i< N % 8; i++) // 最后一个char的剩下位
{if ((_bits[size - 1] & (1<< i)) == (char)0)
return false;
}
return true;
}
1.8 打印函数这不是bitset内置的成员函数,因为STL中重载了流输入>>
和流输出<<
运算符,可以直接打印bitset中的内容,而模拟实现并未重载它们,所以用打印函数输出容器内容。
思路和上一个很类似,也是分批打印:
void Print()
{string ret = "";
size_t size = _bits.size();
for (size_t i = 0; i< size - 1; i++)
{for (size_t j = 0; j< 8; j++)
{if (_bits[i] & (1<< j))
ret += "1";
else
ret += "0";
}
}
for (size_t j = 0; j< N % 8; j++)
{if (_bits[size - 1] & (1<< j))
ret += "1";
else
ret += "0";
}
cout<< ret<< endl;
}
2. bitset测试void bitset_test1()
{xy::bitset<30>bs1;
bs1.set(8);
bs1.set(9);
bs1.set(7);
bs1.set(27);
bs1.set(20);
bs1.Print();
cout<< bs1.count()<< endl;
bs1.reset(8);
bs1.reset(9);
bs1.reset(20);
bs1.Print();
cout<< bs1.count()<< endl;
cout<< bs1.any()<< endl;
bs1.reset(7);
bs1.reset(27);
bs1.Print();
cout<< bs1.none()<< endl;
}
输出:
000000011100000000001000000100
5
000000010000000000000000000100
2
1
000000000000000000000000000000
1
源代码
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧