2-bitmap

た入场券 2021-06-11 15:14 386阅读 0赞

思想很简单：原来8bit 代表8个数字，现在代表4个。按4获取index，按4取模获取 offset

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

思路：

bitmap用一个bit来代表存在还是不存在，现在我们要判断重不重复，则需要三个状态：不存在，存在一个，存在多个。2bits可以表示四个状态，令00表示不存在，01表示存在1个，10表示存在多个，11无意义。

令2bits用一个序号，最后只要判断某序号的2bits是01，则该序号就是不重复的。

整数一共有2^32=4G个，一个整数对应一个序号，一个序号对应2bits，也就是需要4G \* 2bits = 4G \* 1/4Byte = 1G的内存。

如果机器的内存没有1G，我们也可以先将所有数据分配到更小的文件中去，比如用%10，按余数分到19个文件里去（余数可能为-9~9），那么每个文件里整数的整数最多有约4G/20 = 0.2G个，一个整数对应一个序号，一个序号对应2bits，只要约0.05G。

无论是分成小文件还是部分，都只要找出序号对应的2bits是01的序号即可。

这里我们只考虑大端机，小端类似。

![复制代码][copycode.gif]

char getI(int i,char *p)
    {
        unsigned int un= i+(unsigned int)(1<<31);//int可能为负数,一一对应到正数
        unsigned int index = un/4;
        unsigned int offset = un%4;
        return (*(p+index)>>(3-offset)) & 0x03;
    }
    
    void setI(int i,char *p)
    {
        unsigned int un= i+(unsigned int)(1<<31);//int可能为负数,一一对应到正数
        unsigned int index = un/4;
        unsigned int offset = un%4;
        if(getI(i,p) == 0x00)  //00 -> 01
        {
            *(p+index) |= (0x40>>offset);
        }
        else if(getI(i,p) == 0x01) //00 -> 10
        {
            *(p+index) |= (0x80>>offset);
        }
    }

![复制代码][copycode.gif]

[copycode.gif]: /images/20210527/ceb6c6c5418c42c4997d9863331a6302.png

发表评论取消回复

表情：

评论列表（有 0 条评论，386人围观）

还没有评论，来说两句吧...

相关阅读

相关 BitMap

一. BitMap Bit-map的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，

古城微笑少年丶/ 2022年10月05日 15:43/ 0 赞/ 180 阅读

相关 BitMap算法

http://[blog.csdn.net/pipisorry/article/details/62443757][blog.csdn.net_pipisorry_articl

旧城等待，/ 2022年09月29日 15:53/ 0 赞/ 184 阅读

相关 Radis - Bitmaps

位存储。场景：统计疫情感染人数（未感染 0表示，感染1表示）、活跃于不活跃用户、登录未登录、打卡未打卡。只要是两个状态的，都可以使用 Bigmaps。 Bi

深藏阁楼爱情的钟/ 2022年08月29日 13:49/ 0 赞/ 206 阅读

相关 Bitmap.createBitmap 得到的bitmap 不一定是新的bitmap

File tempFile = null; try { Bitmap bitmap = BitmapUtils.createThumbnail(

男娘i/ 2022年07月31日 10:22/ 0 赞/ 9 阅读

相关 bitmap

业务需求对技术的要求是永无止境的。我们需要更好的工具： 1. 更快速的分析，一次任务就需要个把小时，甚至需要一天，数据的产出，无法支持我们业务的快速调整。 2. 更灵活的

古城微笑少年丶/ 2022年06月05日 07:55/ 0 赞/ 245 阅读

相关 redis-bitMap

记录一下使用bitMap的一些操作。 bit操作保存的数据只能是0或者1，这对于判断true/false的统计具备天然的优势。比如签到签退等等。同时也记录一下踩过

我不是女神ヾ/ 2022年05月22日 11:10/ 0 赞/ 171 阅读

相关创建BitMap

Bitmap pResource=(Bitmap)Image.FromFile("..\\\\..\\\\res\\\\animal.bmp"); Bitmap pBitMa

「爱情、让人受尽委屈。」/ 2021年11月17日 02:12/ 0 赞/ 332 阅读

相关 BitMap

[https://blog.csdn.net/kl1106/article/details/79478787][https_blog.csdn.net_kl1106_artic

分手后的思念是犯贱/ 2021年09月18日 14:20/ 0 赞/ 383 阅读

相关 Bitmap OutOfMemoryError

在创建Bitmap的时候因为对象过多而没有即使回收，导致的内存不足： java.lang.OutOfMemoryError E/AndroidRuntime(218

傷城~/ 2021年09月17日 13:18/ 0 赞/ 303 阅读

相关 2-bitmap

思想很简单：原来8bit 代表8个数字，现在代表4个。按4获取index，按4取模获取 offset 在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.

た入场券/ 2021年06月11日 15:14/ 0 赞/ 387 阅读