数据结构————一种标记数组————位图（2.0）

太过爱你忘了你带给我的痛 2021-10-29 22:12 261阅读 0赞

##### 一、简单介绍 #####

位图就是用每一位 来标记一个数是否存在， 相比bool类型， 极大的节省了空间。
    
    如果你想存maxn个数，最多只要 开maxn/32 + 1个 int（32位）的数组就行。
    
    位图的操作：
    ①初始化为零，表示数数字都不存在
    ②标记某个数字
    ③删除某个数字的标记
    ④查询某个数字是否存在

##### 二、实现原理： #####

###### 1、初始化为0： ######

这个很简单，就是将数组初始化为0， 每一位就变为0了。

###### 2、标记某个数字： ######

举个例子， 如果你想将 数字1206标记：  
首先 1206 整除32 == 32  
然后 1026 mod 32 ==2  
所以只要将 下标为32的数组元素中第2位标记为1就行了。  
实现 :bitmap\[1026/32\] |= 1<<(1026%32);  
1026/32 可以换成1026>>5 , 1026%32 可以换成1026&31  
![在这里插入图片描述][20190817090522370.png]  
↓ 存完1026 后 bitmap\[32\]的二进制变化 ↓ ↓  
![在这里插入图片描述][20190817090451685.png]

###### 3、删除操作 ######

同样是1026.  
只要将 下标为32的数组元素第2位标记为0就行了。

实现：bitmap\[1026/32\]=bitmap\[1026/32\] & ~1(1026%32)。  
~：是按位取反操作， 要删除的位为0其他位为1， 这样就不影响其他位了。  
①按位取反  
![在这里插入图片描述][20190817090726634.png]

###### 4、查询操作： ######

同样也是1026.  
如果你想看这个数是否存在， 就看它对应的位置（32,2）是否标记为1就行。  
所以只要 return bitmap\[1026/32\]&1<<(1026%32);  
如果存在返回值为1，否则返回值为0.

#include<bits/stdc++.h>
    #define unint unsigned int
    using namespace std;
    const int maxn = 1e8+5;
    const int M = 6000005;
    const int SHIFT = 5;//2^5 == 32
    const int RADIX = (1<< SHIFT)-1;// 31
    
    int bitmap[(maxn>>SHIFT)+1];//存maxn个数
    
    
    
    void SetBit(int x)/**插入该数*/
    { 
        bitmap[x>>SHIFT]|=(1<<(x&RADIX));// x>>RSIFT相当于x/32 x&RADIX 相当于 x mod 32 操作
    }
    void clear(int i)/***删除操作****/
    { 
    	 bitmap[i >> SHIFT] &= ~(1 << (i & RADIX));
    }
    
    bool GetBit(int x)/**查找是否存在*/
    { 
        return bitmap[x>>SHIFT] & (1 <<(x&RADIX));
    }
    
    void init()/*初始化*/
    { 
    	memset(bitmap, 0 , sizeof(bitmap));
    }
    
    int main()
    { 
    
        
    
    
        return 0;
    }

[20190817090522370.png]: /images/20211029/4b79024cab5d401384143a6f3db5ecd4.png
[20190817090451685.png]: /images/20211029/38dcceb422c140de9b532d0b174b6284.png
[20190817090726634.png]: /images/20211029/0124e75fc9d44fc4a7dde33a9128c89a.png