使用BitSet位集合,一個重復校驗工具

更新時間：2022年10月31日 08:47:33 作者：阿拉的夢想

這篇文章主要介紹了使用BitSet位集合,一個重復校驗工具，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

BitSet位集合，一個重復校驗工具

BitSet，位集合，用于判斷一個int數(shù)字是否存在與bitSet中。

使用一個或多個long存儲數(shù)據(jù)，占用內存超級小，因為判斷64位二進制long中第n位為1表示n這個數(shù)字存在，為0表示不存在。所以一個long可以表示2^63 -1個數(shù)字的存在情況。

使用場景，如手機號重復校驗，數(shù)字id重復校驗，QQ號重復校驗等大量防重的場景。

存在與否是精確的，說不存在絕對不存在，說存在絕對存在，不像布隆過濾器。

1.bitset的內部實現(xiàn)是long數(shù)組，因為一個long位數(shù)不夠表示時，會擴展到多個long

2.set中每一個位的默認值為false（0）

3.bitset長度按需增長

4.bitset非線程安全

    public static void bitSetDemo() {
        /**
         BitSet,用于表示一個int是否在集合中，通過get方法來判斷是否存在。
         底層使用一個long來表示數(shù)據(jù)，
         可以把long看成64位的01二進制，第n位為1表示n存在，
         第n位為0表示n不存在。
         */
        BitSet bs = new BitSet(10);
        bs.set(1);
        bs.set(2);
        bs.set(5);
        System.out.println(bs.get(2));//true
        System.out.println(bs.get(1));//true
        System.out.println(bs.get(3));//false，不存在
        System.out.println(bs.get(5));//true
        //返回bitSet中已存入的數(shù)量
        System.out.println(bs.cardinality());//3
        //邏輯位數(shù)
        System.out.println(bs.length());//6
        //實際位數(shù)
        System.out.println(bs.size());//64
        System.out.println(bs.toString());//{1, 2, 5}
        BitSet bs2 = new BitSet();
        bs2.set(1);
        bs2.set(2);
        bs2.set(6);
        System.out.println(bs2.toString());//{1, 2, 6}
        //取交集，兩者都有的才保留
        bs.and(bs2);
        System.out.println(bs.toString());//{1, 2}
        //取并集，把兩者所有的都保留
        bs.or(bs2);
        System.out.println(bs.toString());//{1, 2, 6}
    }

BitSet的基本用法

概念

bitset可以說是一個多位二進制數(shù)，每八位占用一個字節(jié)，因為支持基本的位運算，所以可用于狀態(tài)壓縮，n位bitset執(zhí)行一次位運算的時間復雜度可視為n/32.

基本操作

1.定義：

bitset< n > s;

表示一個n位的二進制數(shù)，<>中填寫位數(shù)；

2.位運算操作符：

~s: 返回對s每一位取反后的結果；
&，|，^：返回對兩個位數(shù)相同的bitset執(zhí)行按位與、或、異或運算的結果；
<<, >>:返回把一個bitset左移，右移若干位的結果.（補零）；
==，！=：比較兩個位數(shù)相同的bitset代表的二進制數(shù)是否相等；

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所有位變?yōu)?；
s.set(k,v)把s的第k位改為v,即s[k]=v；
s.reset()把s的所有位變?yōu)?.
s.reset(k)把s的第k位改為0,即s[k]=0；
s.flip()把s所有位取反.即s=~s；
s.flip(k)把s的第k位取反，即s[k]^=1；

題目

可達性統(tǒng)計（AcWing164）

思路：

遍歷一遍圖，在回溯時將子節(jié)點狀態(tài)加入節(jié)點狀態(tài)中，用一個n長度的二進制bitset串記錄狀態(tài)第i位為1表示i節(jié)點從該節(jié)點可達，最后輸出每個節(jié)點狀態(tài)中1的個數(shù)即可。遍歷時從入度為1的節(jié)點開始.

代碼：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inf=1e9+7;
bitset<30005> s[30005];
vector<int> g[30005];
int in[30005], vis[30005];
queue<int> q;
void dfs(int v)
{
    //printf("v=%d\n",v);
    if(vis[v])
    {
        return ;
    }
    s[v][v]=1;
    for(int i=0;i<g[v].size();i++)
    {
        int u=g[v][i];
        dfs(u);
        s[v]|=s[u];
    }
    vis[v]=1;
}
int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u, v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        in[v]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        dfs(v);
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",s[i].count());
    }
}

以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: