参考：
查看类 ArrayList 中 removeIf 方法源码时，发现其使用 BitSet 类来存储待删除的元素下标
之前没有接触过这个类，了解之后发现其在数据查询和存储方面有很大用处
主要内容：
-
BitSet浅析 - 类变量和常量
- 构造器
set-
clear-（2） get-
flip- (3) valueOf- 位运算（
and, andNot, or, xor） next-
previous- (4) - 判空 / 判断交集
- 大小（
length, size, cardinality） -
toByteArray和toLongArray -
BitSet分析 -
Java素数查找 - 小结
BitSet 浅析
BitSet 浅析
类 BitSet，顾名思义，它表示一个位集，在每一位上仅有两个选项 - true 或者 false
在实际操作中，如果需要对一堆数据进行某个条件的判断，那么这一类问题都可以使用类 BitSet 来解决
类变量和常量
类 BitSet 包含的变量和常量如下所示
private long[] words;
在类 BitSet 内部，使用长整型（long）数组 words 来保存位集
/*
* BitSets are packed into arrays of "words." Currently a word is
* a long, which consists of 64 bits, requiring 6 address bits.
* The choice of word size is determined purely by performance concerns.
*/
private final static int ADDRESS_BITS_PER_WORD = 6;
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
/* Used to shift left or right for a partial word mask */
private static final long WORD_MASK = 0xffffffffffffffffL;
长整型整数占 64 位，进行左右移动时，使用 6 位二进制即可
private transient int wordsInUse = 0;
变量 wordsInUse 表示在数组 words 中已使用的整数个数
private transient boolean sizeIsSticky = false;
变量 sizeIsSticky 表示是否用户指定了数组 words 的大小（该变量在方法 clone() 和序列化方法中有用到）
private static final long serialVersionUID = 7997698588986878753L;
暂时还不清楚该常量的用处
构造器
类 BitSet 提供了 2 个公有构造器和 1 个私有构造器：
public BitSet()
public BitSet(int nbits)
private BitSet(long[] words)
下面介绍两个公有构造器的使用
BitSet()
源码如下：
public BitSet() {
initWords(BITS_PER_WORD);
sizeIsSticky = false;
}
首先调用函数 initWords，输入参数为常量 BITS_PER_WORD（大小为 64）
然后设置变量 sizeIsSticky 为 false，即用户没有设定数组 words 大小
BitSet(int nbits)
源码如下：
public BitSet(int nbits) {
// nbits can't be negative; size 0 is OK
if (nbits < 0)
throw new NegativeArraySizeException("nbits < 0: " + nbits);
initWords(nbits);
sizeIsSticky = true;
}
输入参数 nbits 表示初始化位集的大小
首先判断参数 nbits 是否符合条件，如果不符合，抛出 NegativeArraySizeException 异常
接下来调用函数 initWords，输入参数为 nbits
最后，设置 sizeIsSticky 为 true，表示用户指定了数组 words 大小
initWords
源码如下：
private void initWords(int nbits) {
words = new long[wordIndex(nbits-1) + 1];
}
该方法中，为 words 创建长度为 wordIndex(nbits-1)+1 的长整型数组
wordIndex
/**
* Given a bit index, return word index containing it.
*/
private static int wordIndex(int bitIndex) {
return bitIndex >> ADDRESS_BITS_PER_WORD;
}
方法 wordIndex 用于计算位集中下标为 bitIndex 的位在数组 words 中的下标
set
set
类 BitSet 提供了 4 个 set 函数：
public void set(int bitIndex)
public void set(int bitIndex, boolean value)
public void set(int fromIndex, int toIndex)
public void set(int fromIndex, int toIndex, boolean value)
set(int bitIndex)
源码如下：
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();
}
输入参数 bitIndex 表示位集下标
该函数功能是设定位集中下标为 bitIndex 的值为 true
首先判断下标 bitIndex 是否大于 0，如果不是，抛出 IndexOutOfBoundsException 异常
然后定义变量 wordIndex，调用函数 wordIndex(bitIndex) 计算数组 words 中相对应的下标
调用函数 expandTo，输入 wordIndex，确保 words[wordIndex] 不为 null
进行位与操作，设定位集中该下标的值为 true
调用函数 checkInvariants() 检查
set(int bitIndex, boolean value)
源码如下：
public void set(int bitIndex, boolean value) {
if (value)
set(bitIndex);
else
clear(bitIndex);
}
该函数可以用值 value 设定位集中下标为 bitIndex 的位
如果 value = true，调用方法 set(int bitIndex)
如果 value = false，调用方法 clear(bitIndex) 来清除该位值
set(int fromIndex, int toIndex)
源码如下：
public void set(int fromIndex, int toIndex) {
checkRange(fromIndex, toIndex);
if (fromIndex == toIndex)
return;
// Increase capacity if necessary
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 (restores invariants)
words[endWordIndex] |= lastWordMask;
}
checkInvariants();
}
该函数用于设置位集中范围在 [fromIndex, toIndex) 之间的值为 true
Note：具体设置的位集范围应该是 [fromIndex, toIndex-1]
第一步：调用函数 checkRange 判断输入参数 fromIndex 和 toIndex 是否符合标准
第二步：如果两个参数相等，则返回
第三步：调用函数 wordIndex，将位集下标转换为数组下标，得到变量 startWordIndex 和 endWordIndex；同时调用函数 expandTo，确保数组容量
第四步：计算掩码 firstWordMask 和 lastWordMask；如果设置范围在数组 words 的同一个数中，则利用掩码对该数进行位与操作；如果不在数组 words 的同一个数中，那么对多个数进行位与操作
最后调用函数 checkInvariants 检查类变量是否符合条件
set(int fromIndex, int toIndex, boolean value)
源码如下：
public void set(int fromIndex, int toIndex, boolean value) {
if (value)
set(fromIndex, toIndex);
else
clear(fromIndex, toIndex);
}
同样可以在批量设置中设定具体值
expandTo
源码如下：
private void expandTo(int wordIndex) {
int wordsRequired = wordIndex+1;
if (wordsInUse < wordsRequired) {
ensureCapacity(wordsRequired);
wordsInUse = wordsRequired;
}
}
在使用过程中，位集的大小可以按需要增长。为防止输入位集下标超出当前位集，可以调用 expandTo 来扩展数组 words 的大小
Note：输入参数 wordIndex 是数组下标
首先定义变量 wordsRequired 计算需要的最小的数组大小
如果当前数组中已使用的数量 wordsInUse 小于需要的大小，那么可以调用函数 ensureCapacity 确保数组 words 足够，同时设置 wordsInUse 的最新值为 `wordsRequired“
ensureCapacity
源码如下：
private void ensureCapacity(int wordsRequired) {
if (words.length < wordsRequired) {
// Allocate larger of doubled size or required size
int request = Math.max(2 * words.length, wordsRequired);
words = Arrays.copyOf(words, request);
sizeIsSticky = false;
}
}
输入参数 wordsRequired 表示当前所需的数组大小
此函数功能是确保数组 words 能够满足需求
如果当前数组 words 长度小于 wordsRequired，那么定义变量 request 计算新建数组大小（两倍当前数组长度或者请求的数组大小，取其中最大值），调用函数 Arrays.copyOf 扩展数组 words，同时设置类变量 sizeIsSticky 为 false
checkInvariants
源码如下：
private void checkInvariants() {
assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
assert(wordsInUse >= 0 && wordsInUse <= words.length);
assert(wordsInUse == words.length || words[wordsInUse] == 0);
}
公共方法改变类 BitSet 实例变量后，调用此函数保证类变量符合以下条件
checkRange
源码如下：
private static void checkRange(int fromIndex, int toIndex) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
if (toIndex < 0)
throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
if (fromIndex > toIndex)
throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
" > toIndex: " + toIndex);
}
检查输入参数 fromIndex 和 toIndex 是否符合条件，即 0 < fromIndex < toIndex，如果不符合，则抛出 IndexOutOfBoundsException 异常
实例测试
下面输入具体参数来验证函数 set(int fromIndex, int toIndex) 的计算过程（假设当前对象位集均为 false）
输入参数 fromIndex = 35, toIndex = 148，所以要设置位集范围 [35, 148) 的位值为 true
0 < fromIndex < toIndex，所以符合函数 checkRange 判断条件
变量 startWordIndex = 0, endWordIndex = 2
firstWordMask = WORD_MASK << fromIndex = 0xffffffffffffffffL << 0010 0011(取后 6 位) = WORD_MASK << 35 = 0xfffffff800000000L
lastWordMask = WORD_MASK >>> -toIndex = 0xffffffffffffffffL >>> 1110 1100(取后 6 位) = WORD_MASK >>> 44 = 0x00000000000fffffL
因为 startWordIndex != endWordIndex，所以先计算数组 words 下标 0 的位与操作
words[startWordIndex] |= firstWordMask -> 0x0000000000000000L |= 0xfffffff800000000L = 0xfffffff800000000L
再计算数组下标 1 的位与操作
words[1] |= WORD_MASK -> 0x0000000000000000L |= 0xffffffffffffffffL = 0xffffffffffffffffL
最后计算数组下标 2 的位与操作
words[2] |= lastWordMask -> 0x0000000000000000L |= 0x00000000000fffffL = 0x00000000000fffffL
测试代码如下：
public static void main(String args[]) {
BitSet bitSet = new BitSet();
bitSet.set(35, 148);
System.out.println(bitSet.cardinality());
long[] res = bitSet.toLongArray();
for (Long l : res) {
System.out.println(Long.toBinaryString(l));
}
}
取值范围长度为 toIndex - fromIndex = 148 - 35 = 113