1:Bitset介绍
BitSet 是用于存储二进制位和对二进制进行操作的 自动去重Java 数据结构,
此类实现了一个按需增长的位向量。位 set 的每个组件都有一个 boolean 值。用非负的整数将 BitSet 的位编入索引。可以对每个编入索引的位进行测试、设置或者清除。通过逻辑与、逻辑或和逻辑异或操作，可以使用一个 BitSet 修改另一个 BitSet 的内容。
默认情况下，set 中所有位的初始值都是 false。
2:优化空间
在程序runtime时,我们经常需要使用数组来记住程序的运行状态,并且根据这些状态及时 对数据做出更新,一般有以下处理办法
- 使用 ***Int [] state=new int[22]; ***保存状态
- 使用 boolean [] state = new boolean[22] 保存状态
分析可知,1byte=8bit int占用4个字节,如果考虑使用bit直接存储状态 ,将会大大节约时间, 不过在改变你的编程习惯之前,你应该清楚 我们如何保存状态,以及对于状态的操作
3:Bitset常用api
构建
BitSet()
创建一个新的位 set。 默认64
BitSet(int nbits)
创建一个位 set，它的初始大小足以显式表示索引范围在 0 到 nbits-1 的位。 一般要求给出大小 当给出的值小于实际需要的值,会自动扩容</pre>
操作
更新:
void set(int bitIndex)
将指定索引处的位设置为 true。
void set(int bitIndex, boolean value)
将指定索引处的位设置为指定的值。
void set(int fromIndex, int toIndex)
将指定的 fromIndex（包括）到指定的 toIndex（不包括）范围内的位设置为 true。 void set(int fromIndex, int toIndex, boolean value)
将指定的 fromIndex（包括）到指定的 toIndex（不包括）范围内的位设置为指定的值。
获取:
| boolean | **get**(int bitIndex)
返回指定索引处的位值。 |
| BitSet | **get**(int fromIndex, int toIndex)
返回一个新的 BitSet，它由此 <tt>BitSet</tt> 中从fromIndex（包括）到 toIndex（不包括）范围内的位组成。 |
翻转:
| boolean | **get**(int bitIndex)
返回指定索引处的位值。 |
| BitSet | **get**(int fromIndex, int toIndex)
返回一个新的 <tt>BitSet</tt>，它由此 <tt>BitSet</tt> 中从 <tt>fromIndex</tt>（包括）到 <tt>toIndex</tt>（不包括）范围内的位组成。 |
删除
| void | **clear**()
将此 BitSet 中的所有位设置为 false。 |
| void | **clear**(int bitIndex)
将索引指定处的位设置为 false。 |
| void | **clear**(int fromIndex, int toIndex)
将指定的 <tt>fromIndex</tt>（包括）到指定的 <tt>toIndex</tt>（不包括）范围内的位设置为 false。 |
长度:
| int | **cardinality**()
返回此 BitSet 中设置为 <tt>true</tt> 的位数。 |
| int | **length**()
返回此 BitSet 的“逻辑大小”：BitSet 中最高设置位的索引加 1。 |
| int | **size**()
返回此 BitSet 表示位值时实际使用空间的位数。 |
重要: 遍历相关:
| int | **nextClearBit**(int fromIndex)
返回第一个设置为 false 的位的索引，这发生在指定的起始索引或之后的索引上。 |
| int | **nextSetBit**(int fromIndex)
返回第一个设置为 true 的位的索引，这发生在指定的起始索引或之后的索引上。 |
4.BitSet 应用举例
统计随机个数
private final static int LEN_NUM = 10; public static void main(String[] args) {
BitSet set = new BitSet();
ArrayList<Integer> list = new ArrayList<>();
Random random = new Random(); for (int i = 0; i < LEN_NUM; i++) {
list.add(random.nextInt(100));
} for (int i = 0; i < list.size(); i++) {
set.set(list.get(i));
} for (int i = 0; i < 10; i++) { if(!set.get(i)) { //输出不在10范围以内的个数
System.out.print(i+" ");
}
}
System.out.println();
System.out.println("有true的多少个"+set.cardinality());
}
输出素数:
// 原始
public static void main(String[] s) {
int n = 1000000;
long start = System.currentTimeMillis();
int[] hash = new int[n + 1];
for (int i = 2; i < n; i++) {
if (hash[i] == 0) {
for (int j = 2 * i; j < n; j += i) {
hash[j] = 1;
}
}
}
long end = System.currentTimeMillis();
System.out.println((end - start) + " ms");
}
} // 改进后的
public static void main(String[] args) { long start = System.currentTimeMillis();
BitSet bitSet = new BitSet(10000000); for (int i = 2; i < 1000000; i++) { if(!bitSet.get(i)) { for (int j = i*2; j <1000000 ; j+=i) {
bitSet.set(j,true);
}
}
} for (int i = 0; i < 1000000; i++) { if(!bitSet.get(i)) {
System.out.println(i+" ");
}
} long end = System.currentTimeMillis();
System.out.println((end - start) + " ms");
}
对不同数据进行排序
场景是无序数组: 因为bitset 自动去重
private static Random random=new Random(); private static Set<Integer> set=new HashSet<>(); // public static void init() { for (int i = 0; i < 1000; i++) {
set.add(random.nextInt(1000));
}
} public static void main(String[] args) {
init();
BitSet bitSet = new BitSet();
Integer [] x=new Integer[set.size()];
Integer[] array = set.toArray(x); for (int i = 0; i < array.length; i++) {
bitSet.set(array[i]);
} int bitLen=bitSet.cardinality(); int[] orderedArray = new int[bitLen]; int k=0; for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
orderedArray[k++] = i;
} for (int i = 0; i < bitLen; i++) {
System.out.println(orderedArray[i]);
}
}</pre>
并交补运算
public static void main(String[] args) {
BitSet bitSet = new BitSet(100);
bitSet.set(1);
bitSet.set(2);
bitSet.set(3);
BitSet bitSet2 = new BitSet(100);
bitSet2.set(2);
bitSet2.set(3);
bitSet2.set(5);
System.out.println("刚开始的bitSet："+bitSet);
System.out.println("刚开始的bitSet2："+bitSet2);
System.out.println("------------------------------"); //求并集
bitSet.or(bitSet2);
System.out.println("求完并集之后的bitSet："+bitSet);
System.out.println("求完并集之后的bitSet2："+bitSet2);
System.out.println("------------------------------"); //使bitSet回到刚开始的状态
bitSet.clear(5); //求交集
bitSet.and(bitSet2);
System.out.println("求完交集之后的bitSet："+bitSet);
System.out.println("求完交集之后的bitSet2："+bitSet2);
System.out.println("------------------------------"); //使bitSet回到刚开始的状态
bitSet.set(1); //此方法返回在bitSet中不在bitSet2中的值，求的是bitSet相对于bitSet2的补集
bitSet.andNot(bitSet2);
System.out.println("求完补集之后的bitSet："+bitSet);
System.out.println("求完补集之后的bitSet2："+bitSet2);
}
