以 O(n) 和 O(log n) 的二进制表示计数 1，其中 n 是位数

Question

我有两个任务 - 在 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 的数量，但略有不同。

Answer 1

假设您的输入字符串将是整数，而不是字符串，则可以使用 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; 
}