bitset.cpp

template <int esize>
class Bitset
{
public:
	static const int bsize = esize / 64 + (esize % 64 ? 1 : 0);

	uint64 data[bsize];

	uint which_byte(uint n) const
	{
		for (uint b = 0; b < bsize; b++) {
			if (n < (b + 1) * 64)
				return b;
		}
		return (uint)-1;
	}

	void set(uint n, bool v)
	{
		uint b = which_byte(n);
		if (b >= bsize)
			return;
		int bit = n % 64;
		data[b] = (data[b] & ~(1 << bit)) | ((uint64)v << bit);
	}

	bool at(uint n) const
	{
		uint b = which_byte(n);
		if (b >= bsize)
			return false;
		return (bool)(data[b] & (1 << (n % 64)));
	}

	bool all() const
	{
		uint b;
		for (b = 0; b < esize / 64; b++)
			if (data[b] != (uint64)-1)
				return false;
		if (esize % 64) {
			uint64 bitmask = ~(1ULL << ((esize % 64) - 1));
			if ((data[b] & bitmask) != bitmask)
				return false;
		}
		return true;
	}

	bool none() const
	{
		uint b;
		for (b = 0; b < esize / 64; b++)
			if (data[b] != (uint64)0)
				return false;
		if (esize % 64) {
			uint64 bitmask = ~(1ULL << ((esize % 64) - 1));
			if ((data[b] & bitmask) != 0)
				return false;
		}
		return true;
	}

	bool any() const
	{
		return !none();
	}

	uint count() const
	{
		if (all())
			return esize;
		if (none())
			return 0;
		uint c = 0, b;
		for (b = 0; b < esize / 64; b++)
			for (uint i = 0; i < 64; i++)
				if (data[b] & (1 << i))
					c++;
		uint mod = esize % 64;
		if (mod) {
			for (uint i = 0; i < mod; i++)
				if (data[b] & (1 << i))
					c++;
		}
		return c;
	}

	void reset()
	{
		memset(data, 0x00, bsize * 8);
	}

	void reset(uint n)
	{
		set(n, false);
	}

	void set()
	{
		memset(data, 0xFF, bsize * 8);
	}

	void set(uint n)
	{
		set(n, true);
	}
};