-
位示圖
鎖定
- 中文名
- 位示圖
- 外文名
- bitmap
- 作 用
- 表示磁盤中的一個盤塊的使用情況
- 應用領域
- 索引，數據壓縮
位示圖簡介
位示圖通常可用m*n個位數來構成位示圖，並使m*n等於磁盤的總塊數。
位示圖也可描述為一個二維數組map:
Var map：array of bit；
位示圖用於存儲空間的分配和回收。
位示圖應用
位示圖（bitmap）又叫位圖，它的最小單元是一個bit。每個bit有兩種取值1或0。
位示圖是一種非常常用的結構，在索引，數據壓縮等方面有廣泛應用。
本文介紹了位圖的實現方法及其應用場景。
每個int有sizeof(int)*8個bit
位示圖代碼
#include<cassert>
#include<iostream>
using namespace std;
#define INT_BIT sizeof(int)
#define MAX 1024*1024*1024
#define SHIFT 5
#define UNIT INT_BIT << 3 // INT_BIT * 2^3
#define MASK 0x1f
class BitSet
{
public:
BitSet(int maxSize = MAX)
:_msize(maxSize)
{
pBitset = new int[_msize / UNIT + 1];
}
~BitSet()
{
if (pBitset){
delete[] pBitset;
}
}
void set(int i)
{
assert(i<_msize);
// i >> SHIFT = i / (2^5)
// i & MASK = i %
int j = i;
if (j>UNIT){
j >>= SHIFT;
}
pBitset[j] |= 1 << (i & MASK);
}
void clear(int i)
{
assert(i<_msize);
int j = i;
if (j>UNIT){
j >>= SHIFT;
}
pBitset[j] &= ~(1 << (i & MASK));
}
bool test(int i)
{
assert(i<_msize);
int j = i;
if (j>UNIT){
j >>= SHIFT;
}
return (pBitset[j] & (1 << (i & MASK)));
}
private:
int _msize;
int *pBitset;
};
位示圖測試代碼
int main()
{
BitSet bitset(100);
int i = 80;
bitset.set(i);
if (bitset.test(i)){
cout << "the pos " << i << " is seted" << endl;
}
else{
cout << "the pos " << i << " is not seted" << endl;
}
bitset.clear(i);
if (bitset.test(i)){
cout << "the pos " << i << " is seted" << endl;
}
else{
cout << "the pos " << i << " is not seted" << endl;
}
}
