转：Bit-Map思想与2-BitMap思想

1. Bit-map思想

给你一堆西安市的电话号码列表，数量大概在千万级，要求从中找出所有重复的电话号码，需要时间复杂度尽可能小。

目前西安市的电话号码大概都以8开头，为8位，也就是类似于82678578这样子

二重暴力搜索时间复杂度太高，这里我们不予考虑。

容易想到的办法就是建立一个标志数组，int boolean都行，用相应的位置值来代替这个号码是否出现，

根据数组的可直接存取特性，来提高效率。但是你是否想过或测试过

int[] a = new int[100000000];

boolean[] a = new boolean[100000000]; //需要大概100M*4的内存，如果

这样类似的语句是否可以通过编译并且执行。

再仔细思考下，就会发现，int型的字段太过于占空间，我们只需要知道这个号码存在与否，

所以最简单的0和1就够用了，能表示0和1的最小存储单位是什么呢？

是内存中的一位。//int 为4 byte  ,那么1个int 可以存放32位；

申请一个int一维数组，那么可以当作为列为32位的二维数组，

            |                            32位                                      |

int a[0] |0000000000000000000000000000000000000|

int a[1] |0000000000000000000000000000000000000|

………………

int a[N] |0000000000000000000000000000000000000|

每一个电话号码，用上面的一位表示，如电话80000000可以用a[0]的第一位表示，有则是表示为1，无则是0

OK，这就是bitmap的思想。

将西安市的电话号码去掉开头的8，就可以将其映射到一个1到10000000的数组中。

8bit是1byte,1024byte是1kb,1024kb是1mb

所以10000000个bit占用的空间为10000000/8/1024/1024mb大概为1mb多些，

这对于现在大家动不动几G的内存来说，完全是小菜一碟。

2. 2-Bitmap实现

在2.5亿个整数中找出不重复的整数，内存不足以容纳这2.5亿个整数。*/

每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义
    #include<stdio.h>  
    #include<memory.h>  
    //用char数组存储2-Bitmap,不用考虑大小端内存的问题  
    unsigned char flags[1000]; //数组大小自定义   
    unsigned get_val(int idx)  
    { 

|    8 bit     |

|00 00 00 00|  //映射3 2 1 0

|00 00 00 00| //表示7 6 5 4

……

|00000000|

        int i = idx/4;  //一个char 表示4个数，
        int j = idx%4;  
        unsigned ret = (flags[i]&(0x3<<(2*j)))>>(2*j);  //0x3是0011 j的范围为0-3，因此0x3<<(2*j)范围为00000011到11000000

如7 i= ,j=3 那么flags[1]&11000000, 得到的是|00 00 00 00| //表示7 6 5 4
        return ret;  
    }  
      
    unsigned set_val(int idx, unsigned int val)  
    {  
        int i = idx/4;  
        int j = idx%4;  
        unsigned tmp = (flags[i]&~((0x3<<(2*j))&0xff)) | (((val%4)<<(2*j))&0xff);  
        flags[i] = tmp;  
        return 0;  
    }  
    unsigned add_one(int idx)  
    {  
        if (get_val(idx)>=2) {  //这一位置上已经出现过了？？
            return 1;  
        }  
        else  {  
            set_val(idx, get_val(idx)+1);  
            return 0;  
        }  
    }  
      
    //只测试非负数的情况;  
    //假如考虑负数的话,需增加一个2-Bitmap数组.  
    int a[]={1, 3, 5, 7, 9, 1, 3, 5, 7, 1, 3, 5,1, 3, 1,10,2,4,6,8,0};  
      
    int main()  
    {  
        int i;  
        memset(flags, 0, sizeof(flags));  
          
        printf("原数组为:");  
        for(i=0;i < sizeof(a)/sizeof(int); ++i)  {  
            printf("%d  ", a[i]);  
            add_one(a[i]);  
        }  
        printf("\r\n");  
      
        printf("只出现过一次的数:");  
        for(i=0;i < 100; ++i)  {  
            if(get_val(i) == 1)  
                printf("%d  ", i);  
        }  
        printf("\r\n");  
      
        return 0;  
    }  


除了用2-Bitmap来计数标记以外,也可以用两个1-Bitmap来实现(如果考虑正负数的情况,就四个1-Bitmap)