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类的两种构造方法

1. 无参构造

   BitSet bs3 = new BitSet();
   

   默认长度为1；

2. 有参构造

   BitSet bs1 = new BitSet(4);
   

常用方法

1. 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

2. 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）会报错。

3. println（s1）： 输出bs1中为true的位所在的索引

   输出为：{0, 2}
   

4. and(bs2)

   bs1.and(bs2);
   输出为：
   ====qian==   
   bs1:1010
   bs2:0110
   ====hou==
   bs1:0010
   bs2:0110
   

5. andNot(bs1)：bs1中0和2所在的位为1，则将bs2中0和1所在的位设置为0；

   bs2.andNot(bs1);
   输出为：
   ====qian==  
   bs1:1010
   bs2:0110
   ====and==
   bs1:1010
   bs2:0100
   

6. or：或操作

7. xor：异或操作；不同取1，相同取0

8. int cardinality( )：返回BitSet 中设置为 true 的位数。

   System.out.println(bs1.cardinality());输出为2；
   

9. clear(int index);clear();clear(int startIndex, int endIndex)：将true变成false

10. BitSet get(int startIndex, int endIndex)：返回一个新的BitSet ，长度为endIndex-startIndex

    bs2:0110BitSet bitSet = bs2.get(1, 3);输出：11
    

11. boolean intersects(BitSet bitSet)：判断两个BitSet 中true所在的位置是否相等；二者的长度不限制

12. int nextSetBit(int startIndex)：从startIndex开始，第一个出现true的位置

    bs1:1010System.out.println(bs1.nextSetBit(1));System.out.println(bs1.nextSetBit(0));输出为：20
    

13. 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。

Java位运算工具类-BitSet详细介绍

原文：https://www.cnblogs.com/rookie--/p/14750653.html