C++ 位图 bitset

发布于：2025-03-18 ⋅ 阅读:(15) ⋅ 点赞:(0)

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;
	};
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布