#Lucene# org.apache.lucene.util.BitUtil.pop(long x) 笔记

q986

　　今天读 Lucene 源码，有这样一个函数：

/** Returns the number of bits set in the long */
public static int pop(long x) {
/*
* Hacker's Delight 32 bit pop function:
* http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
*
* int pop(unsigned x) { x = x - ((x >> 1) & 0x55555555); x = (x &
* 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) &
* 0x0F0F0F0F; x = x + (x >> 8); x = x + (x >> 16); return x &
* 0x0000003F; }*
*/
// 64 bit java version of the C function from above
x = x - ((x >>> 1) & 0x5555555555555555L);
x = (x & 0x3333333333333333L) + ((x >>> 2) & 0x3333333333333333L);
x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
x = x + (x >>> 8);
x = x + (x >>> 16);
x = x + (x >>> 32);
return ((int) x) & 0x7F;
}
　　这一长串代码读得晕晕乎乎，李今
同学 share 了一个链接
说明这段代码。这个函数与 java.lang.Long 中的 bitCount 函数一模一样 -.- 这段代码的原作者实在太有才了，这么几行代码就大肆发挥了一下：

x = x - ((x >>> 1) & 0x5555555555555555L);
//上面这句与下面这句的意思是一样的：
x = (x &  0x5555555555555555L) + ((x >>> 1) & 0x5555555555555555L)
x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
//上面这句的意思也跟下面这个一样：
x = (x & 0x0F0F0F0F0F0F0F0FL) + ( (x >>> 4) & 0x0F0F0F0F0F0F0F0FL);
　　这段代码的目的就是求二进制数中 1 的个数，该作者用三个写法写了一个意思……
　　这段代码的详细解说请见 求二进制数中1的个数。

　　更多的 #求二进制数中 1 的个数# 的文章请见：算法-求二进制数中1的个数

　　遗留了一个问题：作者在用二分法求 x 中 1 的个数时，到每 8 位的时候怎么就不写成下面这样了？

(x + (x >>> 8)) & 0x00ff00ff00ff00ffL
　　而是直接移位相加？
　　顺便说，java 中的移位操作有 3 种：
　　左移 <<
　　右移 >>>(不带符号右移)， >>