8

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

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

4

2 回答 2

7

当然

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

5 的位模式是0101（四位），所以掩码是位模式的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;

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

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

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

于 2012-06-03T22:30:56.960 回答
3

cool 方法仅适用于计算机具有有限范围的 int 值。对于无限范围（如 BigInteger），它不会那么容易工作（以及其他很酷的位算法），因为您需要在计算之前知道所有需要的掩码。

无论如何，您可以通过以下方式阅读它的工作原理：http: //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

它在本章的底部。

于 2012-06-03T22:26:01.443 回答