Java的BitSet原理及应用

原理

众所周知，Java的BitSet使用一个Long（一共64位）的数组中的没一位（bit）是否为1来表示当前Index的数存在不。但是BitSet又是如何实现的呢？其实只需要理解其中的两个方法：

就能够理解BitSet的实现原理是什么了。

set

先看源代码：

public void set(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    int wordIndex = wordIndex(bitIndex);
    expandTo(wordIndex);

    words[wordIndex] |= (1L << bitIndex); // Restores invariants

    checkInvariants();
}

除了判断给的值是否小于0的那两句，我们依次来看一下这个函数的每一句代码。

wordIndex

第一句就是计算wordIndex，通过wordIndex函数获取值。代码如下：

private static int wordIndex(int bitIndex) {
    return bitIndex >> ADDRESS_BITS_PER_WORD;
}

这里ADDRESS_BITS_PER_WORD的值是6，那么最先想到的问题就是：为什么是6呢？而不是其他值呢？

答案其实很简单，还记得在最开始提到的：BitSet里使用一个Long数组里的每一位来存放当前Index是否有数存在。

因为在Java里Long类型是64位，所以一个Long可以存储64个数，而要计算给定的参数bitIndex应该放在数组（在BitSet里存在word的实例变量里）的哪个long里，只需要计算：bitIndex / 64即可，这里正是使用>>来代替除法（因为位运算要比除法效率高）。而64正好是2的6次幂，所以ADDRESS_BITS_PER_WORD的值是6。

通过wordIndex函数就能计算出参数bitIndex应该存放在words数组里的哪一个long里。

expandTo

private void expandTo(int wordIndex) {
    int wordsRequired = wordIndex+1;
    if (wordsInUse < wordsRequired) {
        ensureCapacity(wordsRequired);
        wordsInUse = wordsRequired;
    }
}

从上面已经知道在BitSet里是通过一个Long数组（words）来存放数据的，这里的expandTo方法就是用来判断words数组的长度是否大于当前所计算出来的wordIndex（简单的说，就是能不能存的下），如果超过当前words数组的长度（记录在实例变量wordsInUse里），也即是存不下，则新加一个long数到words里(ensureCapacity(wordsRequired)所实现的。)。

Restores invariants

words[wordIndex] |= (1L << bitIndex); // Restores invariants

这一行代码可以说是BitSet的精髓了，先不说什么意思，我们先看看下面代码的输出：

System.out.println(1<<0);
System.out.println(1<<1);
System.out.println(1<<2);
System.out.println(1<<3);
System.out.println(1<<4);
System.out.println(1<<5);
System.out.println(1<<6);
System.out.println(1<<7);

输出是：

这个输出看出规律没有？就是2的次幂，但是还是不太好理解，我们用下面的输出，效果会更好：

System.out.println(Integer.toBinaryString(1<<0));
System.out.println(Integer.toBinaryString(1<<1));
System.out.println(Integer.toBinaryString(1<<2));
System.out.println(Integer.toBinaryString(1<<3));
System.out.println(Integer.toBinaryString(1<<4));
System.out.println(Integer.toBinaryString(1<<5));
System.out.println(Integer.toBinaryString(1<<6));
System.out.println(Integer.toBinaryString(1<<7));

输出是：

从而发现，上面所有的输出力，1 所在的位置，正好是第1，2，3，4，5，6，7，8（Java数组的Index从0开始）位。而BitSet正是通过这种方式，将所给的bitIndex所对应的位设置成1，表示这个数已经存在了。这也解释了(1L << bitIndex)的意思（注意：因为BitSet是使用的Long，所以要使用1L来进行位移）。

搞懂了(1L << bitIndex)，剩下的就是用|来将当前算出来的和以前的值进行合并了words[wordIndex] |= (1L << bitIndex);。

剩下的checkInvariants就没什么好解释的了。

get

搞懂了set方法，那么get方法也就好懂了，整体意思就是算出来所给定的bitIndex所对应的位数是否为1即可。先看看代码：

public boolean get(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    checkInvariants();

    int wordIndex = wordIndex(bitIndex);
    return (wordIndex < wordsInUse)
        && ((words[wordIndex] & (1L << bitIndex)) != 0);
}

计算wordIndex在上面set方法里已经说明了，就不再细述。这个方法里，最重要的就只有：words[wordIndex] & (1L << bitIndex)。这里(1L << bitIndex)也已经做过说明，就是算出一个数，只有bitIndex位上为1，其他都为0，然后再和words[wordIndex]做&计算，如果words[wordIndex]数的bitIndex位是0，则结果就是0，以此来判断参数bitIndex存在不。

运用

搞清楚了原理，就可以很好的运用了，不过这里不讲怎么使用Java的BitSet，网上有很多。我讲一个我在刷Leetcode时碰见的一个题，就可以使用BitSet的原理来实现。

题目如下：

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
For example, Given nums = [0, 1, 3] return 2.
Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

翻译过来就是：从0到n之间取出n个不同的数，找出漏掉的那个。注意：你的算法应当具有线性的时间复杂度。你能实现只占用常数额外空间复杂度的算法吗？

这正好可以使用BitSet的思想来实现。

public int missingNumberInByBitSet(int[] array) {
    int bitSet = 0;
    for (int element : array) {
        bitSet |= 1 << element;
    }

    for (int i = 0; i < array.length; i++) {
        if ((bitSet & 1 << i) == 0) {
            return i;
        }
    }

    return 0;
}

这里是简单实现，使用int，而不是lang，也没有用一个数组，但是核心思想是这样的。