class Solution {
public:
vector<int> countBits(int n) {
}
};
338. 比特位计数
给你一个整数 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 <= 105
进阶：
O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？__builtin_popcount ）相似题目
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 4.6 MB, 提交时间: 2021-06-09 16:04:40
func countBits(n int) []int {
ans := make([]int, n+1)
for i := 1; i <= n; i++ {
ans[i] = ans[i>>1] + i&1
}
return ans
}
golang 解法, 执行用时: 8 ms, 内存消耗: 4.6 MB, 提交时间: 2021-06-09 15:59:26
func countBits(n int) []int {
ans := make([]int, n+1)
for i := 0; i <= n; i++ {
ans[i] = bitN(i)
}
return ans
}
func bitN(n int) int {
ans := 0
for n != 0 {
n &= n - 1
ans++
}
return ans
}