使用BitSet位集合,一个重复校验工具

目录

BitSet位集合，一个重复校验工具BitSet的基本用法

概念基本操作题目

BitSet位集合，一个重复校验工具

BitSet，位集合，用于判断一个int数字是否存在与bitSet中。
使用一个或多个long存储数据，占用内存超级小，因为判断64位二进制long中第n位为1表示n这个数字存在，为0表示不存在。所以一个long可以表示2^63 -1个数字的存在情况。
使用场景，如手机号重复校验，数字id重复校验，QQ号重复校验等大量防重的场景。
存在与否是精确的，说不存在绝对不存在，说存在绝对存在，不像布隆过滤器。
1.bitset的内部实现是long数组，因为一个long位数不够表示时，会扩展到多个long
2.set中每一个位的默认值为false（0）
3.bitset长度按需增长
4.bitset非线程安全

1.     public static void bitSetDemo() {
2.         /**
3.          BitSet,用于表示一个int是否在集合中，通过get方法来判断是否存在。
4.          底层使用一个long来表示数据，
5.          可以把long看成64位的01二进制，第n位为1表示n存在，
6.          第n位为0表示n不存在。
7.          */
8.         BitSet bs = new BitSet(10);
9.         bs.set(1);
10.         bs.set(2);
11.         bs.set(5);
12.         System.out.println(bs.get(2));//true
13.         System.out.println(bs.get(1));//true
14.         System.out.println(bs.get(3));//false，不存在
15.         System.out.println(bs.get(5));//true
16.         //返回bitSet中已存入的数量
17.         System.out.println(bs.cardinality());//3
18.         //逻辑位数
19.         System.out.println(bs.length());//6
20.         //实际位数
21.         System.out.println(bs.size());//64
22.         System.out.println(bs.toString());//{1, 2, 5}
23.         BitSet bs2 = new BitSet();
24.         bs2.set(1);
25.         bs2.set(2);
26.         bs2.set(6);
27.         System.out.println(bs2.toString());//{1, 2, 6}
28.         //取交集，两者都有的才保留
29.         bs.and(bs2);
30.         System.out.println(bs.toString());//{1, 2}
31.         //取并集，把两者所有的都保留
32.         bs.or(bs2);
33.         System.out.println(bs.toString());//{1, 2, 6}
34.     }

复制代码

BitSet的基本用法


概念

bitset可以说是一个多位二进制数，每八位占用一个字节，因为支持基本的位运算，所以可用于状态压缩，n位bitset执行一次位运算的时间复杂度可视为n/32.

基本操作

1.定义：

bitset< n > s;

表示一个n位的二进制数，<>中填写位数；
2.位运算操作符：

~s: 返回对s每一位取反后的结果；&，|，^：返回对两个位数相同的bitset执行按位与、或、异或运算的结果；<<, >>:返回把一个bitset左移，右移若干位的结果.（补零）；==，！=：比较两个位数相同的bitset代表的二进制数是否相等；

3.[ ]操作符：

s[k] :表示s的第k位，即可取值也可赋值，编号从0开始；

4.count:

s.count() 返回二进制串中有多少个1；

5.any/none
若s所有位都为0，则s.any()返回false，s.none()返回true；
若s至少有一位为1，则s.any()返回true，s.none()返回false；
6.set/rest/flip

s.set()把s所有位变为1；s.set(k,v)把s的第k位改为v,即s[k]=v；s.reset()把s的所有位变为0.s.reset(k)把s的第k位改为0,即s[k]=0；s.flip()把s所有位取反.即s=~s；s.flip(k)把s的第k位取反，即s[k]^=1；

题目

可达性统计（AcWing164）

思路：
遍历一遍图，在回溯时将子节点状态加入节点状态中，用一个n长度的二进制bitset串记录状态第i位为1表示i节点从该节点可达，最后输出每个节点状态中1的个数即可。遍历时从入度为1的节点开始.
代码：

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long ll;
4. typedef unsigned long long ull;
5. const ll inf=1e9+7;
6. bitset<30005> s[30005];
7. vector<int> g[30005];
8. int in[30005], vis[30005];
9. queue<int> q;
10. void dfs(int v)
11. {
12.     //printf("v=%d\n",v);
13.     if(vis[v])
14.     {
15.         return ;
16.     }
17.     s[v][v]=1;
18.     for(int i=0;i<g[v].size();i++)
19.     {
20.         int u=g[v][i];
21.         dfs(u);
22.         s[v]|=s[u];
23.     }
24.     vis[v]=1;
25. }
26. int main()
27. {
28.     int n, m;
29.     scanf("%d%d",&n,&m);
30.     for(int i=1;i<=m;i++)
31.     {
32.         int u, v;
33.         scanf("%d%d",&u,&v);
34.         g[u].push_back(v);
35.         in[v]++;
36.     }
37.     for(int i=1;i<=n;i++)
38.     {
39.         if(in[i]==0)
40.         {
41.             q.push(i);
42.         }
43.     }
44.     while(!q.empty())
45.     {
46.         int v=q.front();
47.         q.pop();
48.         dfs(v);
49.     }
50.     for(int i=1;i<=n;i++)
51.     {
52.         printf("%d\n",s[i].count());
53.     }
54. }

复制代码

以上为个人经验，希望能给大家一个参考，也希望大家多多支持中国红客联盟。