位图法

本文总结下位图法在数据去重方面的使用，全文分为三个部分：

• 一是位图法的定义

• 二是使用位图法判断数据是否存在

• 三是使用位图法找出不重复的数据

最后，附上C++的实现。

位图法

假设我们有40亿的unsigned int 数据，若我们用unsigned int的方式加载到内存，那么需要：40亿 * 4 / 1024 / 1024 = 15258MB 的内存。若我们把每一个数字的值作为数组下标，用一个位数组来表示每个数字的状态，那么空间则缩短了32倍(假设int占用空间为4字节)，即仅仅需要 15258 / 32 = ‭476MB 的内存。

这个方法就叫做位图法。

用位图法判断数据是否存在

基本方法为：申请一块内存，使得bit的数量和需要判断的数字的数量一样. 然后加载所有数字，把数字作为下标所对应的位置为1。

查找的时候，则判断对应的位是否为 1，是则存在，否则不存在。C++实现如下：

#include <bitset>
#define MAX_NUMS 1000000

bool findNumInBigData(vector<int> &array, int num){
    bitset<MAX_NUMS> bitArray;
    for (auto item : array)
        bitArray[item] = 1;
    return bitArray[num];
}

用位图法获取不重复数据

基本方法和上面相同，只不是这次用两位来表示一个数据的状态，若数据重复了则将两位置为11，只出现一次则将两位置为01，没有出现则两位为00。

最后遍历位数组得到所有不重复的数字，C++实现如下：

#include <bitset>
#define MAX_NUMS 1000000

vector<int> findUnRepetitiveNums(vector<int> &array){
    bitset<MAX_NUMS * 2> bitArray;
    for(auto item : array){
        item *= 2;
        if (!bitArray[item] && !bitArray[item + 1])
            bitArray[item + 1] = 1;
        else{
            bitArray[item] = 1;
            bitArray[item+1] = 1;
        }
    }
    vector<int> result;
    for(int i = 0; i < bitArray.size(); i+=2){
        if (!bitArray[i] && bitArray[i+1])
            result.push_back(i / 2);
    }
    return result;
}