一、题目

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

0 <= n <= 105

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

二、题解

class Solution {
public:int hammingWeight(int n) {n = (n & 0x55555555) + ((n >> 1) & 0x55555555);n = (n & 0x33333333) + ((n >> 2) & 0x33333333);n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);return n;}vector<int> countBits(int n) {vector<int> res(n+1,0);for(int i = 0;i <= n;i++){res[i] = hammingWeight(i);}return res;}
};