Java BitSet 源码解析(3)

时间：2022-11-06 17:20:18

参考：

java.util.BitSet

Java BitSet类

查看类 ArrayList 中 removeIf 方法源码时，发现其使用 BitSet 类来存储待删除的元素下标

之前没有接触过这个类，了解之后发现其在数据查询和存储方面有很大用处

主要内容：

  1. BitSet 浅析
  2. 类变量和常量
  3. 构造器
  4. set
  5. clear -（2）
  6. get
  7. flip - (3)
  8. valueOf
  9. 位运算（and, andNot, or, xor）
  10. next
  11. previous - (4)
  12. 判空 / 判断交集
  13. 大小（length, size, cardinality）
  14. toByteArray 和 toLongArray
  15. BitSet 分析
  16. Java 素数查找
  17. 小结

flip

如果想要改变位集中的位值（就是从 true 变为 false，或者反之），可以使用函数 flip，类 BitSet 提供了 2 种重载方式

public void flip(int bitIndex)
public void flip(int fromIndex, int toIndex)
  • flip(int bitIndex)

源码如下：

public void flip(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    int wordIndex = wordIndex(bitIndex);
    expandTo(wordIndex);

    words[wordIndex] ^= (1L << bitIndex);

    recalculateWordsInUse();
    checkInvariants();
}

输入参数为位集下标

该函数功能是改变指定下标的位值

第一步：判断输入参数是否符合条件，否则抛出 IndexOutOfBoundsException 异常

第二步：计算输入位集下标对应的数组下标，并调用函数 expandTo 扩展数组

第三步：使用异或操作，改变对应的位值下标

第四步：调用函数 recalculateWordsInUse 重新计算当前已使用数组大小，调用函数 checkInvariants 判断类变量是否符合条件

  • flip(int fromIndex, int toIndex)

源码如下：

public void flip(int fromIndex, int toIndex) {
    checkRange(fromIndex, toIndex);

    if (fromIndex == toIndex)
        return;

    int startWordIndex = wordIndex(fromIndex);
    int endWordIndex   = wordIndex(toIndex - 1);
    expandTo(endWordIndex);

    long firstWordMask = WORD_MASK << fromIndex;
    long lastWordMask  = WORD_MASK >>> -toIndex;
    if (startWordIndex == endWordIndex) {
        // Case 1: One word
        words[startWordIndex] ^= (firstWordMask & lastWordMask);
    } else {
        // Case 2: Multiple words
        // Handle first word
        words[startWordIndex] ^= firstWordMask;

        // Handle intermediate words, if any
        for (int i = startWordIndex+1; i < endWordIndex; i++)
            words[i] ^= WORD_MASK;

        // Handle last word
        words[endWordIndex] ^= lastWordMask;
    }

    recalculateWordsInUse();
    checkInvariants();
}

该方法功能是改变位集下标为 [fromIndex, toIndex) 的位值

代码和 set(int fromIndex, int toIndex) 类似，不同的是该方法使用的位异或操作

valueOf

类 BitSet 提供了方法 valueOf，用于解析 long 型数组或者 byte 型数组，将其转换为 BitSet 对象，提供了 4 种重载方式

public static BitSet valueOf(long[] longs)
public static BitSet valueOf(LongBuffer lb)
public static BitSet valueOf(byte[] bytes)
public static BitSet valueOf(ByteBuffer bb)

4 种方法都将调用私有构造器

private BitSet(long[] words)

位运算（ and, andNot, or, xor）

不同 BitSet 对象之间也可以进行位运算，类 BitSet 提供了 4 种函数

public void and(BitSet set)
public void andNot(BitSet set)
public void or(BitSet set) 
public void xor(BitSet set)
  • and

源码如下：

public void and(BitSet set) {
    if (this == set)
        return;

    while (wordsInUse > set.wordsInUse)
        words[--wordsInUse] = 0;

    // Perform logical AND on words in common
    for (int i = 0; i < wordsInUse; i++)
        words[i] &= set.words[i];

    recalculateWordsInUse();
    checkInvariants();
}

该函数用于对当前对象进行位与操作，仅当当前位集和输入位集中同一下标的位值都为 true时，保留当前位值，否则，设为 false

  • andNot

源码如下：

public void andNot(BitSet set) {
    // Perform logical (a & !b) on words in common
    for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
        words[i] &= ~set.words[i];

    recalculateWordsInUse();
    checkInvariants();
}

如果输入位集的位值为 true，则设置当前位集中对应下标的位值为 false

  • or

源码如下：

public void or(BitSet set) {
    if (this == set)
        return;

    int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

    if (wordsInUse < set.wordsInUse) {
        ensureCapacity(set.wordsInUse);
        wordsInUse = set.wordsInUse;
    }

    // Perform logical OR on words in common
    for (int i = 0; i < wordsInCommon; i++)
        words[i] |= set.words[i];

    // Copy any remaining words
    if (wordsInCommon < set.wordsInUse)
        System.arraycopy(set.words, wordsInCommon,
                         words, wordsInCommon,
                         wordsInUse - wordsInCommon);

    // recalculateWordsInUse() is unnecessary
    checkInvariants();
}

对当前位值执行位与操作，只要当前位集和输入位集中有一个位值为 true，则设置当前位集该下标的位值为 true

  • xor

源码如下：

public void xor(BitSet set) {
    int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

    if (wordsInUse < set.wordsInUse) {
        ensureCapacity(set.wordsInUse);
        wordsInUse = set.wordsInUse;
    }

    // Perform logical XOR on words in common
    for (int i = 0; i < wordsInCommon; i++)
        words[i] ^= set.words[i];

    // Copy any remaining words
    if (wordsInCommon < set.wordsInUse)
        System.arraycopy(set.words, wordsInCommon,
                         words, wordsInCommon,
                         set.wordsInUse - wordsInCommon);

    recalculateWordsInUse();
    checkInvariants();
}

仅当当前位集和输入位集中同一下标的位值相反时，设置当前位集该下标的位值为 true，否则，设为 false

next

类 BitSet 提供了函数 next 来检索下标，共有两种方式：

public int nextSetBit(int fromIndex)
public int nextClearBit(int fromIndex)
  • nextSetBit(int fromIndex)

源码如下：

public int nextSetBit(int fromIndex) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

    checkInvariants();

    int u = wordIndex(fromIndex);
    if (u >= wordsInUse)
        return -1;

    long word = words[u] & (WORD_MASK << fromIndex);

    while (true) {
        if (word != 0)
            return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
        if (++u == wordsInUse)
            return -1;
        word = words[u];
    }
}

输入参数 fromIndex 表示位集中开始检索的起始下标，如果没有则抛出 -1

该函数功能是从 fromIndex 开始，检索第一个位值为 true 的下标

第一步：检查输入参数 fromIndex 是否符合条件，不符合则抛出 IndexOutOfBoundsException 异常；调用函数 checkInvariants 检查类参数是否符合条件

第二步：调用函数 wordIndex 转换位下标为数组下标，如果得到的数组下标 u 已经大于等于当前已使用的数组个数，那么直接抛出 -1

第三步：计算掩码，排除前 fromIndex 位的干扰，读取下标为 u 的数组数值进行位与运算，计算结果赋值给变量 word

第四步：如果 word 不等于 0，那么在该长整数上一定存在符合条件的位下标，(u * BITS_PER_WORD) 表示前 u 个整数表示的位长，函数 Long.numberOfTrailingZeros(word) 用于计算长整数中从最低位（从右到左）开始连续位值为 false 的长度；如果 word 等于 0，那么将下标 u 增加 1，首先判断是否超出数组已使用个数，如果超出，返回 -1，否则，将下标为 u 的值赋给 word，继续比较

  • nextClearBit(int fromIndex)

源码如下：

public int nextClearBit(int fromIndex) {
    // Neither spec nor implementation handle bitsets of maximal length.
    // See 4816253.
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

    checkInvariants();

    int u = wordIndex(fromIndex);
    if (u >= wordsInUse)
        return fromIndex;

    long word = ~words[u] & (WORD_MASK << fromIndex);

    while (true) {
        if (word != 0)
            return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
        if (++u == wordsInUse)
            return wordsInUse * BITS_PER_WORD;
        word = ~words[u];
    }
}

该函数功能与 nextSetBit 相反，目的在于找出从 fromIndex 开始的第一个位值为 false 的下标

函数实现上和 nextSetBit 相似，虽然是查找位值为 false 的下标，但是在实现时会执行位取反操作，这样，仍旧转换为查找位值为 true 的下标

关键代码如下：

long word = ~words[u] & (WORD_MASK << fromIndex);
...
word = ~words[u];

Long.numberOfTrailingZeros

源码如下：

public static int numberOfTrailingZeros(long i) {
    // HD, Figure 5-14
    int x, y;
    if (i == 0) return 64;
    int n = 63;
    y = (int)i; if (y != 0) { n = n -32; x = y; } else x = (int)(i>>>32);
    y = x <<16; if (y != 0) { n = n -16; x = y; }
    y = x << 8; if (y != 0) { n = n - 8; x = y; }
    y = x << 4; if (y != 0) { n = n - 4; x = y; }
    y = x << 2; if (y != 0) { n = n - 2; x = y; }
    return n - ((x << 1) >>> 31);
}

该函数功能是返回从最低位开始的连续位值为 false 的长度，如果输入参数为 0，那么返回 64

该函数的实现是不断进行位左移运算，每次左移大小为之前的一半（二分法）

实例测试

遍历整个 BitSet 对象，找出位值为 true 的下标

public static void main(String args[]) {
    BitSet bitSet = new BitSet();

    for (int i = 0; i < 10; i += 2) {
        bitSet.set(i);
    }

    for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
        if (i == Integer.MAX_VALUE)
            break;
        System.out.println(i);
    }
}

同理，找出位值为 false 的下标仅需将函数 nextSetBit 改为 nextClearBit 即可

标签：

相关文章