Bitwise -bitCount的公式是什么意思？

Question

下面是来自Integer.bitCount(int )的代码副本

我理解所有的运算符，但不明白这些神奇的数字是如何计算出计数的！有人能给我解释一下吗？我可以看到模式(1,2,4,8,16 & 0x5,0x3,0x0f)。

        public static int bitCount(int i) {
            // HD, Figure 5-2
            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;
        }

Answer 1

好的，你的代码是针对32位整数的，但是让我们计算出16位的第一步，因为字母表没有32个字母。假设输入的二进制形式(字节边界由空格表示)为

i                  = ABCDEFGH IJKLMNOP
i >>> 1            = 0ABCDEFG HIJKLMNO
(i >>> 1) & 0x5555 = 0A0C0E0G 0I0K0M0O

因此，在第一个赋值中，右边的前两位是(AB - 0A)。尝试以下组合：

A  B  AB-0A
0  0  00-00 = 00
1  0  10-01 = 01
0  1  01-00 = 01
1  1  11-01 = 10

因此，结果的前两位给出了输入的前两位中的位数。同样的情况也适用于所有其他两位组。

现在，您再次执行相同的操作。这一次我们将考虑以4为基数的输入，因此两位构成了下面表示法的一个数字，我们可以使用完整的32位。

i                      = ABCD EFGH IJKL MNOP
i & 0x33333333         = 0B0D 0F0H 0J0L 0N0P
i >>> 2                = 0ABC DEFG HIJK LMNO
(i >>> 2) & 0x33333333 = 0A0C 0E0G 0I0K 0M0O

因此，结果的前四位是(0A + 0B) = A + B，对于任何其他四位组也是如此。因此，在这一点上，每组四位包含原始输入中这四位的位数。

使用基数16，下一步是

i                            = AB CD EF GH
i >>> 4                      = 0A BC DE FG
i + (i >>> 4)                = A(A+B) (B+C)(C+D) (D+E)(E+F) (F+G)(G+H)
(i + (i >>> 4)) & 0x0f0f0f0f = 0(A+B) 0(C+D) 0(E+F) 0(G+H)

这是可行的，因为每个四比特组中的比特计数将始终小于四，因此添加两个这样的计数可以用四个比特表示，而不会溢出。因此，加法不会有从一个四位基数16位到另一个四位基数16位的溢出。此时，每个字节都包含该输入字节的位数。Other algorithms可能会使用巧妙的乘法从那里开始，但您引用的代码也会在接下来的步骤中使用加法。

i                           = A B C D
i >>> 8                     = 0 A B C
i2 = i + (i >>> 8)          = A (A+B) (B+C) (C+D)
i2 >>> 16                   = 0 0 A (A+B)
i3 = i2 + (i2 >>> 1         = A (A+B) (A+B+C) (A+B+C+D)
i3 & 0x3f                   = 0 0 0 (A+B+C+D)

这再次利用了数字之间没有溢出的事实。