欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BitMap 博客分类: 寒假小结 BitMap 

程序员文章站 2024-03-25 15:08:58
...
问题:
    腾讯要统计自己的注册用户总量,考虑到有的用户用一个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。(对于这部分代码,可以当做字符串来处理,当然,熟悉位操作的同学可以通过移位实现。)


    到这里,腾讯的用户统计问题就解决了。童鞋们,开始写代码喽。
相关标签: BitMap