比特位计数

Tips

题目类型: 位运算, 动态规划

相关题目:

• 191. 位 1 的个数
• 231. 2 的幂

题目

给定一个非负整数 n, 请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数, 并输出一个数组.

示例

输入: n = 5

输出: [0, 1, 1, 2, 1, 2]

解释:

0 --> 0

1 --> 1

2 --> 10

3 --> 11

4 --> 100

5 --> 101

题解

Brian Kernighan 算法

Tips

一般看到二进制统计 1 的个数先想到 Brian Kernighan 算法, 也就是 n & (n - 1). 关于使用 n & (n - 1), 这里不再赘述, 可访问位运算的一些技巧.

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const bits = new Array(n).fill(0)

  for (let i = 0; i <= n; i += 1) {
    bits[i] = computeZero(i)
  }

  return bits
}

var computeZero = function (n) {
  let count = 0

  // 通过  n & (n - 1) 将 n 逐步抹零, 次数就是 1 的个数
  while (n > 0) {
    n = n & (n - 1)
    count += 1
  }

  return count
}

复杂度分析

时间复杂度: O(nlogn), 一趟循环是 n, 计算从 0 到 n 的每个整数的一比特数的时间都不会超过 O(logn), 整体就是 O(nlogn).

空间复杂度: O(1), 除了返回的数组以外, 空间复杂度为常数.

动态规划

Tips

要求 O(n) 复杂度又是输出方案的题, 通常就是递推的 DP 题.

0 --> 0

1 --> 1

2 --> 10 # 2 抹掉最后一位, 二进制就是 1, 也就是 1, 2 二进制 1 的个数等于 1 二进制 1 的个数

3 --> 11 # 3 抹掉最后一位, 二进制就是 1, 也就是 1, 3 二进制 1 的个数等于 1 二进制 1 的个数 + 1

4 --> 100 # 4 抹掉最后一位, 二进制就是 10, 也就是 2, 4 二进制 1 的个数等于 2 二进制 1 的个数

5 --> 101 # 5 抹掉最后一位, 二进制就是 10, 也就是 2, 5 二进制 1 的个数等于 2 二进制 1 的个数 + 1

6 --> 110 # 6 抹掉最后一位, 二进制就是 11, 也就是 3, 6 二进制 1 的个数等于 3 二进制 1 的个数

7 --> 111 # 7 抹掉最后一位, 二进制就是 11, 也就是 3, 7 二进制 1 的个数等于 3 二进制 1 的个数 + 1

通过上面的规律我们可以看出状态转移方程:

• 对于 n 为奇数, 有 bits[n] = bits[n >> 1] + 1
• 对于 n 为偶数, 有 bits[n] = bits[n >> 1]

两者合起来就有:

bits[n] = bits[n >> 1] + (n % 2), 当然 n % 2 更骚一点, 可以写成 n & 1.

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const bits = new Array(n + 1).fill(0)

  for (let i = 1; i <= n; i++) {
    bits[i] = bits[i >> 1] + (i & 1)
  }

  return bits
}

复杂度分析

时间复杂度: O(n), 仅仅一趟循环.

空间复杂度: O(1), 除了返回的数组以外, 空间复杂度为常数.