如何在Java中此位操作的工作？ [英] How does this bit manipulation work in Java?

问题描述

我一直在寻找到Java如何计算设置一个int位。结果
我在我的头脑简单的东西像这样（我认为这是正确的）：

I was looking into how Java counts bits set of an int.
I had in my mind something simple like this (which I think is correct):

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;  
    }  

相反，我发现我完全不知道是什么做的（好像魔术给我）的方法：

Instead I found a method that I absolutely have no idea what is doing (seems like magic to me):

 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;  

有人能帮助理解这是什么呢，为什么一个简单的功能，像我来到了作为第一个想到的一个是/可能是坏？

Could someone help understand what this does and why a simple function like the one I came up as first thought is/could be bad?

推荐答案

确定

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

5位模式为 0101 （四位），所以面膜是位模式的重复 01 十六倍。这条线计算比特的每两个比特对数的数目。如果你考虑两位对，（I＆GT;＆GT;＆GT; 1）及为0x1 获取低位位置高位。现在，有四种可能的双位模式

The bit pattern of 5 is 0101 (four bits), so the mask is a repetition of the bit pattern 01 sixteen times. This line counts the number of bits in every two-bit pair of the number. If you consider two-bit pairs, (i >>> 1) & 0x1 gets the high-order bit in the low-order position. Now, there are four possible two-bit patterns

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

和每两个比特对现在包含比特的原始有在这些位置的数目

and each two-bit pair now contains the number of bits the original had in those positions.

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

接下来，我们数着各自四位组（又名四位）在位。通过屏蔽一个四位与 0x3中= 0011（B），我们得到的是在低阶位的计数四位的两位，而 （ⅰ＆GT;＆GT;→2）及0x3中获得来自半字节的高阶两位计数。这些计数现在增加。由于每个计数至多2，总和为至多4，因而不离开半字节

Next, we count the bits that were in each four-bit group (aka nibble). By masking a nibble with 0x3 = 0011(b), we get the count of bits that were in the lower order two bits of the nibble, and (i >>> 2) & 0x3 gets the count from the higher order two bits of the nibble. These counts are now added. Since each count was at most 2, the sum is at most 4, hence doesn't leave the nibble.

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

现在在每个八位位组的位进行计数。每个半字节包含在原来的那个地方设置位的数量。由四个位移向右移动从在每个地方到下半字节的高阶四位计数，这些被添加。那么我们也移离下半字节到相邻八位组的高阶nible计数，由该＆放大器屏蔽掉; 0x0f0f0f0f 。由于每个字节最多可以有八位设置，计数不离开八位字节的低位四位。

Now the bits in each octet are counted. Each nibble contains the count of bits set in the original in that place. Shifting right by four bits moves the count from the higher order nibble in each place to the lower order nibble, these are added. Then we also moved the count from the lower order nibble to the higher order nible of the adjacent octet, that is masked out by the & 0x0f0f0f0f. Since each octet can have at most eight bits set, the count doesn't leave the lower order nibble of the octet.

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

现在我们增加对相邻的八位字节的数量。

Now we add the counts of the pairs of adjacent octets.

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

现在我们增加计数的总数中的高阶16位，低位两项。

Now we add the totals of the counts in the high order two octets and the low order two.

return i & 0x3f;

最后，除了最低阶八位所有八位字节屏蔽掉，因为高阶八位仍然含有中间数。

Finally, all octets except the lowest order octet are masked out, since the higher order octets still contained intermediate counts.

为什么你简单的实现可能会被认为是不好的原因是性能。令人费解的位黑客使用更少的操作和没有分支，所以它是速度更快。它是，然而，更容易得到错误的

The reason why your simple implementation might be considered bad is performance. The convoluted bit-hack uses fewer operations and no branches, so it is faster. It is, however, far easier to get wrong.

另一种巧妙的方法在计算设定位的 INT （或长）是

Another neat way to count the set bits in an 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 与

That works because n = n & (n-1) clears the last set bit in n and leaves everything else untouched. If the bit pattern of n ends with

...100...0

的位模式 N-1 是

...011...1

和最后1位前位ñ是相同的。在Java中，这是保证工作还为负数，因为整数溢出具有环绕式传递，如果 N = Integer.MIN_VALUE的，该位模式是 100 ... ... 0 和 N - 1 变成 Integer.MAX_VALUE的通过位模式 011？1 。

and the bits before the last 1-bit in n are the same. In Java, that is guaranteed to work also for negative numbers because integer overflow has wrap-around semantics, so if n = Integer.MIN_VALUE, the bit pattern is 100...0 and n - 1 becomes Integer.MAX_VALUE with the bit pattern 011...1.

这篇关于如何在Java中此位操作的工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！