Java位向量的实现原理与巧妙应用
1、博文介绍
本篇博文将会介绍几本的位运算含义、位向量介绍、BitSet实现原理、Java位向量的应用、拓展介绍Bloom Filter等。
2、位运算介绍
1) 位运算符
java中位运算操作符主要包括：
&: 与
|: 或
^: 异或
~: 非
前三种可以和 = 结合使用，比如 &=、|=、^=；但是~是单目运算符，不能和=结合使用。
<<: 左移运算，相当于乘法，低位补0；
>>: 右移运算，相当于除法，有符号移位若高位为正，则高位补0，若为负，则高位补1；
java中增加了一种"无符号"右移，>>>,它使用零扩展，无论正负都在高位插入0；
移位操作与等号也可以组合使用： >>=、<<=
2）位运算简单应用
// 1. 获得int型最大值；2147483647的十六进制为0x7FFFFFFF,其中最高位为符号位
System.out.println((1 << 31) - 1);// 2147483647， 由于优先级关系，括号不可省略
System.out.println(~(1 << 31));// 2147483647 // 2. 获得int型最小值
System.out.println(1 << 31);
System.out.println(1 << -1); // 3. 判断一个数n是不是2的幂
System.out.println((n & (n - 1)) == 0);
/*如果是2的幂，n一定是100... n-1就是1111....
所以做与运算结果为0*/ // 4. 计算2的n次方 n > 0
System.out.println(2<<(n-1)); // 5. 从低位到高位,将n的第m位置为0
System.out.println(n & ~(0<<(m-1)));
/* 将1左移m-1位找到第m位，取反后变成111...0...1111
n再和这个数做与运算*/ // 6. 从低位到高位,取n的第m位
int m = 2;
System.out.println((n >> (m-1)) & 1); // 7. 从低位到高位.将n的第m位置为1
System.out.println(n | (1<<(m-1)));
/*将1左移m-1位找到第m位，得到000...1...000
n在和这个数做或运算*/ // 8. 获得long类型的最大值
System.out.println(((long)1 << 127) - 1); // 9. 乘以2运算
System.out.println(10<<1); // 10. 求两个整数的平均值
System.out.println((a+b) >> 1); // 11. 除以2运算(负奇数的运算不可用)
System.out.println(10>>1); // 12. 判断一个数的奇偶性，利用的是最后一位
System.out.println((10 & 1) == 1);
System.out.println((9 & 1) == 1); // 13. 不用临时变量交换两个数（面试常考）
a ^= b;
b ^= a;
a ^= b; // 14. 取绝对值（某些机器上，效率比n>0 ? n:-n 高）
int n = -1;
System.out.println((n ^ (n >> 31)) - (n >> 31));
/* n>>31 取得n的符号，若n为正数，n>>31等于0，若n为负数，n>>31等于-1
若n为正数 n^0-0数不变，若n为负数n^-1 需要计算n和-1的补码，异或后再取补码，
结果n变号并且绝对值减1，再减去-1就是绝对值 */ // 15. 取两个数的最大值（某些机器上，效率比a>b ? a:b高）
System.out.println(b&((a-b)>>31) | a&(~(a-b)>>31)); // 16. 取两个数的最小值（某些机器上，效率比a>b ? b:a高）
System.out.println(a&((a-b)>>31) | b&(~(a-b)>>31)); // 17. 判断符号是否相同(true 表示 x和y有相同的符号， false表示x，y有相反的符号。)
System.out.println((a ^ b) > 0);
3）应用 - 小游戏中状态的判断，如斗地主判断四人是否处于准备状态
充分利用一个位有两种状态，可以代表开闭、是否准备好等二状态场景中，即便是多状态也可以用多位来实现，比如在迷宫问题中，可以用00 01 10 11 来代表四个方向。如果正常的判断四人是否处于准备状态，可定义四个变量，但是如果用位运算，则一个byte类型变量的低4位就足够了。
在提高运行速度的同时，也对程序的可读性造成了影响，上面只是举例位运算可以应用在类似的场景中，具体适不适合根据项目背景而定。可以使用设计模式来解决，底层用位实现，封装到上层之后只公开方法。
实现代码：
/**
* Java 位运算的常用方法封装<br>
*/
public class BitUtils { /**
* 获取运算数指定位置的值<br>
* 例如： 0000 1011 获取其第 0 位的值为 1, 第 2 位 的值为 0<br>
*
* @param source
* 需要运算的数
* @param pos
* 指定位置 (0<=pos<=7)
* @return 指定位置的值(0 or 1)
*/
public static byte getBitValue(byte source, int pos) {
return (byte) ((source >> pos) & 1);
} /**
* 将运算数指定位置的值置为指定值<br>
* 例: 0000 1011 需要更新为 0000 1111, 即第 2 位的值需要置为 1<br>
*
* @param source
* 需要运算的数
* @param pos
* 指定位置 (0<=pos<=7)
* @param value
* 只能取值为 0, 或 1, 所有大于0的值作为1处理, 所有小于0的值作为0处理
*
* @return 运算后的结果数
*/
public static byte setBitValue(byte source, int pos, byte value) { byte mask = (byte) (1 << pos);
if (value > 0) {
source |= mask;
} else {
source &= (~mask);
} return source;
} /**
* 将运算数指定位置取反值<br>
* 例： 0000 1011 指定第 3 位取反, 结果为 0000 0011; 指定第2位取反, 结果为 0000 1111<br>
*
* @param source
*
* @param pos
* 指定位置 (0<=pos<=7)
*
* @return 运算后的结果数
*/
public static byte reverseBitValue(byte source, int pos) {
byte mask = (byte) (1 << pos);
return (byte) (source ^ mask);
} /**
* 检查运算数的指定位置是否为1<br>
*
* @param source
* 需要运算的数
* @param pos
* 指定位置 (0<=pos<=7)
* @return true 表示指定位置值为1, false 表示指定位置值为 0
*/
public static boolean checkBitValue(byte source, int pos) { source = (byte) (source >>> pos); return (source & 1) == 1;
} /**
* 入口函数做测试<br>
*
* @param args
*/
public static void main(String[] args) { // 取十进制 11 (二级制 0000 1011) 为例子
byte source = 11; // 取第2位值并输出, 结果应为 0000 1011
for (byte i = 7; i >= 0; i--) {
System.out.printf("%d ", getBitValue(source, i));
} // 将第6位置为1并输出 , 结果为 75 (0100 1011)
System.out.println("\n" + setBitValue(source, 6, (byte) 1)); // 将第6位取反并输出, 结果应为75(0100 1011)
System.out.println(reverseBitValue(source, 6)); // 检查第6位是否为1，结果应为false
System.out.println(checkBitValue(source, 6)); // 输出为1的位, 结果应为 0 1 3
for (byte i = 0; i < 8; i++) {
if (checkBitValue(source, i)) {
System.out.printf("%d ", i);
}
} }
}
3、Java位向量介绍-BitSet
位向量，也叫位图，是一个我们经常可以用到的数据结构，在使用小空间来处理大量数据方面有着得天独厚的优势；位向量的定义就是一串由0.1组成的序列。
Java中对位向量的实现类时Java.util.BitSet;C++标准库中也有相应的实现，原理都是一样的；BitSet源码也很简单，很容易看懂，如果读者在对位向量有一定的了解后，可以通过读源码来了解BitSet的具体实现。
一个bit上有两个值，正好可以用来判断某些是非状态的场景，在针对大数据场景下判断存在性，BitSet是相比其他数据结构比如HashMap更好的选择，在Java中，位向量是用一个叫words的long型数组实现的，一个long型变量有64位，可以保存64个数字；比如我们有[2,8,6,10,15]这5个数要保存，一般存储需要 5*4 = 20字节的存储空间。但是如果我们使用Java.util.BitSet进行存储则可以节省很多的空间只需要一个long型数字就够了。BitSet只面向数字只面向数字使用，对于string类型的数据，可以通过hashcode值来使用BitSet。
由于，1 << 64, 1<<128, 1<<192 这些数字的结果都为1，BitSet内部，long[]数组的大小由BitSet接收的最大数字决定，这个数组将数字分段表示[0,63],[64,127],[128,191]...。即long[0]用来存储[0,63]这个范围的数字的“存在性”，long[1]用来存储[64,127]，依次轮推，这样就避免了位运算导致的冲突。原理如下：
|------------|----------|----------|----------|----------|
|
| 数字范围 [0,63] [64,127] [128,191] ... |
|------------|----------|----------|----------|----------|
|
| long数组索引 0 1 2 ... |
|------------|----------|----------|----------|----------|
Java的BitSet每次申请空间，申请64位，即一个long型变量所占的位数；
BitSet源码实现-缩小版：
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 { /**
在Java里面BitSets被打包成一个叫“words”的long型数组，不过words是private的对外不公开，
只公开了操作他们的方法；
*/
private final static int ADDRESS_BITS_PER_WORD = 6; //2^6=64，程序中出现的 >>6
private final static int BITS_PER_WORD = 64;
private final static int BIT_INDEX_MASK = 63;
private static final long WORD_MASK = 0xffffffffffffffffL;
private long[] words;
private transient int wordsInUse = 0; //开了几个long型数组 public BitSet() {
initWords(64);
}
public BitSet(int nbits) {
if (nbits < 0)
throw new NegativeArraySizeException("nbits < 0: " + nbits);
initWords(nbits);
}
private void initWords(int nbits) {
//初始化多少个long型数组才能存下？除以64(>>6) 然后+1；
words = new long[((nbits-1) >> 6) + 1];
} public void set(int bitIndex) { int wordIndex = (bitIndex >> 6); //除以64定位到某个long型变量；
words[wordIndex] |= (1L << bitIndex); // Restores invariants
} public boolean get(int bitIndex) { int wordIndex = (bitIndex >> 6);
return (words[wordIndex] & (1L << bitIndex)) != 0;
} public void clear(int bitIndex) {
words[wordIndex] &= ~(1L << bitIndex);
} public void clear() {
while (wordsInUse > 0)
words[--wordsInUse] = 0;
} public boolean isEmpty() {
return wordsInUse == 0;
} public int cardinality() {
int sum = 0;
for (int i = 0; i < wordsInUse; i++)
sum += Long.bitCount(words[i]);
return sum;
} public void and(BitSet set) {
if (this == set)
return; while (wordsInUse > set.wordsInUse)
words[--wordsInUse] = 0; // Perform logical AND on words in common
for (int i = 0; i < wordsInUse; i++)
words[i] &= set.words[i]; recalculateWordsInUse();
checkInvariants();
} }
4、BitSet的应用
1）《编程珠玑》中的排序问题
问题重述：一个最多包含n个正整数的文件，每个数都小于n，其中n=107，并且没有重复。最多有1MB内存可用。要求用最快方式将它们排序并按升序输出。
解决方案就是：把文件一次读入，出现的数字在位向量对应索引处中标注为1，读取完文件之后，将位向量从低位向高位依次将为1的索引输出即可。
相关代码：
package cn.liuning.test;
import java.util.BitSet;
public class MainTest { /** 使用BitSet进行排序 */
public static void main(String[] args) { int[] data={1,2,5,9,11,21,12,15};
int max = 0;
for(int i=0;i<data.length;i++){
if(max < data[i]){
max = data[i];
}
}
BitSet bm=new BitSet(max+1);
System.out.println("The size of bm："+bm.size()); for(int i=0;i<data.length;i++){
bm.set(data[i], true);
} StringBuffer buf=new StringBuffer();
buf.append("[");
for(int i=0;i<bm.size();i++){
if(bm.get(i) == true){
buf.append(String.valueOf(i)+" ");
}
}
buf.append("]");
System.out.println(buf.toString()); }
}
/*
输出：
The size of bm：64
[1 2 5 9 11 12 15 21 ]
*/
2）使用BitSet做String类型数据的存在性校验
一种方案：
BitSet bitSet = new BitSet(Integer.MAX_VALUE);//hashcode的值域
//0x7FFFFFFF (int类型的最大值，第一位是符号位，可用Integer.MAX_VALUE代替)
String url = "http://baidu.com/a";
int hashcode = url.hashCode() & 0x7FFFFFFF;
bitSet.set(hashcode);
System.out.println(bitSet.cardinality()); //状态为true的个数
System.out.println(bitSet.get(hashcode)); //检测存在性
bitSet.clear(hashcode); //清除状态
使用上述算法需要解决Java中hashcode存在冲突的问题。即不同的String可能得到的hashcode是一样的（即使不重写hashcode方法）。如何解决？调整hashcode生成算法：我们可以对一个String使用多个hashcode算法，生成多个hashcode，然后在同一个BitSet进行多次“着色”，在判断存在性时，只有所有的着色位为true时，才判定成功。
String url = "http://baidu.com/a";
int hashcode1 = url.hashCode() & 0x7FFFFFFF;
bitSet.set(hashcode1);
int hashcode2 = (url + "-seed-").hashCode() & 0x7FFFFFFF;
bitSet.set(hashcode2);
System.out.println(bitSet.get(hashcode1) && bitSet.get(hashcode2));
//也可以在两个不同的bitSet上进行2次“着色”，这样冲突性更小。但会消耗双倍的内存
其实我们能够看出，这种方式降低了误判的概率。但是如果BitSet中存储了较多的数字，那么互相覆盖着色，最终数据冲突的可能性会逐渐增加，最终仍然有一定概率的判断失误。所以在hashcode算法的个数与实际String的个数之间有一个权衡，我们建议:
“hashcode算法个数 * String字符串的个数” < Integer.MAX_VALUE * 0.8；
另一种解决方案：多个BitSet并行保存
改良1)中的实现方式，我们仍然使用多个hashcode生成算法，但是每个算法生成的值在不同的BitSet中着色，这样可以保持每个BitSet的稀疏度(降低冲突的几率)。在实际结果上，比1)的误判率更低，但是它需要额外的占用更多的内存，毕竟每个BitSet都需要占用内存。这种方式，通常是缩小hashcode的值域，避免内存过度消耗。
BitSet bitSet1 = new BitSet(Integer.MAX_VALUE);//127M
BitSet bitSet2 = new BitSet(Integer.MAX_VALUE);
String url = "http://baidu.com/a";
int hashcode1 = url.hashCode() & 0x7FFFFFFF;
bitSet1.set(hashcode1);
int hashcode2 = (url + "-seed-").hashCode() & 0x7FFFFFFF;
bitSet2.set(hashcode2);
System.out.println(bitSet1.get(hashcode1) && bitSet2.get(hashcode2));
最后：我们要考虑是否有必要完全避免误判，可能有时候这种误判也是我们需要的结果。如果做到100%的正确判断率，在原理上说BitSet是无法做的，BitSet能够保证“如果判定结果为false，那么数据一定是不存在；但是如果结果为true，可能数据存在，也可能不存在(冲突覆盖)”,即“false == YES，true == Maybe”。有人提出将冲突的数据保存在类似于BTree的额外数据结构中，事实上这种方式增加了设计的复杂度，而且最终仍然没有良好的解决内存占用较大的问题。
3）BloomFilter(布隆姆过滤器)
BloomFilter 的设计思想和BitSet有较大的相似性，目的也一致，它的核心思想也是使用多个Hash算法在一个“位图”结构上着色，最终提高“存在性”判断的效率。请参见Guava BloomFilter。如下为代码样例：
Charset charset = Charset.forName("utf-8");
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(charset),2<<21);//指定bloomFilter的容量
String url = "www.baidu.com/a";
bloomFilter.put(url);
System.out.println(bloomFilter.mightContain(url));
5、延伸阅读和参考资料
BloomFilter(布隆姆过滤器)
http://www.programgo.com/article/17112318628/ Hash和Bloom Filter
http://wfwei.github.io/posts/hash-rel/ 相似哈希、完美哈希、Bloom Filter介绍 ***推荐阅读
http://shift-alt-ctrl.iteye.com/blog/2194519 BitSet使用
http://longshaojian.iteye.com/blog/1946865 java位运算实际应用
http://www.cnblogs.com/wuyuegb2312/p/3136831.html 位向量定义与应用 C++
http://blog.luoyuanhang.com/2016/05/15/I-位向量的实现与应用8/