2022-05-26.md

每日一题 - 比特位计数

信息卡片

• 时间：2022-05-26
• 题目链接：https://leetcode.com/problems/counting-bits/
• tag：位运算 动态规则

题目描述

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

• 0 <= n <= 10^5

进阶：

• 很容易就能实现时间复杂度为 O(nlogn) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
• 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount）

思路分析

1. x = x & (x - 1) 清除最低位的 1

   21 & 20 =
   0001 0101 &
   0001 0100 =
   0001 0100 = 20
   
   20 & 19 =
   0001 0100 &
   0001 0011 =
   0001 0000 = 16
   
   16 & 15 =
   0001 0000 &
   0000 1111 =
   0000 0000 = 0
   
   // 0 -> 16 -> 20 -> 21
   

   经过 3 次运算，与 21 二进制表达中 1 的个数 3 个一致

2. 统计后面数1的个数，可以从前面已知数1的个数 + 1 → 1

3. 整数分奇数、偶数 → 2

   • 奇数：奇数一定比前一个偶数多 1

     4 = 100
     5 = 101
     

   • 偶数：1 的个数与 该数/2 以后一样多

     8 = 1000
     4 = 100
     2 = 10
     

参考答案

1. 位运算 $O(n)$

时间复杂度：$O(1)$

function countBits(n) {
  const bits = new Array(n + 1).fill(0)
  for (let i = 1; i <= n; i++) {
    bits[i] = bits[i & (i - 1)] + 1
  }
  return bits
}

2. 奇偶性 $O(n)$

时间复杂度：$O(1)$

function countBits(n) {
  let bits = new Array(n + 1)
  bits[0] = 0
  for (let i = 1; i <= n; i++) {
    // 判断奇偶：i & 1 === 1
    //  - 奇：前一个数 bits[i - 1] 加 1
    //  - 偶：i >> 1 （除以2）
    bits[i] = ((i & 1) === 1 ? bits[i - 1] + 1 : bits[i >> 1])
  }
  return bits
}