学步园

位图数据结构，就是用一块内存区域的每个比特表示一个对象的数据结构。

叫做 bitmap 或者 bitplane。

优点是速度快，内存空间占用小，能表示大范围的数据。

《Programming Pearls》里面举了一个例子，假设要对0到一千万范围内的、没有重复元素的正整数排序，

则利用位图数据结构很合适。

要使用位图数据结构，就必须熟悉位操作。

以下是已经写好的操作位图数据结构的实用函数：

#define BITS_PER_BYTE 8
#define BITS_PER_INT (BITS_PER_BYTE * 4)
// set the bit of the int specified by index to 1.
// the index is zero-based, counting from the left(the higher end)
inline void pearl_int_set(int* data, int index)
{
	int mask = 1 << (BITS_PER_INT - 1 - index);
	*data |= mask;
}

// test whether a bit of the int specified by index is 1.
// the index is zero-based, counting from the left(the higher end)
inline int pearl_int_test(int* data, int index)
{
	int mask = 1 << (BITS_PER_INT - 1 - index);
	return (*data) & mask;
}

// set a bit of the int specified by bit_index to 0.
// the index is zero-based, counting from the left(the higher end)
inline void pearl_int_clear(int *data, int bit_index)
{
	int mask = ~(1 << (BITS_PER_INT - 1 - bit_index));
	*data &= mask;
}

// get the right(lower) part of the int.
inline int pearl_int_right(int *data, int count)
{
	int mask = 1;
	while(count > 0) {
		mask = mask << 1 + 1;
	}
	return *data & mask;	
}

// get the left(upper) part of the int value
inline int pearl_int_left(int *data, int count)
{
	int mask = 1;
	count = BITS_PER_BYTE - count;
	while (count > 0) {
		mask = mask << 1 + 1;
	}

	mask = ~mask;
	return *data & mask;
}

// set a bit of the speicified memory area to 1.
// @warning this function does NOT perform error checking.
inline void pearl_set(int *bitplane, int index)
{
	int offset = index / BITS_PER_INT;
	int pos = index - offset * BITS_PER_INT;

	pearl_int_set(bitplane + offset, pos);
}

// set a bit of the specified memory area to 0.
// @warning this function does NOT perform error checking.
inline void pearl_clear(int *bitplane, int index)
{
	int offset = index / BITS_PER_INT;
	int pos = index - offset * BITS_PER_INT;

	pearl_int_clear(bitplane + offset, pos);
}

// test if a bit of the specified memory area is 1.
// @warning this function does NOT perform error checking.
inline int pearl_test(int *bitplane, int index)
{
	int offset = index / BITS_PER_INT;
	int pos = index - offset * BITS_PER_INT;

	return pearl_int_test(bitplane + offset, pos);
}

约定：

所有比特的编号方法是，从低字节的高位比特位开始，第一个bit为0，最后一个bit为 n-1。

例如，假设 int arr[4] 表示一块内存区域，共16个字节，共128个比特，第1个整数 arr[0] 的高比特（从左边数，第1个字节，第1个比特）为第0个比特。

因此，上面程序与机器是大端还是小端模式无关。

图解：

编号：  |0123456------->-------

              |00000000 | 00000000 | 00000000 | 00000000 | 00000000 | 00000000 | 00000000 | 00000000 |....

              |<-------------------arr[0]--------------------------->|<---------------arr[1]--------------------------------->....

用法举例：

int main(int argc, char* argv[]) {
    int* bitplane = (int*)malloc(sizeof(int)*SIZE);
    pearl_set(bitplane, n); // 0 <= n <= SIZE * 4 * 8 - 1
    if ( pearl_test(bitplane, n) ) {
        printf("bit(%d) is set\n", n);
    }
    pearl_clear(bitplane, n);
    if ( pearl_test(bitplane, n) ) {
        printf("bit(%d) is cleared\n", n);
    }
    return 0;
}