比特计数方法

Question

有人能解释一下这个bitcount方法吗？

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

- user3603642

Answer 1

这基于三个观察结果：

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

前两点一起给出了一个简单的递归算法，将字符串分成两半，对两部分进行递归处理，然后返回它们的位数之和。基本情况是只有一个位，直接返回该位。到目前为止还很简单。

第三个观察结果非常重要，它意味着如果你用每个子串的位数替换它本身，它总是可以适应其可用空间。这意味着如果你给每个计数两倍的空间（通过分离奇数和偶数组），你可以将它们相加，不会从一组进位到下一组。然后你可以将它重写为以下形式：

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个一组的和：

[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个位。

- harold

Answer 2

为什么不添加一些记录代码，在每个步骤显示i的二进制，看看能否弄清楚发生了什么？

或者将其缩小到较小的位数（比如8位），在纸上逐步解决。

这会让你对代码有更好的感觉，而不是简单地由别人解释给你听。 此页面可能会有所帮助。

- Phil Anderson

---

我建议您使用纸张并写下正在发生的事情...只有这些信息，您才能理解正在发生的事情。 - Tobi

Answer 3

这个算法至少可以追溯到HAKMEM项目169

    LDB B,[014300,,A]      ;or MOVE B,A then LSH B,-1
    AND B,[333333,,333333]
    SUB A,B
    LSH B,-1
    AND B,[333333,,333333]
    SUBB A,B               ;each octal digit is replaced by number of 1's in it
    LSH B,-3
    ADD A,B
    AND A,[070707,,070707]
    IDIVI A,77             ;casting out 63.'s

这十个指令，加上常数扩展，可以适用于长度达到62个字；而十一个指令则足以适用于长度达到254个字。

- ddyer