面对大数据的处理（bitmap）

随着大数据的时代来临，越来越多的数据的等待着我们去管理，而越来越多的数据的管理也就意味着消耗大量的资源，

为了让我们的数据占有更小的空间。我们必须引用一个叫“位”的东西去处理。

比如：

举个例子，我们要实现：

给定100亿个整数，设计算法找到只出现一次的整数

我们可以使用hash将所有整数映射到1000个文件中，在每个文件中使用 bitmap（位表示），用两个bit表示出现次数，00表示没出现过，01表示出现过1次，10表示出现过多次，11舍弃，最后归并每个文件中出现只有1次的数即为所求。我们称这种方法为“哈希分桶法”。

我们就设计一个简单的“位图(bitmap)”

#include<iostream>

using namespace std;

    class BitMap{
    public:
        BitMap(){
            bitmap = NULL;
            size = 0;
        }
        BitMap(int size){ // contractor, init the bitmap
            bitmap = NULL;
            bitmap = new char[size];
            if (bitmap == NULL) {
                printf("ErroR In BitMap Constractor!\n");
            }else{
                memset(bitmap, 0x0, size * sizeof(char));
                this->size = size;
            }
        }
     
     
        /*将该位设置成1；
         * set the index bit to 1;
         */
        int bitmapSet(int index){
            int addr = index/8;
            int addroffset = index%8;
            unsigned char temp = 0x1 << addroffset;
            if (addr > (size+1)) {
                return 0;
            }else{
                bitmap[addr] |= temp;
                return 1;
            }
        }
     
        /*
         * return if the index in bitmap is 1;
         */
        int bitmapGet(int index){
            int addr = index/8;
            int addroffset = index%8;
            unsigned char temp = 0x1 << addroffset;
            if (addr > (size + 1)) {
                return 0;
            }else{
                return (bitmap[addr] & temp) > 0 ? 1 : 0;
            }
        }
     
        /*
         * del the index from 1 to 0
         */
        int bitmapDel(int index){
            if (bitmapGet(index) == 0) {
                return 0;
            }
            int addr = index/8;
            int addroffset = index%8;
            unsigned char temp = 0x1 << addroffset;
            if (addr > (size + 1)) {
                return 0;
            }else{
                bitmap[addr] ^= temp;
                return 1;
            }
        }
     
    private:
        char *bitmap;
        int size;
    }