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

我知道这是代码。但我不明白它的作用

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

最佳答案

让我们以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的二进制形式)。这样做可以保留一半的位，尤其是最初位于偶数位的所有位(从我们的初始编号开始的第二，第四，第六，第八位)。

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

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

左边的术语将是高位，而右边的术语将是低位。但是我们知道i = 2 *(最高位)+ 1 *(最低位)，因为最高位上移了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的交集&保留在组中的后两个数字。我们首先获得底部的两个数字，然后将i移至2个点以得出顶部的2个数字。然后我们添加:0010.0010 + 0010.0010 = 0100.0100。完全符合预期。

接下来，我们将2组(共4组)加在一起。

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

0x0f0f = 0b0000111100001111，所以如果我们与之相交，我们将保留每四个数字。我们将i加到降档的4本身，因此我们计算0100.0100 + 0000.0100 = 0100.1000。 4 + 4应该返回8和8 = 0b1000，但是顶部的“4”仍然需要删除。与0f0f0f0f的交集可以做到这一点。

因此，现在我们有了0b1000，它是8。其余的步骤加进甚至更高的位(例如2组8个，合起来比2组16个..)，但是由于我们的数字(255)只有8位长，因​​此高位全为0，因此这不会影响我们的结果。