本文共 2442 字，大约阅读时间需要 8 分钟。

下午的时候写了一下位运算的：

我个人感觉如果对位运算不是很熟的话可以先看一下上面那个

位图 - 数据结构

为什么要位图？上一篇里面有个例子，是这样的：

一般对于去重的思路就是：排序、遍历、去重。

那，就先讲这个排序。怎么排？看完上一篇的小伙伴都知道，用“位”来排序，快。

但是，时间是有了，空间呢？来算一笔账啊：一个int，4个字节，256个int是1k，大概25W个数据为1M，那1billion个数据，就是400M。

这动不动就要耗费这么大的内存来排个序，挺好。

而位图，就将大大地缩小这个，内存占用。

都知道，一个int是32个字节，那如果用每个字节来存一个数据，又当如何？

先不要问怎么实现的（映射），至少现在知道，一个int可以存32个数据，那么这个空间是不是被直接压缩了32倍。

位图设计

数据结构构造

为了方便，我们将位图用一个数组表示，让vector帮我们开辟一段连续的空间，我们只负责将数据设置或者移除就行。

void SetBit(size_t x)	{
   		size_t index = x >> 5;		size_t num = x % 32;		_bitTable[index] |= (1 << num);	}

先把这个构造函数看懂了，不然下面就一团晕。

新元素插入

读取到一个数据，自然是要插入到位图中

void SetBit(size_t x)	{
   		size_t index = x >> 5;		size_t num = x % 32;		_bitTable[index] |= (1 << num);	}

如果是为了去重，在这里就可以动手脚了，不过本着“单一职责原则”，我就不动手脚了。

来看看为什么需要size_t index = x >> 5和size_t num = x % 32两步操作：我们看看要映射5和32这俩个数（如果上面那个构造函数没悟到的话）

位图中元素移出

这个就比较直观了，如果位运算熟练的话

void RemoveBit(size_t x)	{
   		size_t index = x >> 5;		size_t num = x % 32;		_bitTable[index] &= ~(1 << num);	//~(1 << num) ：除了num位为0，其余位都为1	}

位图元素查找

可用于查找，也可用于查重。

bool TestBit(size_t x){
   	size_t index = x >> 5;	size_t num = x % 32;	return _bitTable[index] & (1 << num);}

这些功能也差不多够用了，接下来组装一下。

完整代码

class BitMap{
   public:	BitMap(size_t range)	{
   		_bitTable.resize((range >> 5) + 1);	}	//标识一个数字在位图中的位置	void SetBit(size_t x)	{
   		size_t index = x >> 5;		size_t num = x % 32;		_bitTable[index] |= (1 << num);	}	//取消数字在位图当中的标识.	void RemoveBit(size_t x)	{
   		size_t index = x >> 5;		size_t num = x % 32;		_bitTable[index] &= ~(1 << num);	}	bool TestBit(size_t x)	{
   		size_t index = x >> 5;		size_t num = x % 32;		return _bitTable[index] & (1 << num);	}private:	vector
   
     _bitTable;};
   

找出二次出现的数据

此时我们就需要使用两位来标记同一个数据了。

class NBitMap{
   public:	NBitMap(size_t range)	{
   		_bitTable.resize((range >> 4) + 1);	}	void SetBit(size_t x)	{
   		size_t index = x >> 4;		size_t num = x % 16;		num *= 2;		bool first = _bitTable[index] & (1 << num);		bool second = _bitTable[index] & (1 << (num + 1));		if (!(first && second))		{
   			_bitTable[index] += (1 << num);		}	}	bool TestBit(size_t x)	{
   		size_t index = x >> 4;		size_t num = x % 16;		num *= 2;		return (_bitTable[index] >> num) & 0x03;	}private:	vector
   
     _bitTable;};
   

思考

如何分辨一次出现、二次出现与多次出现的数据？

转载地址：https://lion-wu.blog.csdn.net/article/details/107258974 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！