lucene org.apache.lucene.util.BitVector.java

qianqianling

1 org.apache.lucene.util分析
package org.apache.lucene.util;
Optimized implementation of a vector of bits.  This is more-or-less like
java.util.BitSet, but also includes the following:
a count() method, which efficiently computes the number of one bits;
optimized read from and write to disk;
inlinable get() method;
store and load, as bit set or d-gaps, depending on sparseness;
/*优化实现了一个位向量。大致类似于java.util.BitSet,但是包含了下面的内容：
  一个 count() 方法，有效的计算了bit 1的个数；
  优化对磁盘的读和写；
  get() method;(inlinable?)
  根据稀疏程度，决定在存储和载入用位变量还是d-gaps；
*/

public final int count() {
// if the vector has been modified
if (count == -1) {
int c = 0;
int end = bits.length;
for (int i = 0; i < end; i++)
c += BYTE_COUNTS[bits & 0xFF];  // sum bits per byte
count = c;
}
return count;
}

count()方法，用来统计这个bit向量中1的个数。由于bit其实是以byte数组的形式存储的，一个byte有8个bit。常规的方法可以对每个byte拿来用位移或者位与的方式得到每位判断是否是1，求总数。这里的方法是：
这个其实是一个查找表，对于8位的byte，每位都有1或0两种可能，所以一共有2^8=256种可能的值，每个值对应1的个数是固定的。假如我们预先把这256种可能值都算好存到数组里，到时候只要一次取值就可以了。查找表其实是一种空间换时间的方法，适用于函数的自变量范围较小的情况。它能够显著提高速度（都直接取值了。。。）。
http://michaelo-o.spaces.live.com/Blog/cns!2E4590EFB3E88D3A!364.entry
首先通过bits to int的转换，得到的int数值就可以用BYTE_COUNTS[int]来取得bit 1的个数。
测试代码如下：
public class Test {
private static final byte[] BYTE_COUNTS = {  // table of bits/byte
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
public static void main(String[] args){
byte b = (byte)-1;
char[] c = getraw(b);
System.out.println("int fomate(between -128~127):"+(int)b);
int i=8;
System.out.print("raw fomate:");
while(i--!=0){
System.out.print(c);
}
System.out.println();
System.out.println("bit 1 counts:"+count(b));
}
public static  int count(byte bits) {
int c = BYTE_COUNTS[bits & 0xFF];
return c;
}

public static char[] getraw(byte bits){
int i=0;
char[] c = new char[8];
c = (bits&1)==0?'0':'1';i++;
while((bits>>=1)!=0&&i<8){
c = (bits&1)==0?'0':'1';i++;
}
while(i<8){
c='0';i++;
}
return c;
}
}

程序结果：
int fomate(between -128~127):-1
raw fomate:11111111
bit 1 counts:8