Java位向量的实现原理与巧妙应用

时间:2024-08-06 13:38:14

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/

  

相关文章