位图原理以及C++实现

位图

位图就是一个数组的每一个数据的每一个二进制位来表示一个数据，0表示数据不存在，1表示数据存在。

例如136这个数字，

• 136 / 32 = 4，一个int的二进位制可以存放32个数，136存放于第4个区间，（区间从0开始）
• 136 % 32 = 8，表示136存放于8号位置，（位置从0开始）

然后将那个位置置为1即可。

位图代码实现

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class BitMap {
public:
	BitMap(int size) {
		//要存储数据的大致范围
		m_bitmap.resize(size / 32 + 1);
	}

	//设置位
	void Set(int x) {
		int block = x / 32;
		int index = x % 32;
		m_bitmap[block] |= (1 << index);//或运算 将对应位标识位为1 
		//eg:  原来无数据，存储0，
		//00000000 | 00000001 = 00000001
	}

	//清除位
	void Reset(int x) {
		int block = x / 32;
		int index = x % 32;
		m_bitmap[block] &= ~(1 << index);
		//eg: 原来存储了0，消去0
		//00000001 & 11111110 = 00000000
	}

	//检查位
	bool Test(int x) {
		int block = x / 32;
		int index = x % 32;
		if (m_bitmap[block] & (1 << index))
			return true;
		else return false;
	}

private:
	vector<int> m_bitmap;
};

代码实例

int main() {

	//int a = 1;

	//cout << a << "--" << (a << 1) << endl;

	//设置136记录到位图，然后查看其是否存在
	BitMap bitmap(136);
	bitmap.Set(136);
	if (bitmap.Test(136)) cout << "136位于位图之中" << endl;
	else cout << "136不在位图中" << endl;

	if(bitmap.Test(120)) cout << "120位于位图之中" << endl;
	else cout << "120不在位图中" << endl;

	bitmap.Reset(136);
	if (bitmap.Test(136)) cout << "136位于位图之中" << endl;
	else cout << "136不在位图中" << endl;

	//给定一个数组：存储1-10000，现在随机删除两个数字，求被删去的两个数字
	vector<int> nums(10000);
	for (int i = 0; i < 10000; i++) {
		nums[i] = i + 1;
	}

	nums[3546] = 0;
	nums[9856] = 0;

	//重新打算数组元素
	random_shuffle(nums.begin(), nums.end());

	//找出被删除的那两个元素
	BitMap bits(10000);
	for (int i = 0; i < 10000; i++) {
		bits.Set(nums[i]);
	}

	cout << "被删除的元素： ";
	for (int i = 1; i <= 10000; i++) {
		if (!bits.Test(i)) {
			cout << i << " ";
		}
	}
	cout << endl;
	

	return 0;
}

输出结果：

136位于位图之中
120不在位图中
136不在位图中
被删除的元素： 3547 9857

实例

一个文件无序存放了1万个数字，每行1个，数字范围1-1w，不重复，现在随机删除两个数字，请把两个数字找出来。

• 使用hash，遍历文件，每遍历到一个数字，就以该数字为下标的数组元素置1
• 然后再遍历一遍hash，值为0的元素对应的下标就是所求的数字。

内存优化

使用bitmap，每一个bit可以代表一个数字。这样可以压缩到内存。

压缩率

bit表示一位数字，而之前一个数字就是int，压缩率32倍

适用bitmap的场景

• 数据比较密集、数据连续不重复，数据有范围！

若数据有重复

• 使用2-bitmap。00表示不出现、01表示出现1次，10表示出现2次，11表示无定义
• 若是随机统计一个数具体出现了多少次呢？
  • 最多出现1万次，那么二进制就是14位
  • 用14位来记录一个数，也比32位记录一个数开销小。