位示圖

位示圖是利用二進制的一位來表示磁碟中的一個盤塊的使用情況。當其值為“0”時，表示對應的盤塊空閒；為“1”時，表示已經分配。有的系統把"0"作為盤塊已分配的標記，把“1”作為空閒標誌。(它們的本質上是相同的，都是用一位的兩種狀態標誌空閒和已分配兩種情況。)磁碟上的所有盤塊都有一個二進制位與之對應，這樣，由所有盤塊所對應的位構成一個集合，稱為位示圖。

基本介紹

• 中文名：位示圖
• 外文名：bitmap
• 作用：表示磁碟中的一個盤塊的使用情況
• 套用領域：索引，數據壓縮

簡介

位示圖是利用二進制的一位來表示磁碟中的一個盤塊的使用情況。當其值為“0”時，表示對應的盤塊空閒；為“1”時，表示已經分配。有的系統把"0"作為盤塊已分配的標記，把“1”作為空閒標誌。(它們的本質上是相同的，都是用一位的兩種狀態標誌空閒和已分配兩種情況。)磁碟上的所有盤塊都有一個二進制位與之對應，這樣，由所有盤塊所對應的位構成一個集合，稱為位示圖。通常可用m*n個位數來構成位示圖，並使m*n等於磁碟的總塊數。

位示圖也可描述為一個二維數組map:

Var map：array of bit；

位示圖用於存儲空間的分配和回收。

位示圖的實現

1. 定義：

位示圖（bitmap）又叫點陣圖，它的最小單元是一個bit。每個bit有兩種取值1或0。

位示圖是一種非常常用的結構，在索引，數據壓縮等方面有廣泛套用。本文介紹了點陣圖的實現方法及其套用場景。

2. 實現

在C/C++中沒有位示圖這種數據類型，下面我們利用int來實現一個位示圖類

每個int有sizeof(int)*8個bit

3.代碼

#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 0x1fclass 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;};

4. 測試代碼

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;    }}