BitMap 博客分类： 寒假小结 BitMap

问题：
    腾讯要统计自己的注册用户总量，考虑到有的用户用一个IP同时注册了扣扣,DNF和LOL，为了不重复统计，要将超内存的整型数据进行排重操作。
   
初级想法：
    为了解决大型数组排重问题，我们先了解一下bitmap这个概念。bit指位，map指映射。bitmap，顾名思义，就是指输入的整型数能用bit数组中的数一一对应表示出来。也就是说，我们可以建立一个很大的“bit数组”，这个数组足以映射到所有的整型，于是乎我们用一个bit（一个位）表示一个int（32位），只用了原数据的三十二分之一的空间就完成了。

遇到的问题：
    现在，我们面临的最最重要的问题是：我们的电脑无法直接对位进行操作！！！

解决问题的思路：
    问题到这里，似乎成了一个死结，我们只能用一个byte表示一个int了，节省四分之三的空间，但这远远达不到需求。
    试想，我们能否通过byte间接操作bit呢？
    一个byte占据八位的存储空间，如果我们找到了一种方法使得一个byte表示八个整型数据，就间接找到了我们理想化的方法。

实际解决步骤：
    下面开始讨论这个大数组排重问题的具体实现思路。
    1）创建一个byte数组，长度为2的29次方，把所有的byte置0。
    2）对应输入的int型数据，先对8取整得m，并把byte[m]转化为二进制数表示。
    3）对8取余得到n，将byte[m]的第n位置1。（对于这部分代码，可以当做字符串来处理，当然，熟悉位操作的同学可以通过移位实现。）


    到这里，腾讯的用户统计问题就解决了。童鞋们，开始写代码喽。