4

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

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

3 回答 3

3

我们以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.1010for 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, and 8 = 0b1000，但仍然需要删除顶部的“4”。与的交集就是这样做的0f0f0f0f。

所以现在我们有了0b1000，也就是 8。其余的步骤添加了更高的位（比如 2 组 8 在一起，而不是 2 组 16 ..）但是由于我们的数字（255）只有 8 位长，所以更高的位都是 0，所以这不会影响我们的结果。

于 2017-05-21T05:44:29.317 回答
1

解释 ：

此方法返回您 long 需要的二进制数位：https ://www.tutorialspoint.com/java/lang/long_bitcount.htm

这个怎么运作 ：

  • 例如，让我们取 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 十进制
    • 0010比较的是0001，什么是1。
    • 9+1=10=我

我认为这是足够的例子。希望能帮助到你。

于 2017-05-21T05:47:37.760 回答
0

算法是：

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

这是一个递归算法——您现在对双方都应用相同的算法。使其快速的聪明之处在于，您可以使用同时在两半上执行算法的移位操作。所以算法是 O(log(N)) 其中 N = 2^n 是你的机器号中的位数。

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

于 2020-06-25T00:54:02.000 回答