使用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 << j);
        if (val > 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 类的使用，我们可以更方便地进行位运算和集合运算。在实际应用中，需要根据实际需求选择合适的方法和算法。