C++ 哈希的应用--位图

template<size_t N> // 非类型模板参数：用一个整形作为模板的一个参数，在模板中可以当常量使用
class bitset
{
public:
    bitset()
	{
		_bits.resize(N / 8 + 1, 0);
	}
 
    void set(size_t x)//标记
    {
        size_t i = x / 8;
        size_t j = x % 8;
 
        _bits[i] |= (1 << j);
 
    }
    void reset(size_t x)//清除
    {
        _bits[i] &= (~(1 << j));
    }
 
    bool test(size_t x)//测试这个值在不在
    {
        size_t i = x / 8;
        size_t j = x % 8;
 
        return _bits[i] & (1 << j);
    }
private:
    vector<char> _bits;
};

class bitset {
public:
	bitset(size_t N) {
		_bits.resize(N / 32 + 1, 0);
		_num = 0;
	}
 
	void set(size_t x) {
		size_t index = x / 32;  // 算出x映射的位在第几个整形
		size_t pos = x % 32;  // 算出x在这个整形中第几个位置(bit位)
 
		_bits[index] |= (1 << pos); // 第pos个位置成1
		// 左移、右移这里的左右不是方向
		// 左移是向高位移
		// 右移是向低位移
 
		++_num;
	}
 
	void reset(size_t x) {
		size_t index = x / 32;  // 算出x映射的位在第几个整形
		size_t pos = x % 32;  // 算出x在这个整形中第几个位置(bit位)
 
		_bits[index] &= ~(1 << pos); // 第pos个位置成0
 
		--_num;
	}
 
	// 判断x在不在
	bool test(size_t x) {
		size_t index = x / 32;  // 算出x映射的位在第几个整形
		size_t pos = x % 32;  // 算出x在这个整形中第几个位置(bit位)
 
		return _bits[index] & (1 << pos);
 
	}
 
private:
	std::vector<int> _bits; // 一个int4个字节，一个字节8个bit位
	size_t _num;
};

void test_bitset() {
 
	bitset bs(100);
	bs.set(99);
	bs.set(98);
	bs.set(97);
	bs.set(96);
	for (size_t i = 0; i < 100; ++i) {
		printf("[%d]:%d\n", i, bs.test(i));
	}
	cout << bs.test(96);
 
	//bitset bs1(-1);//无符号最大数直接传-1，会转成最大数量
	//bitset bs2(pow(2,32));
	//bitset bs3(0xffffffff);
}

    template<size_t N>
    class solution {
	public:
		void set(size_t x) {
			if (_bs1.test(x) == false && _bs2.test(x) == false) {   // 00
				_bs2.set(x);  //   01
			}
			else if (_bs1.test(x) == false && _bs2.test(x) == true) {  // 01
				_bs1.set(x);  
				_bs2.reset(x);  //   10
			}
		}
 
        void PrintOnce()
	    {
		    for (size_t i = 0; i < N; ++i)
		    {
			    if (!_bs1.test(i) && _bs2.test(i))
			    {
			    	cout << i << endl;
		    	}
	    	}
		    cout << endl;
	    }
 
	private:
		bitset<N> _bs1;
	    bitset<N> _bs2;
 
	};

	void test_solution()
	{
		solution<100> tbs;
		int a[] = { 3, 5, 6, 7, 8, 9 ,33, 55, 67, 3,3,3,5,9,33 };
		for (auto e : a)
		{
			tbs.set(e);
		}
		tbs.PrintOnce();
	}