使用Java BitSet 類實現位集合操作

一、BitSet 類概述

Java BitSet 類表示一組簡單的開關或標誌。它內部由一個長整型數組（long[]）實現，其中每個元素都代表64位的二進位數，這些二進位數的每一位可看作一個開關，開關只有兩種狀態，即打開（1）和關閉（0）。可以通過調整這些開關的狀態，來進行一些位運算操作。BitSet 類封裝的是一組位，因此集合運算也可以被實現。該類是線程安全的。

二、BitSet 類的常用方法

1.void set(int index)

將指定的位設置為 true。index 參數表示要設置的位的索引（第一個位的索引是0），該方法不會返回任何值。

BitSet bitSet = new BitSet(8);
bitSet.set(0);
bitSet.set(2);
System.out.println(bitSet); // 輸出{0, 2}

2.void clear(int index)

將指定的位設置為 false。index 參數表示要清除的位的索引（第一個位的索引是0），該方法不會返回任何值。

BitSet bitSet = new BitSet(8);
bitSet.set(0);
bitSet.set(2);
bitSet.clear(2);
System.out.println(bitSet); // 輸出{0}

3.boolean get(int index)

返回指定位的值。index 參數表示要查詢的位的索引（第一個位的索引是0），如果該位是開啟的則返回 true，否則返回 false。

BitSet bitSet = new BitSet(8);
bitSet.set(0);
System.out.println(bitSet.get(0)); // 輸出true

4.int nextClearBit(int fromIndex)

返回第一個未被設置為開啟的位的索引（第一個位的索引是0），該索引的值大於或等於 fromIndex。如果不存在這樣的索引，則返回 bitSet 的大小：length()

BitSet bitSet = new BitSet(8);
bitSet.set(0);
bitSet.set(3);
int index = bitSet.nextClearBit(0);
System.out.println(index); // 輸出1

5.String toString()

將 BitSet 轉換成 String 類型。該方法返回包含所有位狀態的字元串。0 表示關閉狀態，1 表示開啟狀態，左邊的位是最高有效位。

BitSet bitSet = new BitSet(8);
bitSet.set(0);
bitSet.set(2);
System.out.println(bitSet.toString()); // 輸出「00000101」

三、在實際應用中使用 BitSet 類

1. 應用場景1：少量整數的排序

如果需要對一個不大的整數集合進行排序，將集合中的每個值作為 BitSet 的索引，可以方便地進行排序。下面的示例中，我們將整數集合{1,3,5,7,9}排序：

BitSet bitSet = new BitSet();
int[] arr = {1,3,5,7,9};
for (int i : arr) {
    bitSet.set(i);
}
for (int i = 0; i < bitSet.size(); i++) {
    if (bitSet.get(i)) {
        System.out.print(i + " ");
    }
} // 輸出「1 3 5 7 9」

2. 應用場景2：按位存儲和傳輸數據

在某些情況下，需要按位存儲和傳輸數據。應用 BitSet 類可以方便地進行這些操作。下面是一個示例，我們使用 BitSet 類按位存儲和傳輸 5 個位元組的數據，然後再將其轉換回位元組形式：

BitSet bitSet = new BitSet();
byte[] bytes = {0b00010011, 0b01010101, 0b10101010, (byte) 0b11001100, (byte) 0b11110000};
for (int i = 0; i < bytes.length; i++) {
    for (int j = 0; j < 8; j++) {
        int val = bytes[i] & (1 < 0) {
            bitSet.set(i * 8 + j);
        }
    }
}
System.out.println(bitSet); // 輸出{0, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 26, 27, 28, 29, 30}
byte[] newBytes = new byte[5];
for (int i = 0; i < bitSet.size(); i += 8) {
    byte b = 0;
    for (int j = 0; j < 8; j++) {
        if (bitSet.get(i + j)) {
            b |= 1 << j;
        }
    }
    newBytes[i / 8] = b;
}
System.out.println(Arrays.toString(newBytes)); // 輸出「[19, 85, -86, -52, -16]」

3. 應用場景3：判斷兩個集合的交集和並集

使用 BitSet 類可以方便地實現位運算，進而實現原本需要較長的代碼實現的集合操作。下面的示例中，我們新建兩個 BitSet 類型的集合 bitSet1 和 bitSet2，其中 bitSet1 包含索引值為 1、3、5 和 7 的四個位，bitSet2 包含索引值為 3、4 和 5 的三個位。我們使用 and() 方法得到 bitSet1 和 bitSet2 的交集，使用 or() 方法得到 bitSet1 和 bitSet2 的並集：

BitSet bitSet1 = new BitSet();
BitSet bitSet2 = new BitSet();
bitSet1.set(1);
bitSet1.set(3);
bitSet1.set(5);
bitSet1.set(7);
bitSet2.set(3);
bitSet2.set(4);
bitSet2.set(5);
BitSet andBitSet = (BitSet) bitSet1.clone();
andBitSet.and(bitSet2);
System.out.println(andBitSet); // 輸出{3, 5}
BitSet orBitSet = (BitSet) bitSet1.clone();
orBitSet.or(bitSet2);
System.out.println(orBitSet); // 輸出{1, 3, 4, 5, 7}

四、總結

本文介紹了使用 Java BitSet 類實現位集合操作的概念和常用方法，並提供了三個常見的應用場景。通過對 BitSet 類的使用，我們可以更方便地進行位運算和集合運算。在實際應用中，需要根據實際需求選擇合適的方法和演算法。