C++ 位图 bitset
std::betset
template <size_t N> class bitset;
N是一个非类型模板参数,表示这个位图有N个比特位
1. 构造 construct
bitset(); //默认构造
bitset (unsigned long val); //用一个无符号long型构造
//用字符串构造
template<class charT, class traits, class Alloc>
explicit bitset (const basic_string<charT,traits,Alloc>& str,
typename basic_string<charT,traits,Alloc>::size_type pos = 0,
typename basic_string<charT,traits,Alloc>::size_type n = basic_string<charT,traits,Alloc>::npos);
注意:
用整数和字符串初始化时,是从位图的低位开始进行初始化的
例如:
int main ()
{
std::bitset<16> foo; //16位比特位为0
std::bitset<16> bar (0xfa2); //用0xfa2 - 111110100010 进行构造
std::bitset<16> baz (std::string("0101111001")); //用字符串构造
std::cout << "foo: " << foo << '\n';
std::cout << "bar: " << bar << '\n';
std::cout << "baz: " << baz << '\n';
return 0;
}
output:
foo: 0000000000000000
bar: 0000111110100010
baz: 0000000101111001
2. 成员函数
操作函数
2.1 bitset::set
all bits (1) bitset& set();
single bit (2) bitset& set (size_t pos, bool val = true);
-
第一种方式:将所有比特位设置为1
-
第二种方式:将pos位置的比特位设置为val
pos
:从低位,下标为0开始数,pos
即倒数第pos个下标val
:true -> 1; false -> 0
例如:
int main()
{
std::bitset<16> foo;
std::cout << "foo: " << foo << '\n';
foo.set();
std::cout << "foo: " << foo << '\n';
foo.set(2, false);
std::cout << "foo: " << foo << '\n';
return 0;
}
output:
foo: 0000000000000000
after foo.set(), foo: 1111111111111111
after foo.set(2, false), foo: 1111111111111011
2.2 bitset::reset
all bits (1) bitset& reset();
single bit (2) bitset& reset (size_t pos);
- 将所有的比特位或
pos
处的比特位置0
例如:
int main()
{
std::bitset<16> foo;
foo.set();
std::cout << "foo: " << foo << '\n';
foo.reset(3);
std::cout << "after foo.reset(3), foo: " << foo << '\n';
return 0;
}
output:
foo: 1111111111111111
after foo.reset(3), foo: 1111111111110111
2.3 bitset::flip
all bits (1) bitset& flip();
single bit (2) bitset& flip (size_t pos);
- 反转所有比特位或将
pos
位置的比特位反转
例如:
int main()
{
std::bitset<16> foo;
std::cout << "foo: " << foo << '\n';
foo.flip(3);
std::cout << "after foo.flip(3), foo: " << foo << '\n';
return 0;
}
output:
foo: 0000000000000000
after foo.flip(3), foo: 0000000000001000
2.4 bitset::operator[]
bool operator[] (size_t pos) const; //获取该比特位为0还是1
reference operator[] (size_t pos); //获取该比特位的引用,可直接修改
获取状态函数
成员函数 | 功能 |
---|---|
size_t size() const; | 获取一共多少个比特位 |
size_t count() const; | 获取有多少个比特位为1 |
bool test (size_t pos) const; | 判断pos 位置的比特位是否为1 |
bool any() const; | 判断位图中是否有比特位为1 |
bool none() const; | 判断位图中是否所有比特位为0(any 的反面) |
bool all() const noexcept; | 判断位图中是否所有的比特位为1 |
转换函数
成员函数 | 功能 |
---|---|
string to_string() const | 将位图转换为0/1字符串 |
unsigned long to_ulong() const; | 将位图转换为ul型整数 |
unsigned long long to_ullong() const; | 将位图转换为ull型整数 |
3. 输入输出运算符重载
输入的比特位从低位开始填充
例如:
int main()
{
std::bitset<10> foo;
std::cout << "please input: ";
std::cin >> foo;
std::cout << "output foo: " << foo << std::endl;
return 0;
}
output:
please input: 1111
output foo: 0000001111
4. 位运算重载
5. 模拟实现
bitset
实际上使用多个unsigned long
型进行实现的
例如如果N == 1000
,由于一个unsigned long
为32(也可能是64),那我们就需要1000 / 32 = 31 + 1
,即32
个unsigned long
型数据
注意:
bitset
的第 0 位存储在数组的第一个无符号整数的最低位。
5.1 构造 construct
template<size_t N>
class bitset
{
public:
bitset()
{
_bitset.resize(N / 32 + 1);
}
private:
std::vector<unsigned long> _bitset;
};
5.2 操作函数
5.2.1 set
如果要将所有位置1,很简单,将vector
中的每个数| 0UL
即可
如果要将指定pos
位置的比特位置1,那么就先要获得pos
位置的比特位:
- 先获取
pos
在第几个整数:pos / 32
- 再获取
pos
在这个整数的第几个比特位pos % 32
bitset& set()
{
for (auto& num : _bitset)
num |= ~0UL;
return *this;
}
bitset& set(size_t pos, bool val = true)
{
assert(pos < N);
size_t unit_index = pos / sizeoful; //在第几个整数
size_t bit_index = pos % sizeoful; //在这个整数的第几个比特位
if (val)
_bitset[unit_index] |= (1UL << bit_index);
else
_bitset[unit_index] &= ~(1UL << bit_index);
return* this;
}
5.2.2 reset
和set
的逻辑类似
bitset& reset()
{
for (auto& num : _bitset)
num = 0;
return *this;
}
bitset& reset(size_t pos)
{
assert(pos < N);
size_t unit_index = pos / sizeoful; //在第几个整数
size_t bit_index = pos % sizeoful; //在这个整数的第几个比特位
_bitset[unit_index] &= ~(1UL << bit_index);
return *this;
}
5.2.3 flip
bitset& flip()
{
for (auto& num : _bitset)
num = ~num;
return *this;
}
bitset& flip(size_t pos)
{
assert(pos < N);
size_t unit_index = pos / sizeoful; //在第几个整数
size_t bit_index = pos % sizeoful; //在这个整数的第几个比特位
_bitset[unit_index] ^= (1UL << bit_index);
return *this;
}
5.3 获取状态函数
bool test(size_t pos) const
{
assert(pos < N);
size_t unit_index = pos / sizeoful; //在第几个整数
size_t bit_index = pos % sizeoful; //在这个整数的第几个比特位
return _bitset[unit_index] & (1UL << bit_index);
}
size_t size() const
{
return N;
}
size_t count() const
{
int ret = 0;
for (size_t i = 0; i < N; i++)
ret += test(i);
return ret;
}
bool any() const
{
for (auto& num : _bitset)
if (num)
return true;
return false;
}
bool none() const
{
return !any();
}
bool all() const
{
int ret = 0;
for (size_t i = 0; i < N; i++)
ret += test(i);
return ret == N;
}
5.4 输出运算符重载
friend std::ostream& operator<< (std::ostream& cout, const bitset<N>& bitset)
{
for (size_t i = N - 1; i >= 0; --i)
cout << (bitset.test(i) == true ? 1 : 0);
return cout;
}
5.5 代码
namespace lwj
{
template<size_t N>
class bitset
{
const size_t sizeoful = sizeof(unsigned long) * 8;
public:
bitset()
{
_bitset.resize(N / sizeoful + 1);
}
bitset& set()
{
for (auto& num : _bitset)
num |= ~0UL;
return *this;
}
bitset& set(size_t pos, bool val = true)
{
assert(pos < N);
size_t unit_index = pos / sizeoful; //在第几个整数
size_t bit_index = pos % sizeoful; //在这个整数的第几个比特位
if (val)
_bitset[unit_index] |= (1UL << bit_index);
else
_bitset[unit_index] &= ~(1UL << bit_index);
return* this;
}
bitset& reset()
{
for (auto& num : _bitset)
num = 0;
return *this;
}
bitset& reset(size_t pos)
{
assert(pos < N);
size_t unit_index = pos / sizeoful; //在第几个整数
size_t bit_index = pos % sizeoful; //在这个整数的第几个比特位
_bitset[unit_index] &= ~(1UL << bit_index);
return *this;
}
bitset& flip()
{
for (auto& num : _bitset)
num = ~num;
return *this;
}
bitset& flip(size_t pos)
{
assert(pos < N);
size_t unit_index = pos / sizeoful; //在第几个整数
size_t bit_index = pos % sizeoful; //在这个整数的第几个比特位
_bitset[unit_index] ^= (1UL << bit_index);
return *this;
}
bool test(size_t pos) const
{
assert(pos < N);
size_t unit_index = pos / sizeoful; //在第几个整数
size_t bit_index = pos % sizeoful; //在这个整数的第几个比特位
return _bitset[unit_index] & (1UL << bit_index);
}
size_t size() const
{
return N;
}
size_t count() const
{
int ret = 0;
for (size_t i = 0; i < N; i++)
ret += test(i);
return ret;
}
bool any() const
{
for (auto& num : _bitset)
if (num)
return true;
return false;
}
bool none() const
{
return !any();
}
bool all() const
{
int ret = 0;
for (size_t i = 0; i < N; i++)
ret += test(i);
return ret == N;
}
friend std::ostream& operator<< (std::ostream& cout, const bitset<N>& bitset)
{
for (size_t i = N - 1; i >= 0; --i)
cout << (bitset.test(i) == true ? 1 : 0);
return cout;
}
private:
std::vector<unsigned long> _bitset;
};
}