[leetcode] 338. 比特位计数(位运算+动态规划）

桃扇骨 2022-11-05 00:46 173阅读 0赞

### 目录 ###

*   *  题目描述：338. 比特位计数
     *  解题思路
     *   *  思路一：动态规划——最低设置位
         *  思路二：动态规划——移位
         *   *  复杂度分析
     *  代码实现
     *  Tips

## 题目描述：338. 比特位计数 ##

> [题目链接][Link 1]  
> [参考题解链接][Link 2]

给定一个非负整数 **num**。对于 **0 ≤ i ≤ num** 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

*  示例 1:

> 输入: 2  
> 输出: \[0,1,1\]

*  示例 2:

> 输入: 5  
> 输出: \[0,1,1,2,1,2\]

*  进阶:

1.  给出时间复杂度为 **O(n\*sizeof(integer))** 的解答非常容易。但你可以在线性时间 **O(n)** 内用一趟扫描做到吗？
2.  要求算法的空间复杂度为 **O(n)** 。
3.  不使用任何内置函数来执行此操作。

## 解题思路 ##

首先要知道，按位与运算`&`的一个性质是：对于任意整数 x，令 `x = x & (x−1)`，该运算**将 x 的二进制表示的最后一个 1 变成 0**。简单说，可以去掉最右边的一个1（如果有的话）。

### 思路一：动态规划——最低设置位 ###

定义正整数 x 的`最低设置位`为 x 的二进制表示中的最低的 1 所在位。例如，10 的二进制表示是  101 0 ( 2 ) 1010\_\{(2)\} 1010(2) ，其最低设置位为 2，对应的二进制表示是  1 0 ( 2 ) 10\_\{(2)\} 10(2) 。

令  y = x & ( x − 1 ) y=x \\&(x-1) y=x&(x−1)，则 y 为将 x 的最低设置位从 1 变成 0 之后的数，显然  0 ≤ y < x 0 \\le y<x 0≤y<x， bits \[ x \] = bits \[ y \] + 1 \\textit\{bits\}\[x\]=\\textit\{bits\}\[y\]+1 bits\[x\]=bits\[y\]\+1。因此对任意正整数 x，都有  bits \[ x \] = bits \[ x & ( x − 1 ) \] + 1 \\textit\{bits\}\[x\]=\\textit\{bits\}\[x \\&(x-1)\]+1 bits\[x\]=bits\[x&(x−1)\]\+1 。

遍历从 1 到  num \\textit\{num\} num 的每个正整数  i i i，计算  bits \\textit\{bits\} bits 的值。最终得到的数组  bits \\textit\{bits\} bits 即为答案。

### 思路二：动态规划——移位 ###

`x >> 1`会把最低位去掉，因此 x >> 1 比 x 小，同样也是在前面的数组里算过。  
如果 x 的最低位是0，则 x 中 1 的个数和 x >> 1 中 1 的个数相同；  
如果 x 的最低位是1，x 中 1 的个数是 x >> 1中 1 的个数再加 1 。

#### 复杂度分析 ####

*  时间复杂度：  
    `O(num)`。对于每个数，只需要 O(1) 的时间计算「一比特数」。
 *  空间复杂度：  
    `O(1)`。除了返回的数组以外，空间复杂度为常数。

## 代码实现 ##

(两种思路只有一行不同）

class Solution:
    
        def countBits(self, num: int) -> List[int]:
            ones = [0]
            for i in range(1, num+1):
                # ones.append(ones[i & (i-1)] + 1) # 思路一
                ones.append(ones[i >> 1] + (i & 1)) # 思路二
    
            return ones

官方题解还提供了其他几种方法，可以去了解一下。

## Tips ##

位运算有时候还蛮好用的~要记住一些小结论！

--------------------

A u t h o r : C h i e r Author: Chier Author:Chier

[Link 1]: https://leetcode-cn.com/problems/counting-bits
[Link 2]: https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/%5D%28https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/%29%20%3E