位图：Bitmap
A bit array (also known as bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level parallelism in hardware to perform operations quickly. A typical bit array stores kw bits, where w is the number of bits in the unit of storage, such as a byte or word, and k is some nonnegative integer. If w does not divide the number of bits to be stored, some space is wasted due to internal fragmentation.
下面给出位图的实现：#pragma warning(disable:4996)
#include
#include
#include
using namespace std;
//位图：Bitmap类
class Bitmap
{
private:
char* M;//比特图所存放的空间M[]，容量为N*sizeof(char)*8比特
int N;
protected:
void init(int n)
{
N = (n + 7) / 8;
M = new char[N];
memset(M, 0, N);
}
public:
Bitmap(int n = 8)
{
init(n);//按指定或默认规模创建比特图
}
Bitmap(char* file, int n = 8)
{
//按指定规模或者默认规模，从文件之中读取比特图
init(n);
FILE* fp = fopen(file, "r");
fread(M, sizeof(char), N, fp);
fclose(fp);
}
~Bitmap()
{
delete[]M;
M = NULL;//析构时释放比特图空间
}
void set(int k)
{
expand(k);
M[k >> 3] |= (0x80 >> (k & 0x07));
}
void clear(int k)
{
expand(k);
M[k >> 3] &= ~(0x80 >> (k & 0x07));
}
bool test(int k)
{
expand(k);
return M[k >> 3] & ((0x80) >> (k&0x07));
}
void dump(char* file)
{
//将位图整体导出至指定文件，以便此后对新的位图进行整体初始化
FILE* fp = fopen(file, "w");
fwrite(M, sizeof(char), N, fp);
fclose(fp);
}
char* bits2string(int n)
{
//将前N位转换为字符串
expand(n - 1);//此时可能被访问的最高位为bitmap[n-1]
char* s = new char[n + 1];
s[n] = '\0';
for (int i = 0; i < n; i++)
{
s[i] = test(i) ? '1' : '0';
}
return s;//返回字符串
}
void expand(int k)//若被访问的Bitmap[k]已出界，则需扩容
{
if (k < 8 * N)
{
return;//若仍在界内，无需扩容
}
int oldN = N;
char* oldM = M;
init(2 * k);//与向量类似，加倍策略
memcpy_s(M, N, oldM, oldN);
//将元数据转移至新的的空间
delete[] oldM;
}
};
int main()
{
int n = 1000;
Bitmap bt(n);
for (int i = 0; i< n; i++)
{
bt.set(i);
}
if (bt.test(20000))
{
cout << "founded!" << endl;
}
else
{
cout << "not founded!" << endl;
}
system("pause");
return 0;
}
在上述实现过程中使用了位运算，这里的是现实充分考量了计算机做数据存储的特点，以及位图数据结构的优势。请大家仔细思考。
大致解释如下：
①：如何由一个整数k定位到指定位置？
思路是先定位到第k比特所在的字节位置，然后在计算出它所在这个字节的第几位。因为一个字节（char）占8位，所以可以由 k >> 3 算出第k比特所在字节位置，这里设找到的这个字节位 b。然后计算它所在8位字节 b 的第几位，用 k % 8 即可得到，写成位运算 k & 0x07 ，获得低三位所等价的数字，这里设为 x。
②
定位到了指定位，如何修改它？
已经找到了第k比特在字节 b 的 第 x 位。如果要将k添加进位图，就需要将字节 b 的 第 x 位设置为1，只需用一个第 x 位为1的字节与字节 b 做或运算即可。构造这样的字节：0b 1000 0000 >> x（就是：0x80 >> (k & 0x07)），就可以将字节第 x 为设为1。然后通过位运算 | ，M[k >> 3] |= (0x80 >> (k & 0x07))。
作者：dos diosas
