BitCount法

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

它基于三个观察结果，

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‘still使用各种技巧来优化一些操作，例如，4组可以用最后的掩蔽进行求和，因为计数最多可达4，所以直接加起来最多可得到8，这仍然适合它可用的4位。

Answer 2

为什么不添加一些日志代码，在每个步骤中以二进制格式显示i，看看是否可以计算出正在发生的事情？

或者把它缩小到一个较小的位数(例如8位)，然后在纸上处理它。

它会让你对代码有更好的感觉，而不是简单地向你解释。

此页可能会有帮助。

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；11个指令最多可达254。