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 次，我们得到相同的结果。

好的，现在我们准备好第二行代码了。我们目前有 0b1010.1010 表示 i，我们准备添加每对 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，所以这不会影响我们的结果。

Answer 2

解释：

此方法 returns 您的 long 将作为二进制数的位：https://www.tutorialspoint.com/java/lang/long_bitcount.htm

> > > 是逻辑移位：它将值移位它后面的数字 n ；前 n 位用零填充：Difference between >>> and >>
&是按位与：https://www.tutorialspoint.com/java/java_bitwise_operators_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二进制=0十进制
- 10(i)减去0
第二行：i = (i & 0x3333333333333333L) + ((i > > > 2) & 0x3333333333333333L);
- 0x3333333333333333L十六进制=11001100110011001100110011001100110011二进制
- (i > > > 2) 表示 i 移动了两个：i=10，二进制：1010；移动后：0010
- i(1010) 与 11001100110011001100110011001100110011 相比是 1001 = 9 decimal
- 0010 比较的是 0001，什么是 1.
- 9+1=10=我

我认为这已经足够了。希望对你有帮助。

Answer 3

算法是：

要计算 2^n 位数字中 1 位的数量（在这种情况下 n = 6，但您可以为任何机器数大小编写此算法），将其分成两半，然后使用移位操作，同时计算左半部分和右半部分中 1 位的个数，将结果存储在每半部分的最右边（最低有效位）位中。然后通过将左侧移动到右侧并相加来合并这些结果。

这是一个递归算法---你现在对两边应用相同的算法。让它变快的巧妙之处在于您可以使用移位操作同时在两半上执行算法。所以算法是 O(log(N)) 其中 N = 2^n 是你的机器号中的位数。

所以最后几行代码正在对每个季度进行“重组”，然后是每个季度，然后是整个季度。

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

How does Long.bitCount() finds the number of set bits?

java

bitcount

long-integer

解释：

工作原理：