java - Long.bitCount() 如何找到设置的位数？

Question

我知道这是代码。但我无法理解它的作用

 `public static int bitCount(long i){
         i = i - ((i  > > > 1) & 0x5555555555555555L);
         i = (i & 0x3333333333333333L) + ((i  > > > 2) & 0x3333333333333333L);
         i = (i + (i  > > > 4)) & 0x0f0f0f0f0f0f0f0fL;
         i = i + (i  > > > 8);
         i = i + (i  > > > 16);
         i = i + (i  > > > 32);
       return (int)i & 0x7f;
 }`

Answer 1

我们以255为例。随着我们的进行，这些位被组合在一起。首先，我们从 255 开始，作为 0b1111.1111(二进制中的 8 个 1)

第一行代码是:

i = i - ((i  > > > 1) & 0x5555555555555555L);

这条线正在梳理每一对 1。因为我们有 8 个 1，所以我们期望组合我们的对，并得到类似 2,2,2,2 的结果。由于它是二进制的，我们期望 10101010。

让我们看看i >> > 1。我是 0b1111.1111，这是向下移动 1，所以我们得到 0b0111.1111。我们取 & 与 0b0101.0101 的交集(这是 5 在二进制中为 101)。这样做可以保留我们一半的位，特别是所有最初位于偶数点的位(我们初始数字的第 2、4、6、8 位)。

然后我们从我们的初始值中减去它，这有点 hacky。我们正在尝试将我们的最高位添加到我们的最低位，所以我们可以这样做:

((i > > > 1) & 0x5555) + (i & 0x5555)

左边的项是最高位，右边的项是最低位。但是我们知道 i = 2*(top bits) + 1*(bottom bits)，因为 top bits 被上移 1(这与乘以 2 相同)。因此，通过将最高位减去 1 次，我们得到了相同的结果。

好的，现在我们准备好第二行代码了。我们目前有 i 的 0b1010.1010，我们准备添加每对 2。我们期望得到 4,4(每一半使用 4 位)，或 0100.0100二进制。代码是:

i = (i & 0x3333333333333333L) + ((i  > > > 2) & 0x3333333333333333L);

我们正在获取每组 4 个中前 2 个数字和后 2 个数字，并将它们相加。 0x3333 = 0b0011.0011.0011.0011 因此我们可以看到，& 与 3 的交集将底部的 2 个数字保持在一个组中。我们首先得到底部的两个数字，然后我们将 i 移动 2 个位置以获得顶部的 2 个数字。然后我们添加:0010.0010 + 0010.0010 = 0100.0100。完全符合预期。

接下来我们将 2 组 4 个相加。

 i = (i + (i  > > > 4)) & 0x0f0f0f0f0f0f0f0fL;

0x0f0f = 0b0000111100001111，因此如果我们与此相交，我们将保留每 4 个数字。我们将 i 加到其自身降档 4，因此我们计算 0100.0100 + 0000.0100 = 0100.1000。 4 + 4 应该还给 8，并且 8 = 0b1000，但是前面的“4”还是需要去掉。与 0f0f0f0f 的交集执行此操作。

所以现在我们有了 0b1000，它是 8。其余的步骤添加了更高的位(比如 2 组 8 在一起，而不是 2 组 16..)但是因为我们的数字(255) 只有 8 位长，高位全为 0，所以这不会影响我们的结果。