BitSet类

发表于 分类于 ， 本文字数： 8.5k

适合场景

整数，无重复；

BitSet基础

BitSet，也就是weitu，由于可以用非常紧凑的格式来表示给定范围的连续数据而经常出现在各种算法设计中。

img

####基本原理

用1位来表示一个数据是否出现过，0为没有出现过，1表示出现过。使用的时候既可根据某一个是否为0表示此数是否出现过（具有两种状态的数据）

1G的空间，有$1024102410248=8.5810^9$ 位，也就是可以表示85亿个不同数的状态。

常见的应用是那些需要进行统计的数据，将40亿个不同数据进行排序(采用技术排序的思想)等。

常见扩展

采用2位或者更多位来表示此数据的更多信息，比如出现了多少次等。

java中的BitSit的实现

构造函数

底层使用long数组作为内部存储结构，因此Bitset至少为一个long的大小，一个long 8 个字节，8*8 = 64位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

   /**
    * Creates a new bit set. All bits are initially {@code false}.
    */
   public BitSet() {
       initWords(BITS_PER_WORD);
       sizeIsSticky = false;
   }

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;
   }

不指定初始值大小，则默认为BITS_PRE_WORD, $2^6=64$位

1
2
3
4
5
6
7
8
9
10
11
/*
    * 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;

清空BitSet

通过循环方式来置0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
     * Sets all of the bits in this BitSet to {@code false}.
     *
     * @since 1.4
     */
    public void clear() {
        while (wordsInUse > 0)
            words[--wordsInUse] = 0;
    }

     //清空某一位
     public void clear(int bitIndex) {
         
     //清空指定范围
     public void clear(int fromIndex, int toIndex) {

反转位

1
2
3
public void flip(int bitIndex) {
    
public void flip(int fromIndex, int toIndex) {

设置位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
   /**
    * Sets the bit at the specified index to {@code true}.
    *
    * @param  bitIndex a bit index
    * @throws IndexOutOfBoundsException if the specified index is negative
    * @since  JDK1.0
    */
   public void set(int bitIndex) {
       
     /**
    * Sets the bit at the specified index to the specified value.
    *
    * @param  bitIndex a bit index
    * @param  value a boolean value to set
    * @throws IndexOutOfBoundsException if the specified index is negative
    * @since  1.4
    */
   public void set(int bitIndex, boolean value) {
       if (value)
           set(bitIndex);
       else
           clear(bitIndex);
   }  
 /**
    * Sets the bits from the specified {@code fromIndex} (inclusive) to the
    * specified {@code toIndex} (exclusive) to {@code true}.
    *
    * @param  fromIndex index of the first bit to be set
    * @param  toIndex index after the last bit to be set
    * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
    *         or {@code toIndex} is negative, or {@code fromIndex} is
    *         larger than {@code toIndex}
    * @since  1.4
    */
   public void set(int fromIndex, int toIndex) {
       
/**
    * Sets the bits from the specified {@code fromIndex} (inclusive) to the
    * specified {@code toIndex} (exclusive) to the specified value.
    *
    * @param  fromIndex index of the first bit to be set
    * @param  toIndex index after the last bit to be set
    * @param  value value to set the selected bits to
    * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
    *         or {@code toIndex} is negative, or {@code fromIndex} is
    *         larger than {@code toIndex}
    * @since  1.4
    */
   public void set(int fromIndex, int toIndex, boolean value) {

获取位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
    * Returns the value of the bit with the specified index. The value
    * is {@code true} if the bit with the index {@code bitIndex}
    * is currently set in this {@code BitSet}; otherwise, the result
    * is {@code false}.
    *
    * @param  bitIndex   the bit index
    * @return the value of the bit with the specified index
    * @throws IndexOutOfBoundsException if the specified index is negative
    */
   public boolean get(int bitIndex) {
       
 /**
    * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
    * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
    *
    * @param  fromIndex index of the first bit to include
    * @param  toIndex index after the last bit to include
    * @return a new {@code BitSet} from a range of this {@code BitSet}
    * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
    *         or {@code toIndex} is negative, or {@code fromIndex} is
    *         larger than {@code toIndex}
    * @since  1.4
    */
   public BitSet get(int fromIndex, int toIndex) {

获取当前bitset总bit的大小(最高位true的位置)

1
2
3
4
5
6
7
8
9
/**
    * Returns the "logical size" of this {@code BitSet}: the index of
    * the highest set bit in the {@code BitSet} plus one. Returns zero
    * if the {@code BitSet} contains no set bits.
    *
    * @return the logical size of this {@code BitSet}
    * @since  1.2
    */
   public int length() {

返回true的数目

1
2
3
4
5
6
7
/**
    * Returns the number of bits set to {@code true} in this {@code BitSet}.
    *
    * @return the number of bits set to {@code true} in this {@code BitSet}
    * @since  1.4
    */
   public int cardinality() {

####返回第一个false的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
    * Returns the index of the first bit that is set to {@code false}
    * that occurs on or after the specified starting index.
    *
    * @param  fromIndex the index to start checking from (inclusive)
    * @return the index of the next clear bit
    * @throws IndexOutOfBoundsException if the specified index is negative
    * @since  1.4
    */
   public int nextClearBit(int fromIndex) {
   
    /**
    * Returns the index of the nearest bit that is set to {@code false}
    * that occurs on or before the specified starting index.
    * If no such bit exists, or if {@code -1} is given as the
    * starting index, then {@code -1} is returned.
    *
    * @param  fromIndex the index to start checking from (inclusive)
    * @return the index of the previous clear bit, or {@code -1} if there
    *         is no such bit
    * @throws IndexOutOfBoundsException if the specified index is less
    *         than {@code -1}
    * @since  1.7
    */
   public int previousClearBit(int fromIndex) {

返回第一个true的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
     * Returns the index of the first bit that is set to {@code true}
     * that occurs on or after the specified starting index. If no such
     * bit exists then {@code -1} is returned.
     *
     * <p>To iterate over the {@code true} bits in a {@code BitSet},
     * use the following loop:
     *
     *  <pre> {@code
     * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
     *     // operate on index i here
     *     if (i == Integer.MAX_VALUE) {
     *         break; // or (i+1) would overflow
     *     }
     * }}</pre>
     *
     * @param  fromIndex the index to start checking from (inclusive)
     * @return the index of the next set bit, or {@code -1} if there
     *         is no such bit
     * @throws IndexOutOfBoundsException if the specified index is negative
     * @since  1.4
     */
    public int nextSetBit(int fromIndex) {
    
     /**
     * Returns the index of the nearest bit that is set to {@code true}
     * that occurs on or before the specified starting index.
     * If no such bit exists, or if {@code -1} is given as the
     * starting index, then {@code -1} is returned.
     *
     * <p>To iterate over the {@code true} bits in a {@code BitSet},
     * use the following loop:
     *
     *  <pre> {@code
     * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
     *     // operate on index i here
     * }}</pre>
     *
     * @param  fromIndex the index to start checking from (inclusive)
     * @return the index of the previous set bit, or {@code -1} if there
     *         is no such bit
     * @throws IndexOutOfBoundsException if the specified index is less
     *         than {@code -1}
     * @since  1.7
     */
    public int previousSetBit(int fromIndex) {

位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void and(BitSet set) {

public void or(BitSet set) {

public void xor(BitSet set) {

 /**
    * Clears all of the bits in this {@code BitSet} whose corresponding
    * bit is set in the specified {@code BitSet}.
    *
    * @param  set the {@code BitSet} with which to mask this
    *         {@code BitSet}
    * @since  1.2
    */
public void andNot(BitSet set) {

判空 (是否有true)

1
2
3
4
5
6
7
8
/**
    * Returns true if this {@code BitSet} contains no bits that are set
    * to {@code true}.
    *
    * @return boolean indicating whether this {@code BitSet} is empty
    * @since  1.4
    */
   public boolean isEmpty() {

交集

1
2
3
4
5
6
7
8
9
10
/**
    * Returns true if the specified {@code BitSet} has any bits set to
    * {@code true} that are also set to {@code true} in this {@code BitSet}.
    *
    * @param  set {@code BitSet} to intersect with
    * @return boolean indicating whether this {@code BitSet} intersects
    *         the specified {@code BitSet}
    * @since  1.4
    */
   public boolean intersects(BitSet set) {

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class BitSetDemo {
    public static void main(String[] args) {
        BitSet bitSet = new BitSet(64);
        bitSet.set(1,9,true);
//        bitSet.clear();
        bitSet.clear(1,2);
//        bitSet.set(60,true);
        System.out.println(bitSet.nextClearBit(0));
        System.out.println(bitSet.previousClearBit(10));
        System.out.println(bitSet.nextSetBit(0));
        System.out.println(bitSet.previousSetBit(10));
        System.out.println(bitSet.length());
        System.out.println(bitSet.size());
        System.out.println(bitSet.cardinality());
        System.out.println(bitSet.isEmpty());
    }
}

1688303879699

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏