参考：
查看类 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素数查找 - 小结
previous
previous
类 BitSet 提供了函数 previous，用于查找在指定下标之前的最近的位值为 true 或者 false 的下标
public int previousSetBit(int fromIndex)
public int previousClearBit(int fromIndex)
previousSetBit(int fromIndex)
源码如下：
public int previousSetBit(int fromIndex) {
if (fromIndex < 0) {
if (fromIndex == -1)
return -1;
throw new IndexOutOfBoundsException(
"fromIndex < -1: " + fromIndex);
}
checkInvariants();
int u = wordIndex(fromIndex);
if (u >= wordsInUse)
return length() - 1;
long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
while (true) {
if (word != 0)
return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
if (u-- == 0)
return -1;
word = words[u];
}
}
输入参数 fromIndex 为位集下标
该函数功能是找出位集中在 fromIndex 之前最近的位值为 true 的下标，如果不存在，则返回 true
第一步：参数检查
第二步：得到数组对应下标 u，如果 u 不小于数组已使用下标，表示在它之前离它最近的下标为 位集大小 - 1，即 length()-1
第三步：利用无符号右移运算符，计算掩码，设置 fromIndex 之后位值为 false，与数组下标 u 的数值进行位与操作，得到变量 word
第四步：如果 word 不等于 0，那么表示该整数中存在符合条件的位，否则，判断下标 u 是否已等于 0，如果是，返回 -1，否则，u-1 后继续赋值给 word
previousClearBit(int fromIndex)
该函数功能和 previousBitSet 相反，检索在 fromIndex 之前的最近的位值为 false 的下标
函数实现和 previousBitSet 类似，仅是修改了关键实现：
long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));
...
return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
...
word = ~words[u];
Long.numberOfLeadingZeros
返回从最高位开始位值连续为 0 的长度
实例测试
从后向前遍历输出位值为 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.length(); i >= 0; i = bitSet.previousSetBit(i - 1)) {
System.out.println(i);
}
}
判空 / 判断交集
类 BitSet 使用函数 isEmpty 判断位集是否为空：
public boolean isEmpty() {
return wordsInUse == 0;
}
其实现是判断已使用整数个数是否为 0
使用函数 intersects 来判断是否和其它 BitSet 对象有交集
源码如下：
public boolean intersects(BitSet set) {
for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
if ((words[i] & set.words[i]) != 0)
return true;
return false;
}
只要当前位集和输入位集在某个位上均为 true，那么判断两者有交集
大小（
length, size, cardinality）
length, size, cardinality）
类 BitSet 提供了 3 种方式来获取大小
public int length()
public int size()
public int cardinality()
length()
源码如下：
public int length() {
if (wordsInUse == 0)
return 0;
return BITS_PER_WORD * (wordsInUse - 1) +
(BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
}
该函数返回的是当前已使用的位集长度
size()
源码如下：
public int size() {
return words.length * BITS_PER_WORD;
}
该函数返回的是类 BieSet 内部已申请内存的位长度
cardinality()
源码如下：
public int cardinality() {
int sum = 0;
for (int i = 0; i < wordsInUse; i++)
sum += Long.bitCount(words[i]);
return sum;
}
该函数得到的是位集中位值为 true 的个数
toByteArray 和
toLongArray
toByteArray 和
toLongArray
类 BitSet 提供了 2 种方式来将内部位集转换为数组输出
public long[] toLongArray()
public byte[] toByteArray()
toLongArray()
源码如下：
public long[] toLongArray() {
return Arrays.copyOf(words, wordsInUse);
}
因为类 BeiSet 内部使用 long 型数组保存位集，所以返回已使用数组即可
-
toByteArray()public byte[] toByteArray() {
int n = wordsInUse;
if (n == 0)
return new byte[0];
int len = 8 * (n-1);
for (long x = words[n - 1]; x != 0; x >>>= 8)
len++;
byte[] bytes = new byte[len];
ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
for (int i = 0; i < n - 1; i++)
bb.putLong(words[i]);
for (long x = words[n - 1]; x != 0; x >>>= 8)
bb.put((byte) (x & 0xff));
return bytes;
}
转换为 Byte 数组麻烦一点，因为长整形变量占 64 位，字节变量占 8 位，所以一个长整型变量可以转换为 8 个字节变量
BitSet 分析
BitSet 分析
理清类 BitSet 源码后，可以发现，它适用于处理二值问题，保存一堆数据是否满足某一条件的结果（true 或者 false）
优点如下
- 按位存储，内存占用空间小
- 已封装好足够多的操作
缺点如下
- 线程不安全
- 类
BitSet内部是动态增加long型数组，但是并没有动态减少，可能会引发OutOfMemory
以下是相关的博文：
为什么Java中的BitSet使用long数组做内部存储，而不使用int数组或者byte数组？
Java 素数查找
Java 素数查找
参考：
- 素数
素数（prime number），又称为质数，定义为在大于 1 的自然数中，除了 1 和它本身外不再有其它因数
基本判断思路：
对正整数 n，如果用 2 到根号 n 之间的所有整数去除，均无法整除，则 n 为质数
- 筛选法求素数（使用
BitSet）
第一步：设置位集下标 2-n 均为 true
第二步：从前到后进行遍历，找出位值为 true 的下标，每找到一个，将其与后面下标值进行除法操作，如果能够整除，则设置该下标为 false
操作 1：遍历到 根号 n 即可
操作 2：得到当前下标后，将其用 1，2，3，4... 顺序相乘得到目标下标值
实例测试
找出前 2000万 个整数中包含的素数个数
方法一：
public static int findPrimeNumber_v1(int range) {
int count = 0;
boolean flag = false;
for (int i = 2; i < range; i++) {
if (i == 2) {
count++;
continue;
}
flag = true;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
count++;
}
}
return count;
}
方法二：
public static int findPrimeNumber_v2(int range) {
BitSet bitSet = new BitSet(range + 1);
for (int i = 2; i < range; i++) {
bitSet.set(i);
}
int s = (int) Math.sqrt(range);
int r = 0;
for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
for (int j = 2; j < range; j++) {
r = i * j;
if (r > range)
break;
bitSet.clear(r);
}
}
return bitSet.cardinality();
}
测试：
public static void main(String args[]) {
int range = 20000000;
long time1 = System.currentTimeMillis();
System.out.println(findPrimeNumber_v1(range));
long time2 = System.currentTimeMillis();
System.out.println(time2 - time1);
time1 = System.currentTimeMillis();
System.out.println(findPrimeNumber_v2(range));
time2 = System.currentTimeMillis();
System.out.println(time2 - time1);
}
由结果可知，使用 BitSet 配合筛选法，查找速度大大增加
小结
这是第一次完整的分析一个类的源码，还没有找到方法更好的理清函数之间的的关系，所以就直接按照函数源码进行了分析（其实有些函数的源码其实并不需要讲解，看一看就明白了）
以后应该不会像这样子直接分析源码了，应该在弄懂一个类 / 框架的原理的前提下，再进行归纳总结