力扣算法：比特位计数 _二进制

力扣算法：比特位计数备注
一、比特位计数 1、问题
2、思路
思路一：
计算一个“非负整数n的二进制数”中所包含1的数目：建立一个循环，计算 0 ≤ n ≤ num中，每个数字n当中1的数目。
举例，计算一个“非负整数n的二进制数”中所包含1的数目：
思路二：
循环遍历0 ≤ i ≤ num 范围中的每个数字 i 。将每个 i 先转化为二进制数，然后将二进制数转化为字符串，最后统计字符串中的“1”的数目返回。3、代码
#coding:utf-8from typing import Listclass Solution:def countBits1(self, n1: int) -> List[int]:def count_ones(i):count = 0while i:i = i&(i-1)count += 1return countreturn [count_ones(i) for i in range(n1+1)]def countBits2(self, n2: int) -> List[int]:return [str(bin(i)).count("1") for i in range(n2+1)]if __name__ == "__main__":sl = Solution()print(sl.countBits1(5))print(sl.countBits2(5))
4、时间与空间复杂度
思路一：

文章插图
时间复杂度：O(nlogn)
对从 0 到 n 的每个整数计算「一比特数」，对每个整数计算「一比特数」的时间都不会超过 O(log?n)
空间复杂度：O(1)
思路二：
时间复杂度：O(n)
对从 0 到 n 的每个整数计算二进制中包含1的数目。
空间复杂度：O(1)
【力扣算法：比特位计数】备注