Long.bitCount()是如何找到set位数的？

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 (二进制数为81)。

第一行代码是：

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

这条线对1的每对都进行了梳理，因为我们有8‘s，所以我们希望把它们组合起来，得到2,2,2,2，2，2，2。因为它是二进制的，所以我们期望10101010。

让我们看看i > > > 1。我是0b1111.1111，这是下降1，所以我们得到了0b0111.1111。我们采用交点，&，与0b0101.0101 (这是从5是101二进制)。这样做保留了我们一半的比特，特别是所有最初处于偶数点的比特(第2，4，6，8位)。

然后，我们从初始值中减去这一点，这有点麻烦。我们正试图将我们的顶部比特添加到我们的底部比特中，因此我们可以这样做：

((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在一个组中保持下两个数字。我们先得到下两个数字，然后移动我超过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。其余的步骤加进更高的位数(就像两个8组加在一起，比两个16组加起来。)但是，由于我们的数字(255)只有8位长，更高的位数都是0，所以这不会影响我们的结果。

Answer 2

说明：

此方法返回您的long将作为二进制数字的位：bitcount.htm

• > > >是逻辑上的移位:它用后面的数字n移动值；前n位填充了零：Difference between >>> and >>。
• &是按位和：examples.htm
• 0x3333333333333333L只是一种用十六进制表示某些比数的方法。转换器：http://coderstoolbox.net/number/

它的工作原理：

• 例如，让我们以i=10十进制= 1010二进制
• 第一线：i = i - ((i > > > 1) & 0x5555555555555555L);
  • 0x5555555555555555L十六进制= 101010101010101010101010101010101010101二进制
  • 1010被移动一位：0101
  • 0101与101010101010101010101010101010101010101 : {0 = 1} = 0 , {1 = 0} = 0 , {0 = 1} = 0 , {1 = 0} = 0 : 0000相比是按位计算的
  • 0000 binary=0十进制
  • 10(i)减去0

• 二线：i = (i & 0x3333333333333333L) + ((i > > > 2) & 0x3333333333333333L);
  • 0x3333333333333333L十六进制=11001100110011001100110011001100110011二进制
  • (i > > > 2)的意思是我被两个移位: i=10，二进制：1010；在移位后：0010
  • i(1010)与11001100110011001100110011001100110011的比较是1001 =9小数点
  • 0010比较的是0001，什么是1。
  • 9+1=10=i

我认为这是个足够的例子。希望能帮上忙。

Answer 3

算法是：

若要计算2^n位数中的1位数(在本例中为n= 6，但您可以为任何机器数大小编写此算法)，请将其分成两半，并使用移位操作同时计算左半和右半的1位数，将结果存储在每一半中最右边(最不重要)的位中。然后，通过将左侧移到右侧，然后添加这些结果。

这是一种递归算法--你现在将同样的算法应用于双方。让它变得更快的聪明之处是，您可以使用shift操作，它同时对两个部分执行该算法。所以算法是O(log(N))，其中N= 2^n是机器编号中的位数。

所以最后一行代码对每个季度进行“重组”，然后是每半个，然后是整个过程。