Bitset，也就是位图，由于可以用非常紧凑的格式来表示给定范围的连续数据而经常出现在各种算法设计中。上面的图来自c++库中bitset的一张图。
基本原理是，用1位来表示一个数据是否出现过，0为没有出现过，1表示出现过。使用用的时候既可根据某一个是否为0表示此数是否出现过。
一个1G的空间，有 8*1024*1024*1024=8.58*10^9bit，也就是可以表示85亿个不同的数。
常见的应用是那些需要对海量数据进行一些统计工作的时候，比如日志分析等。
面试题中也常出现，比如：统计40亿个数据中没有出现的数据，将40亿个不同数据进行排序等。
又如：现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来(百度)。
programming pearls上也有一个关于使用bitset来查找电话号码的题目。
Bitmap的常见扩展，是用2位或者更多为来表示此数字的更多信息，比如出现了多少次等。
二. Java中bitset的实现Bitset这种结构虽然简单，实现的时候也有一些细节需要主要。其中的关键是一些位操作，比如如何将指定位进行反转、设置、查询指定位的状态（0或者1）等。
本文，分析一下java中bitset的实现，抛砖引玉，希望给那些需要自己设计位图结构的需要的程序员有所启发。
Bitmap的基本操作有：
初始化一个bitset，指定大小。
清空bitset。
反转某一指定位。
设置某一指定位。
获取某一位的状态。
当前bitset的bit总位数。
1. 声明在java中，bitset的实现，位于java.util这个包中，从jdk 1.0就引入了这个数据结构。在多个jdk的演变中，bitset也不断演变。本文参照的是jdk 7.0 源代码中的实现。
声明如下：
package java.util; import java.io.*; import java.nio.ByteBuffer; import java.nio.ByteOrder; import java.nio.LongBuffer; public class BitSet implements Cloneable, java.io.Serializable {、 private long[] words; .... ....
同时我们也看到使用long数组来作为内部存储结构。这个决定了，Bitset至少为一个long的大小。下面的构造函数中也会有所体现。
2. 初始化函数
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);
private void initWords(int nbits) {
words = new long[wordIndex(nbits-1) + 1];
}
private static int wordIndex(int bitIndex) {
return bitIndex >> ADDRESS_BITS_PER_WORD;
}
private final static int ADDRESS_BITS_PER_WORD = 6;
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
两个构造函数，分别是一个指定了初始大小，一个没指定。如果没指定，我们可以看到默认的初始大小为, 2^6 = 64-1=63 bit. 我们知道java中long的大小就是8个字节，也就是8*8=64bit。也就是说，bitset默认的是一个long整形的大小。初始化函数指定了必要的大小。
注意：如果指定了bitset的初始化大小，那么会把他规整到一个大于或者等于这个数字的64的整倍数。比如64位，bitset的大小是1个long，而65位时，bitset大小是2个long，即128位。做这么一个规定，主要是为了内存对齐，同时避免考虑到不要处理特殊情况，简化程序。
3. 清空bitset
a. 清空所有的bit位，即全部置0。通过循环方式来以此以此置0。 如果是C语言，使用memset会不会快点？
public void clear() { while (wordsInUse > 0) words[--wordsInUse] = 0; } b. 清空某一位
public void clear(int bitIndex) {
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
int wordIndex = wordIndex(bitIndex);
if (wordIndex >= wordsInUse)
return;
words[wordIndex] &= ~(1L << bitIndex);
recalculateWordsInUse();
checkInvariants();
}
第一行是参数检查，如果bitIndex小于0，则抛参数非法异常。后面执行的是bitset中操作中经典的两步曲：a. 找到对应的long b. 操作对应的位。
a. 找到对应的long。 这行语句是 int wordIndex = wordIndex(bitIndex);
b. 操作对应的位。常见的位操作是通过与特定的mask进行逻辑运算来实现的。因此，首先获取 mask（掩码）。
对于 clear某一位来说，它需要的掩码是指定位为0，其余位为1，然后与对应的long进行&运算。
~(1L << bitIndex); 即获取mask
words[wordIndex] &= ; 执行相应的运算。
注意：这里的参数检查，对负数index跑出异常，对超出大小的index，不做任何操作，直接返回。具体的原因，有待进一步思考。
c. 清空指定范围的那些bits