---

引言

ArrayList 提供了一个方法 removeIf ，

其源码实现中，巧用 BitSet，惊艳到我了。

于是乎，拜读 BitSet 源码，位运算用的真6，服！！！

---

一、BitSet是什么？

我们常说的位图，在JAVA 中的实现，是 BitSet ，

也可以说是一种算法吧，很突出点：省空间，

什么意思呢？举个简单的例子吧。

比如说有这么个场景：某基金的交易日记为1，休息日记为0，
那要记录一整年的数据，那就是 365 个数字，由1和0组成。
若数字是 int 类型，那 365 个数字，就是 1460 字节。
如果用 BitSet 来记录，理论上 48 个字节就可以了。

BitSet 使用 long 数组来记录数据，
long 8 个字节， 64 位，每位可对应一天的数据

比如第1天是交易日，在 long 的第 1 位，记录为 1，

第2天是休息日，在 long 的第 2 位，记录为 0，

以此类推，365 天， 6 个 long 就搞定。

BitSet 提供了一系列的方法，

封装位运算，方便使用。

这里写了个小 Demo，

图中 set (2) 就是 long 的 第 2 位 设置为 1

set (7) 就是 long 的 第 7 位 设置为 1，

bitSet.get(2) ，显示为 true （该位是 1，就会返回 true）
bitSet.get(5) ，显示为 false （该位是 0，就会返回 false）

先简单介绍下API，有个印象，之后再分析源码。

二、BitSet 常用方法

1、set(int bitIndex)
. 将对应下标位置的值设置为1

前面截图中的例子，说的不严谨，应该说下标位置。

调用 set (2)，set (7) 后，对应的 long ，二进制应该是：10000100

如果调用 set (66) 时，那会怎么样呢？

一个 long 是 64 位，不够用了，

那会在 long 数组的第二个元素中进行操作，

也就是第二个 long，下标为 2 的位置，设置为1，

即 第二个 long 的二进制是：100

2、get(int bitIndex)
. 判断对应下标处是否为1，是1 返回 true, 否则返回 false

比如截图中的例子， get(2) 返回 true。

调用 set (66) 时，会判断 第二个 long ，

其下标为2 的位置是否为1。

3、clear(int bitIndex))
. 将对应下标处的值清除

其实从方法的命名，也能猜到。说白了，就是把对应的下标处，设置为 0。

4、flip(int bitIndex))
. 将对应下标处的值反转

某下标处是1，调用该方法后变为0，
同样，本来是0，调用之后就变为1。

5、nextSetBit(int bitIndex))
. 从某下标处开始，第1个值为1的下标是多少

比如说，还是截图中的例子，调用 bitSet.nextSetBit(2)，就会返回2
从下标为2开始判断，哪个位置值为1，当然就是 2 了。

调用 bitSet.nextSetBit(4)，就会返回7，也很简单，
下标 4、5、6 的值都是 0，首次值为1，是下标7，所以返回 7。

如果不存在值为1的情况怎么办呢？
比如截图中的情况，调用 bitSet.nextSetBit(10)，
返回 -1。

6、nextClearBit(int bitIndex))
. 从某下标处开始，第1个值为0的下标是多少

这个与上面的那个类似，不多解释了。

7、previousSetBit(int bitIndex))
8、previousClearBit(int bitIndex))

不多解释
下面几个是求交集、并集、补集，差集的

09、and(BitSet set) ----- 两者交集
10、or(BitSet set) ------- 两者全集
09、xor(BitSet set) ------- 两者全集减去交集，剩下的
10、andNot(BitSet set) ------- 前面的bit，去掉交集剩余的

---

三、BitSet 源码解析

1、初始化

初始化（不指定大小）：BitSet bitSet = new BitSet();
初始化（指定了大小）：BitSet bitSet = new BitSet(30);

初始化的相关代码，粘贴出来了

public class BitSet implements Cloneable, java.io.Serializable {

    private final static int ADDRESS_BITS_PER_WORD = 6;
    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
	
    private long[] words; // long 数组
    
    private transient int wordsInUse = 0;
    
    public BitSet() {
        initWords(BITS_PER_WORD); // 初始化数组大小
        sizeIsSticky = false;
    }

    public BitSet(int nbits) {
        if (nbits < 0)
            throw new NegativeArraySizeException("nbits < 0: " + nbits);
        initWords(nbits);
        sizeIsSticky = true;
    }
    
    private void initWords(int nbits) {
        words = new long[wordIndex(nbits-1) + 1];
    }

    private static int wordIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_WORD;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

不指定大小时，初始化后 words 的长度为1。

指定了大小，初始化后 words 的长度，可以认为是 (n/64)+1。

比如初始化时，传入30，可以认为要记录 30 个数据。

一个 long 是 64 位，最大可以记录64个数据。

要记录30 个数据，一个 long 就可以了。

直观的可以看这个图，传入是 n 时，

若 n%64 == 0 , 那需要 long 的个数就是 n/64
若 n%64 != 0 , 那需要 long 的个数就是 (n/64)+1

这两种情况 与 ((n-1)/64)+1 等价。

代码中 bitIndex >> ADDRESS_BITS_PER_WORD 这个就是除以64的意思。

n/64 和 n >> 6 是等价的，

如果不是很清楚，问下度娘吧，要不留言也行。

总结一句：初始化时，确定 long 数组大小。

2、set(int bitIndex) 源码

前面说过，这个方法是，将某下标处的值，设置为1。

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

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

    words[wordIndex] |= (1L << bitIndex); // Restores invariants

    checkInvariants();
}
1
2
3
4
5
6
7
8
9
10
11

int wordIndex = wordIndex(bitIndex); 这个是算出，该坐标，是第几个 long.

这个方法，上面画图说过了，大概就是 除以64 的意思。

expandTo(wordIndex); 这个方法是自动扩容的，本篇不细说了。

比如说 set(int bitIndex) ，传入的是 3。

按位或操作的性质：

下标为3的那个位置，计算出的结果一定是 1，
其下标位置的值，一定不变。

再比如说 set(int bitIndex) ，传入的是 67

int wordIndex = wordIndex(bitIndex); 这里 wordIndex 就是 1

1L << 67 和 1L << 3 是 相等 的，其它的不用多解释了。

3、get(int bitIndex) 源码

前面说过，这个方法是，判断对应下标处，是不是1，
是1 返回 true, 否则返回 false

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

    checkInvariants();

    int wordIndex = wordIndex(bitIndex);
    return (wordIndex < wordsInUse)
        && ((words[wordIndex] & (1L << bitIndex)) != 0);
  }
}
1
2
3
4
5
6
7
8
9
10
11

wordIndex 是根据入参，算出该坐标，是第几个 long.

wordsInUse 这个前面没说，它表示 words 的实际长度，即总共有几个 long

wordIndex < wordsInUse 这个是判断是否下标越界，

如果越界直接返回 false。

这个不难理解，自己琢磨下，实在不懂留言里问吧！

(words[wordIndex] & (1L << bitIndex)) != 0，这句画图解释下

假如 箭头所指的位置是 bitIndex， 按位与操作的性质，
其它下标处，结果一定为0，

bitIndex 下标处的值，问号是1，结果就是1，问号是0，结果就是0。

通过巧妙的位运算，就判断出某下标处，是否为1。

4、clear(int bitIndex) 源码

前面说过，这个方法就是，将对应下标处的值清除

所谓清除，就是设置为0

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

   int wordIndex = wordIndex(bitIndex);
   if (wordIndex >= wordsInUse)
       return;

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

   recalculateWordsInUse();
   checkInvariants();
 }
 
  private void recalculateWordsInUse() {
    int i;
    for (i = wordsInUse-1; i >= 0; i--)
        if (words[i] != 0)
            break;

    wordsInUse = i+1; // The new logical size
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int wordIndex = wordIndex(bitIndex); 这个是算出，该坐标，是第几个 long

words[wordIndex] &= ~(1L << bitIndex); 这个也画个图解释。

假如 箭头所指的位置是 bitIndex， 按位与操作的性质

index 下标处的值，一定为0，其它位的值一定不变

recalculateWordsInUse 这个方法简单说下，

当把某坐标处的值，设置为0后，有可能整个long 的值变为0，

这时要重新计算 wordsInUse

5、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();
 }
1
2
3
4
5
6
7
8
9
10
11
12

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

按位异或操作，相同为0，不同为1。

结合图来看， 箭头处，值反转，其它下标处的值，保持原样。

至此为止，对某一下标处的操作，几个方法都讲完了，

这位运算封装的很好，你可以直接调用就好了。

下面看下范围操作！也很好玩儿。

5、set(int fromIndex, int toIndex) 源码

这个方法是将，某一范围的值，都设置为1（包头不包尾）

public void set(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) {
        words[startWordIndex] |= (firstWordMask & lastWordMask);
    } else {
        words[startWordIndex] |= firstWordMask;
        for (int i = startWordIndex+1; i < endWordIndex; i++)
            words[i] = WORD_MASK;
        words[endWordIndex] |= lastWordMask;
    }
    checkInvariants();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这分为两种情况，

• bitSet.set(5, 8) ， 范围落在同一个 long 上，
• bitSet.set(60, 80) ， 范围跨越不同的 long 。

先说第一种情况哈

firstWordMask & lastWordMask 运算的结果，就是下标为 5，6，7 为1，其它都为0，

最后， 按位或操作，使 words[0] 的 5，6，7 位都设置为1，其它都不变。

别问作者是怎么写出来的，反正我写不出来，

我相信，我不孤独，绝大多数的人，都写不出来！

另外一种情况是跨越不同的 long

处理首尾两个 long, 方法类似，不再画图了。

之间的 long，设置为 -1，即 64 位都是1，不需要位运算了。

6、and(BitSet set) 源码

这个方法前面说过，是求交集。

 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();
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这个比较好理解，

while 循环，是将多出来的 long 都设置为0。
多出来的，肯定不是交集。

对应下标的 long 取交集，即 按位与操作

最后重新计算 wordsInUse

其它 几个集合运算的方法，套路都差不多，略。

7、nextClearBit(int fromIndex)源码

这个方法前面说过，是从某下标处开始，第1个值为0的下标是多少

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

    checkInvariants();

    int u = wordIndex(fromIndex); // 算出是第几个 long 
    if (u >= wordsInUse)
        return fromIndex;  // 越界说明该下标处是0，直接返回

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

    while (true) {
        if (word != 0) // 目标下标，就在当前 long 中
            return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
        if (++u == wordsInUse)
            return wordsInUse * BITS_PER_WORD;
        word = ~words[u];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这个思路很巧妙，画图更容易懂，假设 fromIndex 是5

假设 words[0] 是上面这个样子，箭头处是下标5的位置，

那肉眼可见，从 5 开始，第一个0的位置，下标是8。

通过位运算，把下标 0~5 设置为0，其余的 0 和 1 翻转，

下标8的位置是1，之前的全部是 0 。

Long.numberOfTrailingZeros(word)

这个方法，就是返回低位有几个连续的0。
比如 二进制 11100，会返回 2，
比如 二进制 10101000，会返回 3，

u * BITS_PER_WORD 就是 u * 64 ，这个不多解释。

if (++u == wordsInUse) 这个意思是，最后一个 long，所有位上都是1。

这样的位运算，我实在是想不到，服气！

previousSetBit(int bitIndex)) previousClearBit(int bitIndex)) 套路差不多，略！

---

总结

1. BitSet 简单介绍，它是一种算法吧，用 位 来记录数据，省空间。封装 位运算。
2. BitSet 常用的API，差不多是增删除改查，还支持范围操作。
3. BitSet 的源码解析，主要分析了位运算的效果。

至于 BitSet 的应用，之后有时间再单独写一篇吧。OVER!!!