位计数方法 [英] BitCount Method

问题描述

任何人都可以解释这种位计数方法.

Can anyone Explain this bitcount method.

public static int bitCount(int i) {
        // Hacker's Delight, Figure 5-2
        i -= (i >> 1) & 0x55555555;
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        i = ((i >> 4) + i) & 0x0F0F0F0F;
        i += i >> 8;
        i += i >> 16;
        return i & 0x0000003F;
    }

推荐答案

它基于三个观察结果，

1. 单个位的位数就是该位本身.
2. 两个位串的串联连接的位数是它们的位数之和.
3. 任何字符串的位数都不超过该字符串本身的位数.

前两点共同为您提供了一个简单的递归算法，将字符串分成两半，对两个递归，返回总和.基本情况是您返回的单个位.到目前为止很简单.

The first two points together give you a simple recursive algorithm, split the string in two halves, recurse on both, return the sum. The base case is a single bit which you return. Simple so far.

第三个观察点非常重要，这意味着如果将每个子字符串替换为其位计数，它将始终适合其可用空间.这意味着，如果您给每个计数加倍的空间(通过将奇数组和偶数组分开)，您可以将它们相加，并且不会有一个从进位到下一组的进位.然后，您可以将其重写为以下形式:

The third observation is very important, it means that if you replace each substring with its bitcount, it will always fit in the space available to it. It means that if you give every count twice as much space (by separating the odd and the even groups), you can sum them and there will be no carry from one group into the next. Then you can rewrite it to this form:

i = (i & 0x55555555) + ((i >> 1) & 0x55555555); // sum groups of 1
i = (i & 0x33333333) + ((i >> 2) & 0x33333333); // sum groups of 2
i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f); // sum groups of 4
...

以此类推.在这里发生的是，在+的左侧，我们采用了偶数组(第0、2、4等)，而在右侧，我们采用了奇数组，并将它们与相应的偶数组对齐.例如，对2个组进行求和:

And so on. What happens here is that on the left side of the + we take the even groups (0th, 2nd, 4th etc) and on right side we take the odd groups and align them with their corresponding even groups. For example, summing groups of 2:

[10 01 00 01 00 01 10 10]  // note that 11 cannot occur
split
even:  [0001 0001 0001 0010]
odd:   [1000 0000 0000 1000]
align: [0010 0000 0000 0010]
sum:   [0011 0001 0001 0100]

然后，Hacker's Delight使用各种技巧来优化某些操作，例如最后可以仅使用掩码将4个一组进行求和，因为计数最多增加到4，因此直接相加最多可以得到8，因此仍然适合它可用的4位.

Then Hacker's Delight uses various tricks to optimize some operations out, for example groups of 4 can be summed using only the masking at the end, because the counts go up to 4 at most so summing them directly gives 8 at most, which still fits in the 4 bits available to it.

这篇关于位计数方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！