#Lucene# org.apache.lucene.util.BitUtil.pop(long x) 笔记
今天读 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 种:
左移 <<
右移 >>>(不带符号右移), >>
?
?
?
?
1 楼 vivizhyy 2012-05-25
via: 王奋进
引用
以统计32位整数为例,假设32位全部为1,16进制表示为
x=0xFFFFFFFF,
经过前三步,就是1、2、4移位运算之后,
x=0x08080808
经过 x = x + (x >>>; 之后
x=0x08101010
再经过x = x + (x >>> 16);之后
x=0x08101820
最后return x & 0x0000003F;
result=0x00000020
可以看到结果是正确的。
具体的原因就是因为32位整数,所有1的个数加起来不会超过0x3F,而64位中1的个数不会超过0x7F,也就是结果最多不过7位。
到移动8位的时候,结果已经聚集到低位来了,高位的结果不会对低位造成影响,所以不用再做额外的与运算。