java - 在 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);
  }
}

我找到了:Count number of 1's in binary representation但略有不同。

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