这种位操作在 Java 中是如何工作的？

我正在研究 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;  

有人可以帮助理解它的作用以及为什么像我首先想到的那样的简单函数是/可能是坏的吗？

Sure

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

5 的位模式是0101（四位），因此掩码是位模式的重复01十六次。该行计算数字的每个两位对中的位数。如果考虑两位数对，(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;

现在对每个八位位组中的位进行计数。每个半字节包含原始数据中该位置设置的位数。右移四位将计数从每个位置的高位半字节移动到低位半字节，并将它们相加。然后，我们还将计数从相邻八位字节的低阶半字节移动到高阶半字节，该计数被& 0x0f0f0f0f。由于每个八位位组最多可以设置八位，因此计数不会留下八位位组的低位半字节。

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

现在我们将相邻八位位组对的计数相加。

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

现在我们将高位两个八位位组和低位两个八位位组中的计数总数相加。

return i & 0x3f;

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

您的简单实现可能被认为不好的原因是性能。复杂的位破解使用更少的操作并且没有分支，因此速度更快。然而，它更容易出错。

另一种计算设置位的巧妙方法int (or long) is

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 is

...011...1

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