建站
咨询
售后
建站咨询
成都创新互联公司服务项目包括莫力达网站建设、莫力达网站制作、莫力达网页制作以及莫力达网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，莫力达网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到莫力达省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
位图的概念：
在C++中，位图是以位来表示整数的结构，普通的整数一个数需要用4个字节来表示，我们可以换种思想，在整个整数的集合范围内，某个整数存在与否，只有两种情况，在或者不在，那么，我们可以考虑只用一个bit位，来表示该整数存在的状态，从而达到节省内存的目的。
位图实例分析：
给一个实际的例子，给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中
我们可以简单计算一下，40亿个整数全部放到内存，需要160亿个字节，粗略计算，大致需要16G的内存，如果我们把每个整数是否出现，转换成用一位来表示它存在的状态，需要5亿个字节，也就是大约500M的内存，对于计算机而言，对内存的节省亦常地重要，这就是位图的一个重要应用。
位图模拟实现：
首先我们考虑位图的结构，实际上也是对数组的封装，只不过我们这里需要的是以bit位为单位进行存放，每一位的状态只有0和1两种，这里用来表示该整数是否在位图内。
我们以一个×××为例，在一个×××的空间，存储【1 6 9 4 12 10】这些数，存储结果应该如下：
这个只给出了两个字节，全可以表示上面的6个整数。
关于位图的底层，这里我们使用vector来模拟实现。
#include#include using namespace std; class BitMap { public: BitMap(const size_t& range) { int sz = (range >> 5) + 1; _vec.resize(sz); } void BitSet(const size_t& x) { int index = x >> 5; // index是x对应位所在的下标 int num = x % 32; // num是x对应该×××的第多少位 _vec[index] |= 1 << num; } void BitReSet(const size_t& x) { int index = x >> 5; // index是x对应位所在的下标 int num = x % 32; // num是x对应该×××的第多少位 _vec[index] &= (~(1 << num)); } bool BitTest(const size_t& x) { int index = x >> 5; // index是x对应位所在的下标 int num = x % 32; // num是x对应该×××的第多少位 return _vec[index] & (1 << num); } protected: vector _vec; };
位图的实现实际上就是进行一系列的位操作，通过位操作找到该×××对应的位，下面给出一组简单的测试用例
void TestBitMap()
{
BitMap mp(100);
mp.BitSet(1);
mp.BitSet(2);
mp.BitSet(11);
mp.BitSet(22);
cout << "test --<1>" << mp.BitTest(1) << endl;
cout << "test --<2>" << mp.BitTest(2) << endl;
cout << "test --<11>" << mp.BitTest(11) << endl;
cout << "test --<22>" << mp.BitTest(22) << endl<" << mp.BitTest(1) << endl;
cout << "test --<2>" << mp.BitTest(2) << endl;
cout << "test --<11>" << mp.BitTest(11) << endl;
cout << "test --<22>" << mp.BitTest(22) << endl << endl;
}
源码库中的位图：
在源码库中，有这样一个容器 bitset，和我们这里的bitmap性质基本是一样的，当然，功能要比上面实现的位图大得多。
A bitset is a special container class that is
designed to store bits (elements with only two possible values: 0 or 1,
true or false, ...).
The class is very similar to a
regular array, but optimizing for space allocation: each element occupies only
one bit (which is eight times less than the smallest elemental type in C++:
char).
Each element (each bit) can be accessed individually: for
example, for a given bitset named mybitset, the expression
mybitset[3] accesses its fourth bit, just like a regular array accesses
its elements.
Because no such small elemental type exists in most C++
environments, the individual elements are accessed as special references which
mimic bool elements:
库中提供了一系列的函数操作，除了set、reset、test之外，常用的还有filp<取反操作>，count<统计位为1的个数>。关于bitset的操作，都包含在
#include
的头文件中。
位图的分析与扩展：
位图的确用起来会很方便，但并不是任何情况下都需要使用到位图的，位图通常是为了处理大量数据，内存中不足以存放所有的数字才使用的一种数据结构，因为位图也有着一定的缺陷：
1> 它的可读性差
2> 位图在视图节约空间的时候，也伴随着一定的消耗，它要求给最大值和最小值之间的所有数都要占用一个bit位，当数据过于分散而数据量又不至太大的情况，位图其实是一种比较浪费空间的做法。如果最小值为10000，位图开辟出来的前10000个bit位其实就空了出来，没有利用到，之前我们举得例子，40亿个整数，因为无符号整数的最大值就到42.9亿左右，大部分的整数值确定都已经被取到，因此我们采用了位图来实现。
3> 当位图用来存储有符号整数时，有两种解决方案，一种是我们约定好最小值不再从0开始，所有的计算都需要减去有符号整数的最大值，另一种是这里采用两位来存储一个数，用两位来表示正数、负数、不存在三种状态。
试想，如果我们要求统计40亿个无符号整数中，出现两次以上的数该如何处理？
。。。。。。
同样，多加一位标志位，用两个bit位来进行处理，那这样的话，就需要我们自己来实现一个基本的两位为一个单元的位图结构。
除此之外，位图还可用来排序，判重，当然这里仅仅限于无符号整数，和上一节的哈希一样，受限于整数范围确实是个不好的地方，下一谈会提到字符串哈希算法与布隆过滤器，正是由于字符串哈希算法，才使得这些数据结构得以大范围的使用。
关于哈希算法： http://muhuizz.blog.51cto.com/11321490/1870717
-----muhuizz整理
网站题目：海量数据处理第二谈-----位图BitMap
网页路径：http://scyingshan.cn/article/ghopcc.html
