位图

1、简介
位图的基本概念是用一个比特位来标记某个数据的存放状态，由于采用了位为单位来存放数据，所以节省了大量的空间。

应用方面可以在海量数据中去除重复数据，给不重复数据排序，判断某个数据书否在某一堆数据中，数据压缩等。

缺点是不适合多状态 一个bit只能表示两种状态，如果要表示更多的状态，就需要更多的状态位来实现。
如果一个数字需要多个状态位来表示的话，位图的优越性也会大打折扣，而且复杂度却在增加。

2、下面写一个C语言的判断给定数字是否在原始数据中的代码:

#include <stdio.h>
#include <string.h>

void init(int *bit, int *data, int bit_length, int data_length)
{
    int i;
    int n, m;
    memset(bit, 0, bit_length * sizeof(bit[0]));
    for (i = 0; i < data_length; i++)
    {
        n = data[i] / (sizeof(bit[0])*8);
        if (n > bit_length)
            continue;
        m = data[i] % (sizeof(bit[0])*8);
        bit[n] |= (1 << m); // 把第m位 置1
    }
}

int existence(int bit[], int length, int x)
{
    int n = x / (sizeof(bit[0])*8);
    if (n > length)
        return 0;
    int m = x % (sizeof(bit[0])*8);
    int r = bit[n] & (1 << m); // 取出 第m位
    return (0 == r ? 0 : 1);
}

int main()
{
    int data[] = {3, 2, 6, 5, 8, 4, 60, 30}; // 原始数据
    int bit[2];

    // 初始化位图
    init(bit, data, sizeof(bit) / sizeof(bit[0]), sizeof(data) / sizeof(data[0]));
    
    // 判断某数字是否存在数组 data 中
    printf("%d\n", existence(bit, sizeof(data) / sizeof(data[0]), 9));
    printf("%d\n", existence(bit, sizeof(data) / sizeof(data[0]), 60));
    printf("%d\n", existence(bit, sizeof(data) / sizeof(data[0]), 160));

    return 0;
}

3、位图在 C++ 中有实现bitset类。
上面的C代码换成C++ 代码如下：

#include <iostream>
#include <bitset>
using namespace std;

void init(bitset<64> &bit, int *data, int data_length)
{
    int i;
    
    for (i = 0; i < data_length; i++)
    {
        if (data[i] >= bit.size())
            continue;
        bit.set(data[i], 1); // 将第n位置1
    }
}

int existence(bitset<64> &bit, int x)
{
    if (x >= bit.size())
        return 0;
    if (bit.test(x)) // 或者 if (bit[x] == 1)
        return 1;
    return 0;
}

int main()
{
    int data[] = {3, 2, 6, 5, 8, 4, 60, 30}; // 原始数据
    bitset<64> bit;

    // 初始化位图
    init(bit, data, sizeof(data) / sizeof(data[0]));
    
    // 判断某数字是否存在数组 data 中
    cout << existence(bit, 9) << endl;
    cout << existence(bit, 60) << endl;
    cout << existence(bit, 160) << endl;

    return 0;
}