Description 描述

dynamic_bitset 类表示一组位。它通过 operator[] 访问各个位的数值，并提供可应用于内置整数的所有位运算符，例如 operator& 和 operator<< 。位集中的位数在 dynamic_bitset 构造函数的参数中通过运行时指定。

dynamic_bitset 类与 std::bitset 类几乎相同。不同之处在于 dynamic_bitset 的大小（位数）是在构造 dynamic_bitset 对象时在运行时指定的，而 std::bitset 的大小则在编译时通过整数模板参数指定。

dynamic_bitset 设计的核心问题在于表示有限集合的子集。每个位都代表有限集合中的元素是否属于该子集。因此， dynamic_bitset 的位运算，例如 operator& 和 operator| ，对应于集合运算，例如交集和并集。

每个位表示布尔值真或假 (1 或 0)。要 设置 位，即将其赋值为 1。要 清除 或 复位 位，即将其赋值为 0。要 翻转 位，即将其值更改为 1（如果它为 0）或 0（如果它为 1）。每个位都有一个非负 位置。位集 x 包含 x.size() 位，每个位都分配到 [0,x.size()) 范围内的唯一位置。位置为 0 的位称为 最低有效位，位置为 size() - 1 的位是 最高有效位。当将 dynamic_bitset 的实例转换为或从无符号长 n 转换时，位集的位置 i 的位具有与 (n >> i) & 1 相同的值。

dynamic_bitset 不是一个容器，并且不提供迭代器。

简单的示例

#include <iostream>
#include <boost/dynamic_bitset.hpp>

int main()
{
    boost::dynamic_bitset<> x(5); // all 0's by default
    x[0] = 1;
    x[1] = 1;
    x[4] = 1;
    
    // 不提供迭代器，因此采用这种方式进行迭代
    // 输出： 10011
    for (boost::dynamic_bitset<>::size_type i = 0; i < x.size(); ++i) {
	    std::cout << x[i];
    }

	// 输出的x和上面的迭代输出相反，即：10011
    std::cout << x << std::endl;

    return 0;
}

#include <iostream>
#include <boost/dynamic_bitset.hpp>

int main()
{
	// ul : unsigned long
	// 第一个数字2表示集合大小为2，第二个数字表示创建的集合是二进制的该数字
	boost::dynamic_bitset<> b0(10, 123456789ul);
	std::cout << "b0 = " << b0 << std::endl;	// b0 = 0100010101

	const boost::dynamic_bitset<> b1(std::string("0100010101"));
	std::cout << "b1 = " << b1 << std::endl;	// b1 = 0100010101

	b0[b0.size() - 1] = 1;
	std::cout << "b0 = " << b0 << std::endl;	// b0 = 1100010101

	// 集合的并集
	auto b2 = b0 | b1;
	std::cout << "b2 = " << b2 << std::endl;	// b2 = 1100010101

	// 集合的交集
	auto b3 = b0 & b1;
	std::cout << "b3 = " << b3 << std::endl;	// b3 = 0100010101

	// 集合中 1 的数量
	std::cout << "Number of 1s: " << b0.count() << std::endl;

	// 集合的补集
	auto b0_complement = ~b0;
	std::cout << "b0_complement = " << b0_complement << std::endl;

	// 集合的差A-B就是A & ~B
	auto b0_minus_b1 = b0 & ~b1;
	std::cout << "b0_minus_b1 = " << b0_minus_b1 << std::endl;

	return 0;
}

应用：PCenter问题的集合

#include <boost/dynamic_bitset.hpp>
#include <iostream>
class PCenterSet
{
public:
	PCenterSet(int n);
	void add(int node_id);
	void remove(int node_id);
	inline int count() const;
    // 交集
    PCenterSet intersection(const PCenterSet& other) const;

    // 并集
    PCenterSet union_set(const PCenterSet& other) const;

	// 直接得到并集的元素数量
	int union_count(const PCenterSet& other) const;

    // 补集
	PCenterSet complement() const;

    // 重载 ostream 的 << 运算符
	friend std::ostream& operator<<(std::ostream& os, const PCenterSet& pSet);

private:
	int n;
	boost::dynamic_bitset<> set;
};

PCenterSet::PCenterSet(int _n) : n(_n), set(_n) {}

void PCenterSet::add(int node_id)
{
	if (node_id >= 0 && node_id < n)
		set[node_id] = 1;
}

void PCenterSet::remove(int node_id)
{
	if (node_id >= 0 && node_id < n)
		set[node_id] = 0;
}

int PCenterSet::count() const
{
	return set.count();
}

PCenterSet PCenterSet::intersection(const PCenterSet& other) const
{
	PCenterSet result(n);
	result.set = set & other.set;
	return result;
}

PCenterSet PCenterSet::union_set(const PCenterSet& other) const
{
	PCenterSet result(n);
	result.set = set | other.set;
	return result;
}

int PCenterSet::union_count(const PCenterSet& other) const
{
	return (set | other.set).count();
}

PCenterSet PCenterSet::complement() const
{
	PCenterSet result(n);
	result.set = ~set;
	return result;
}

std::ostream& operator<<(std::ostream& os, const PCenterSet& pSet)
{
	os << "{";
	bool first = true;
	for (int i = 0; i < pSet.n; ++i)
	{
		if (pSet.set[i] == 1)
		{
			if (!first)
				os << ", ";
			os << i;
			first = false;
		}
	}
	os << "}";
	return os;
}