BitSet
前言
最近用到了位图索引的相关知识，第一次接触Java中进行位向量运算的工具类BitSet，简单学习记录一下。
一、简介
功能
BitSet类是一种用来保存位值的特殊数组，数组的大小可以改变。它和位向量的功能类似。
实现原理
源码中的介绍如下：
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.
简言之：
BitSet的数据封装到一个叫words的数组中，数组中的每一个word都是一个long类型的数据（我的理解是：位向量需要表示为人最容易理解的形式-整数，而表示整数的数据类型中，long的长度最长，为8字节64bit，64bit可以表示64种事物的状态）
words = new long[wordIndex(nbits-1) + 1];
二、方法
BitSet类的两种构造方法
-
无参构造
BitSet bs3 = new BitSet();默认长度为1；
-
有参构造
BitSet bs1 = new BitSet(4);
常用方法
-
length() 返回BitSet的逻辑长度
BitSet bs1 = new BitSet(4); System.out.println(bs3.length()); bs3.set(2); System.out.println(bs3.length());输出为：0和3
输出为0是因为：bs1的各个位均为false，即0000，所以逻辑长度为0
输出为3是因为：bs1变为0010，所以逻辑长度为3
-
get(i) 获得i位置的位符号（true or false）
for (int i = 0; i <4 ; i++) { if (i%2 == 0) bs1.set(i);//把i位置设为true } for (int i = 0; i <4 ; i++) { if(bs1.get(i)){ System.out.print("1"); } if(!bs1.get(i)) { System.out.print("0"); } }输出为：1010
注：i可以取大于0的任何整数值，但不能取小于0的值；即get（-1）会报错。
-
println（s1）： 输出bs1中为true的位所在的索引
输出为：{0, 2} -
and(bs2)
bs1.and(bs2); 输出为： ====qian== bs1:1010 bs2:0110 ====hou== bs1:0010 bs2:0110 -
andNot(bs1)：bs1中0和2所在的位为1，则将bs2中0和1所在的位设置为0；
bs2.andNot(bs1); 输出为： ====qian== bs1:1010 bs2:0110 ====and== bs1:1010 bs2:0100 -
or：或操作
-
xor：异或操作；不同取1，相同取0
-
int cardinality( )：返回BitSet 中设置为 true 的位数。
System.out.println(bs1.cardinality());输出为2； -
clear(int index);clear();clear(int startIndex, int endIndex)：将true变成false
-
BitSet get(int startIndex, int endIndex)：返回一个新的BitSet ，长度为endIndex-startIndex
bs2:0110BitSet bitSet = bs2.get(1, 3);输出：11 -
boolean intersects(BitSet bitSet)：判断两个BitSet 中true所在的位置是否相等；二者的长度不限制
-
int nextSetBit(int startIndex)：从startIndex开始，第一个出现true的位置
bs1:1010System.out.println(bs1.nextSetBit(1));System.out.println(bs1.nextSetBit(0));输出为：20 -
int size( )：Returns the number of bits of space actually in use by this {@code BitSet} to represent bit values.
BitSet bs2 = new BitSet(63);BitSet bs3 = new BitSet(65);System.out.println(bs2.size());System.out.println(bs3.size());输出为：64128即：BitSet的空间实际使用的单位为64bit
三、补充说明
-
情况1
BitSet bs1 = new BitSet(6);BitSet bs2 = new BitSet(63);System.out.println(bs1.length());for (int i = 0; i <63 ; i++) { if (i%2 == 0) bs1.set(i);//把i位置设为true}for (int i = 0; i <2 ; i++) { bs2.set(i);//把i位置设为true}bs2.xor(bs1);System.out.println(bs1.size());System.out.println(bs2.size());输出为：64 和 64（因为bs1和bs2赋值的时候，长度都没有超过64）
-
情况2
BitSet bs1 = new BitSet(6);BitSet bs2 = new BitSet(63);System.out.println(bs1.length());for (int i = 0; i <65 ; i++) { if (i%2 == 0) bs1.set(i);//把i位置设为true}for (int i = 0; i <2 ; i++) { bs2.set(i);//把i位置设为true}bs2.xor(bs1);System.out.println(bs1.size());System.out.println(bs2.size());输出为：128 和 128（因为bs1赋值的时候长度超过64，并且和bs1进行了位运算，所以长度都变成了128）
如果把bs2.xor(bs1);去掉，输出结果为128和64
四、总结
- BitSet底层是用long类型的数据进行存储的，且长度单位为64，比如需要表示001，则实际001 = 00100...0（64位）
- 当长度超过64位时，比如需要表示0010000..0（68位），会用两个long类型的数据表示该BitSet，即实际的001000..00（68位） = [001000..0(64位)，000000000(64位)]
- 当两个长度不同的BitSet进行运算时，比如001（3位）和0010000..0（68位）进行运算，最终它们的长度均为68位，实际占有空间的大小为128bit。