Bitset改進你的程式品質

1:Bitset介紹

BitSet 是用于存儲二進制位和對二進制進行操作的 自動去重Java 資料結構,

此類實作了一個按需增長的位向量。位 set 的每個元件都有一個 ​

​boolean​

​​ 值。用非負的整數将 ​

​BitSet​

​​ 的位編入索引。可以對每個編入索引的位進行測試、設定或者清除。通過邏輯與、邏輯或和邏輯異或操作，可以使用一個 ​

​BitSet​

​​ 修改另一個 ​

​BitSet​

​ 的内容。

預設情況下，set 中所有位的初始值都是 ​

​false​

​。 

2:優化空間

在程式runtime時,我們經常需要使用數組來記住程式的運作狀态,并且根據這些狀态及時 對資料做出更新,一般有以下處理辦法

• 使用 Int [] state=new int[22]; 儲存狀态
• 使用 boolean [] state = new boolean[22] 儲存狀态

分析可知,1byte=8bit  int占用4個位元組,如果考慮使用bit直接存儲狀态 ,将會大大節約時間, 不過在改變你的程式設計習慣之前,你應該清楚 我們如何儲存狀态,以及對于狀态的操作

3:Bitset常用api

建構

BitSet() 
          建立一個新的位 set。 預設64
BitSet(int nbits) 
          建立一個位 set，它的初始大小足以顯式表示索引範圍在 0 到 nbits-1      

 操作

更新:  
void set(int bitIndex) 
          将指定索引處的位設定為 true。 
 void set(int bitIndex, boolean value) 
          将指定索引處的位設定為指定的值。 
 void set(int fromIndex, int toIndex) 
          将指定的 fromIndex（包括）到指定的 toIndex（不包括）範圍内的位設定為 true。 
 void set(int fromIndex, int toIndex, boolean value) 
          将指定的 fromIndex（包括）到指定的 toIndex（不包括）範圍内的位設定為指定的值。 
擷取:      

​ ​boolean​ ​	​ ​get(int bitIndex)​ ​           傳回指定索引處的位值。
​ ​BitSet​ ​	​ ​get(int fromIndex, int toIndex)​ ​           傳回一個新的 BitSet，它由此 BitSet 中從 fromIndex（包括）到 toIndex（不包括）範圍内的位組成。

翻轉:      

​ ​boolean​ ​	​ ​get(int bitIndex)​ ​           傳回指定索引處的位值。
​ ​BitSet​ ​	​ ​get(int fromIndex, int toIndex)​ ​           傳回一個新的 BitSet，它由此 BitSet 中從 fromIndex（包括）到 toIndex（不包括）範圍内的位組成。

删除      

​ ​ void​ ​	​ ​clear()​ ​           将此 BitSet 中的所有位設定為 ​ ​false​ ​。
​ ​ void​ ​	​ ​clear(int bitIndex)​ ​           将索引指定處的位設定為 ​ ​false​ ​。
​ ​ void​ ​	​ ​clear(int fromIndex, int toIndex)​ ​           将指定的 fromIndex（包括）到指定的 toIndex（不包括）範圍内的位設定為 ​ ​false​ ​。

長度:      

​ ​ int​ ​

​ ​cardinality()​ ​           傳回此 ​ ​BitSet​ ​ 中設定為 true

​ ​int​ ​

​ ​length()​ ​           傳回此 ​ ​BitSet​ ​​ 的“邏輯大小”：​ ​BitSet​ ​ 中最高設定位的索引加 1。

​ ​ int​ ​

​ ​size()​ ​           傳回此 ​ ​BitSet​ ​ 表示位值時實際使用空間的位數。

重要: 周遊相關:      

​ ​ int​ ​	​ ​nextClearBit(int fromIndex)​ ​           傳回第一個設定為 ​ ​false​ ​ 的位的索引，這發生在指定的起始索引或之後的索引上。
​ ​ int​ ​	​ ​nextSetBit(int fromIndex)​ ​           傳回第一個設定為 ​ ​true​ ​ 的位的索引，這發生在指定的起始索引或之後的索引上。

4.BitSet 應用舉例

  統計随機個數

private final static int LEN_NUM = 10;
    public static void main(String[] args) {
        BitSet set = new BitSet();

        ArrayList<Integer> list = new ArrayList<>();

        Random random = new Random();
        for (int i = 0; i < LEN_NUM; i++) {
            list.add(random.nextInt(100));
        }
        for (int i = 0; i < list.size(); i++) {
            set.set(list.get(i));
        }
        for (int i = 0; i < 10; i++) {
            if(!set.get(i)) { //輸出不在10範圍以内的個數
                System.out.print(i+" ");
            }
        }
        System.out.println();
        System.out.println("有true的多少個"+set.cardinality());
    }      

 輸出素數:

// 原始
    public static void main(String[] s) {
        int n = 1000000;
        long start = System.currentTimeMillis();
        int[] hash = new int[n + 1];
        for (int i = 2; i < n; i++) {
            if (hash[i] == 0) {
                for (int j = 2 * i; j < n; j += i) {
                    hash[j] = 1;
                }
            }
        }
        long end = System.currentTimeMillis();
        System.out.println((end - start) + " ms");
    }
// 改進後的

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        BitSet bitSet = new BitSet(10000000);
        for (int i = 2; i < 1000000; i++) {
            if(!bitSet.get(i)) {
                for (int j = i*2; j <1000000 ; j+=i) {
                    bitSet.set(j,true);
                }
            }
        }
        for (int i = 0; i < 1000000; i++) {
            if(!bitSet.get(i)) {
                System.out.println(i+" ");
            }
        }
        long end = System.currentTimeMillis();
        System.out.println((end - start) + " ms");
    }      

對不同資料進行排序

場景是無序數組: 因為bitset 自動去重

private static  Random random=new Random();
        
        private static Set<Integer> set=new HashSet<>(); //
        
        public static void init() {
            for (int i = 0; i < 1000; i++) {
                set.add(random.nextInt(1000));
            }
        }
        
        public static void main(String[] args) {
            init();
            BitSet bitSet = new BitSet();
            
            Integer [] x=new Integer[set.size()];
            Integer[] array = set.toArray(x);
            for (int i = 0; i < array.length; i++) {
                bitSet.set(array[i]);
            }
            int bitLen=bitSet.cardinality();
            int[] orderedArray = new int[bitLen];
            
            int k=0;
            for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
                orderedArray[k++] = i;
            }
            
            for (int i = 0; i < bitLen; i++) {
                System.out.println(orderedArray[i]);
            }
        }      

并交補運算

public static void main(String[] args) {
        BitSet bitSet = new BitSet(100);
        bitSet.set(1);
        bitSet.set(2);
        bitSet.set(3);
 
        BitSet bitSet2 = new BitSet(100);
        bitSet2.set(2);
        bitSet2.set(3);
        bitSet2.set(5);
 
        System.out.println("剛開始的bitSet："+bitSet);
        System.out.println("剛開始的bitSet2："+bitSet2);
        System.out.println("------------------------------");
        //求并集
        bitSet.or(bitSet2);
        System.out.println("求完并集之後的bitSet："+bitSet);
        System.out.println("求完并集之後的bitSet2："+bitSet2);
        System.out.println("------------------------------");
        //使bitSet回到剛開始的狀态
        bitSet.clear(5);
 
        //求交集
        bitSet.and(bitSet2);
        System.out.println("求完交集之後的bitSet："+bitSet);
        System.out.println("求完交集之後的bitSet2："+bitSet2);
        System.out.println("------------------------------");
        //使bitSet回到剛開始的狀态
        bitSet.set(1);
        //此方法傳回在bitSet中不在bitSet2中的值，求的是bitSet相對于bitSet2的補集
        bitSet.andNot(bitSet2);
        System.out.println("求完補集之後的bitSet："+bitSet);
        System.out.println("求完補集之後的bitSet2："+bitSet2);
    }      

Bitset操作 是比較耗CPU的,但是速度快