这个位操作在Java中如何工作？

Question

我正在研究Java如何计算int的位集.
在我的脑海里,我有一些简单的东西(我认为是正确的):

public static int bitCount(int number){  
        final int MASK = 0x1;  
        int count = 0;  

        for(int i = 0; i < 32; i++){  
            if(((number >>> i) & MASK) == MASK){  
                count++;  
            }  
        }  
        return count;  
    }  

相反,我找到了一种方法,我完全不知道在做什么(对我来说似乎很神奇):

 i = i - ((i >>> 1) & 0x55555555);  
 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);  
 i = (i + (i >>> 4)) & 0x0f0f0f0f;  
 i = i + (i >>> 8);  
 i = i + (i >>> 16);  
 return i & 0x3f;  

有人可以帮助理解这是什么以及为什么一个简单的功能,如我首先想到的那个/可能是坏的？

Answer 1

当然

i = i - ((i >>> 1) & 0x55555555);

5的位模式是0101(4位),因此掩码是位模式的重复0116次.该行计算该数字的每两位对中的位数.如果考虑两位对,则(i >>> 1) & 0x1获取低位位置的高位.现在,有四种可能的两位模式

00 ~> 00 - 00 = 00
01 ~> 01 - 00 = 01
10 ~> 10 - 01 = 01
11 ~> 11 - 01 = 10

现在每个两位对包含原始位置的位数.

i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

接下来,我们计算每个四位组(也称为半字节)中的位数.通过屏蔽半字节0x3 = 0011(b),我们获得半字节的低位两位的位数,并(i >>> 2) & 0x3从半字节的高位两位获得计数.现在添加了这些计数.由于每个计数最多为2,因此总和最多为4,因此不会留下半字节.

i = (i + (i >>> 4)) & 0x0f0f0f0f;

现在计算每个八位字节中的位数.每个半字节包含在该位置原始中设置的位数.向右移动四位将计数从每个位置的高阶半字节移动到低阶半字节,这些都被添加.然后我们还将计数从低阶半字节移动到相邻八位字节的高阶nible,这被掩盖了& 0x0f0f0f0f.由于每个八位位组最多可以设置8位,因此计数不会离开八位位组的低位半字节.

i = i + (i >>> 8);

现在我们添加相邻八位字节对的计数.

i = i + (i >>> 16);

现在我们在高位两个八位位组和低位二位数中添加计数总数.

return i & 0x3f;

最后,除了最低阶八位字节之外的所有八位字节都被屏蔽掉,因为高阶八位字节仍然包含中间计数.

您的简单实现可能被认为是错误的原因是性能.复杂的bit-hack使用较少的操作而没有分支,因此速度更快.然而,这更容易出错.

计算int(或long)中的设置位的另一种巧妙方法是

public static int bitCount(int n) {
    int count = 0;
    while(n != 0) {
        ++count;
        n = n & (n-1);
    }
    return count;
}

这是有效的,因为n = n & (n-1)清除了最后一点,n并保持其他一切不变.如果位模式n结束

...100...0

比特模式n-1是

...011...1

并且最后1位之前的位n是相同的.在Java中,这保证也适用于负数,因为整数溢出具有环绕语义,因此,如果n = Integer.MIN_VALUE位模式是100...0并且n - 1变为Integer.MAX_VALUE位模式011...1.