Study Plan For Algorithms - Part42

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

def countBits(n):res = []for i in range(n + 1):res.append(countOnes(i))return resdef countOnes(x):count = 0while x > 0:x &= x - 1count += 1return count

方法二：

def countBits(n):res = [0]for i in range(1, n + 1):res.append(res[i & (i - 1)] + 1)return res

方法三：

def countBits(n):res = []for num in range(n + 1):binary = bin(num)[2:]  # 将数字转换为二进制字符串并去除前缀'0b'ones_count = sum(1 for bit in binary if bit == '1')res.append(ones_count)return res