连续自然数二进制中 1 的个数

连续自然数二进制中 1 的个数

问题

这个题目说的是，给你一个非负整数 n，你要分别计算出 0 ~ n 这 n + 1 个整数的二进制表示中 1 的个数，将结果以数组的形式返回。

比如说，给你的整数 n 等于 4：

n = 4

你要分别计算出 0/1/2/3/4 这 5 个数的二进制表示中 1 的个数。我们先把这 5 个数的二进制表示写出来：

0: 0
1: 1
2: 10
3: 11
4: 100

于是可以得到这 5 个数二进制表示中 1 的个数分别是 0/1/1/2/1，返回这个数组即可：

[0, 1, 1, 2, 1]

代码

public class AlgoCasts {

  // Time: O(k), Space: O(1)
  private int numberOfOne(int n) {
    int count = 0;
    while (n != 0) {
      ++count;
      n &= (n - 1);
    }
    return count;
  }

  // Time: O(n*k), Space: O(1)
  public int[] countBits(int n) {
    int[] d = new int[n+1];
    for (int i = 0; i <= n; ++i)
      d[i] = numberOfOne(i);
    return d;
  }

  // Time: O(n), Space: O(1)
  public int[] countBitsOn(int n) {
    int[] d = new int[n+1];
    for (int i = 1; i <= n; ++i)
      d[i] = d[i & (i-1)] + 1;
    return d;
  }

}