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。i 是0b1111.1111，现在向下移动 1，所以我们得到0b0111.1111。我们取交集 ,&与0b0101.0101（这是从 5 变为二进制 101 得出的）。这样做可以保留一半的位，特别是最初位于偶数位置的所有位（初始数字的第 2、4、6、8 位）。

然后我们从初始值中减去这个值，这有点hacky。我们正在尝试将顶部位添加到底部位，因此我们可以这样做：

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

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

好的，现在我们准备好第二行代码了。目前我们已经有了0b1010.1010i，并且准备好将每对 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，因此这不会影响我们的结果。