在O(n)和O(log n)时间复杂度内计算二进制表示中的1的数量，其中n是位数。

Question

在O(n)和O(log n)时间复杂度内计算二进制表示中的1的数量，其中n是位数。

3

我有两个任务 - 在O(n)和O(log n)的时间复杂度内统计二进制表示中1的数量。由于第一个任务比较简单，我不知道如何在没有排序等情况下以O(log n)的时间复杂度统计它们的数量。这是否可能呢？目前我的代码：

public class CountOnes {
  public static void main(String[] args)
  {
    System.out.println("Program to count ones");
    countOnesInLinearTime("110");
    countOnesInlogarithmicTime("110");
  }

  private static void countOnesInlogarithmicTime(String binaryRepresentationOfLong) {
    //TODO
  }

  private static void countOnesInLinearTime(String binaryRepresentationOfLong) {
    int numberOfOnes = 0;
    for(int i = 0; i < binaryRepresentationOfLong.length(); i++)
    {
      if(binaryRepresentationOfLong.charAt(i) == '1')
      {
        numberOfOnes++;
      }
    }
    System.out.println(numberOfOnes);
  }
}

我发现了这个链接：二进制表示中1的数量不过有些不同。

- Michu93

1

我猜想你需要为 int、long 等类型的数据做这个操作，也就是说需要支持移位？ - Willem Van Onsem

2

你确定你的解决方案吗？“String”不是任何东西的二进制表示。 - Sharon Ben Asher

1

输入是否总是字符串？如果是这样，那么您必须查看每个字符。根据您链接的问题上的此评论，给定整数输入，该解决方案将为logN。https://dev59.com/_mox5IYBdhLWcg3w8IxJ#L6GdEYcBWogLw_1bkkNm - OneCricketeer

2个回答

4

您可以按照以下方式计算一个long中设置位的数量：

long l = 1425142514251425142L; // some value
long c = l;
c = ((c >> 1) & 0x5555555555555555L) + (c & 0x5555555555555555L);
c = ((c >> 2) & 0x3333333333333333L) + (c & 0x3333333333333333L);
c = ((c >> 4) & 0x0f0f0f0f0f0f0f0fL) + (c & 0x0f0f0f0f0f0f0f0fL);
c = ((c >> 8) & 0x00ff00ff00ff00ffL) + (c & 0x00ff00ff00ff00ffL);
c = ((c >> 16) & 0x0000ffff0000ffffL) + (c & 0x0000ffff0000ffffL);
c = ((c >> 32) & 0x00000000ffffffffL) + (c & 0x00000000ffffffffL);

我们基本上执行了O(n)次操作，其中n是位数。对于第i步（i从1开始），我们执行类似以下的操作：

c = ((c >> 2ⁱ) & mask) + (c & mask);

口罩具有二进制结构：

0101010101010101
0011001100110011
0000111100001111
0000000011111111
...

因此，在第i步中，它是2ⁱ个零的重复，后跟2ⁱ个一，并且重复此过程直到达到64位。

这是如何工作的？通过将一个2ⁱ向右移动，我们“对齐”数字的两个部分。第一部分是放置在mask为0的位置的数字1，另一部分是mask为1的位置。然后我们将两部分相加。

在第一步中，这意味着对于每两个比特，我们将比特向右对齐，将它们相加，而这个和的结果（一个介于0和2之间的值，包括0和2），可以用两个比特来表示。因此，c现在包含了32个2比特数字的序列，每个数字表示两个比特数的总和。

在下一次迭代中，我们再次执行对齐，并且现在我们将16个2比特数字与其左边的邻居（另外16个2比特数字）相加，这可能会产生从0到4的值，因此我们可以用3比特来表示该数字，但我们使用了4比特的空间。

每次迭代，因此我们将其他2ⁱ个数字与2^i-1个数字相加，经过O(log n)后，我们最终将两个长度为n/2位的数字相加，这将产生设置位的总数。

在这里，我们假设我们可以在常数时间内添加两个数字，并且在常数时间内进行移位和掩码操作。如果数字是任意大的，则不是这种情况，因此该算法在严格意义上不是O(log n)。事实上，对于任意大的数字，该算法甚至更糟糕。

也就是说，除非您预先了解数字的结构并能够利用它，否则您无法更快地计算任意长的算法，因为至少需要读取每个比特一次以确定其值。

- Willem Van Onsem

@Henry：这正是最后一段所讲的。我们可以在*O(n)的时间复杂度内对两个任意大的整数求和，同时进行掩码和移位操作（不会增加额外成本），但是需要注意的是，考虑到算术运算的时间复杂度，这确实不是O(n log)*。 - Willem Van Onsem

这是其中一种优化，但增长率不是 O(logn)。 - Kaidul

@Kaidul：如之前所述，如果位大小是固定的（大小为n），则需要n个这样的步骤，我们在此假设加法、掩码和移位都在恒定时间内完成，但对于任意大的数字，这是不可能的。在少于*Ω(n)*的时间内计算任意大数的位数是不可能的。 - Willem Van Onsem

@Kaidul：我所说的log n步骤是指对于32位的int，需要少一步。对于（假设的）128位数字，需要多一步，对于256位数字，需要额外一步。但是这些步骤，就像所有移位/位运算和加法一样，在软件中实现时不会以恒定时间运行，而是与位数成线性关系，或在某些情况下在硬件中为*O(log n)*（因为我们可以使用“硬件并行性”）。 - Willem Van Onsem

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kaidul · Accepted Answer

假设您的输入字符串将为整数，而不是字符串，可以使用Brian Kernighan算法实现：
从一个数字中减去1会切换所有位（从右到左）直到最右设置位（包括最右设置位）。因此，如果我们将一个数字减去1并对它本身进行按位与(&)运算（n & (n-1)），则取消设置最右边的位。如果我们在循环中执行 n & (n-1)，并计算循环执行的次数，我们可以得到集合位数。
这种解决方案的美妙之处在于它循环的次数等于给定整数中设置位的数量。

1. Initialize count: = 0
2. If integer n is not zero
      (a) Do bitwise & with (n-1) and assign the value back to n
          n: = n&(n-1)
      (b) Increment count by 1
      (c) go to step 2
3. Else return count

实现

int countNumberOfOnes(int n) { 
    int count = 0; 
    while (n > 0) { 
        n &= (n - 1); 
        count++; 
    } 
    return count; 
}