位计数方法

Question

谁能解释一下这个位计数方法。

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

Answer 1

为什么不添加一些日志记录代码以在每个步骤中以二进制形式显示 i 并查看是否可以弄清楚发生了什么？

或者将其减少到更小的位数（比如 8 个）并在纸上完成。

与简单地向您解释代码相比，它会让您对代码有更好的感觉。

This page 可能会有帮助。

Answer 2

该算法至少可以追溯到 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

这 10 条指令，扩展了常量，适用于最多 62 个字长。; 11 最多 254..

Answer 3

它基于三个观察结果，

单个位的位数就是该位本身。
两个位串串接的位数是它们的位数之和。
任何字符串的位数都不会比该字符串本身多。

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

第三个观察结果非常重要，这意味着如果用它的位数替换每个子字符串，它将始终适合它可用的 space。这意味着如果你给每个计数两倍 space （通过将奇数组和偶数组分开），你可以将它们相加并且不会有进位从一组到下一组。然后你可以改写成这样的形式：

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

位计数方法

BitCount Method

java

bit-manipulation