338.Counting Bits
===

###### tags: `Easy` `DP` `Bit Manipulation`

[338. Counting Bits](https://leetcode.com/problems/counting-bits/)

### 題目描述

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` <= 10^5^

**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++)?

### 解答

#### C#

public class Solution {
    public int[] CountBits(int n) {
        int[] ans = new int[n + 1]; 
        if (n == 0) return ans;
        
        ans[1] = 1;
        for (int threshold = 2; threshold <= n; threshold <<= 1) {
            ans[threshold] = 1;
            for (int i = threshold + 1; i <= n && i < (threshold << 1); i++) {
                ans[i] = 1 + ans[i - threshold];
            }
        }

        return ans;
    }
}

public class Solution {
    public int[] CountBits(int n) {
        int[] ans = new int[n + 1]; 
        if (n == 0) return ans;

        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }

        return ans;
    }
}

### Reference
>[name=Jim][time=Sep 1, 2023]

#### Python

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        bound = 1
        k = 0
        for i in range(1, n + 1):
            ans[i] = ans[k] + 1
            k += 1
            if k == bound:
                k = 0
                bound *= 2
        return ans

> [name=Yen-Chi Chen][time=Fri, Sep 1, 2023]

#### C++

class Solution {
public:
    vector<int> countBits(int n) {
        ios_base::sync_with_stdio(0); cin.tie(0);
        
        vector<int> ans;
        for (int num = 0; num <= n; num ++) {
            ans.push_back(parallelBitCount(num));
        }
        return ans;
    }

    int parallelBitCount(uint32_t n) {
        n = ( n & 0x55555555 ) + ( ( n >> 1 ) & 0x55555555 );
        n = ( n & 0x33333333 ) + ( ( n >> 2 ) & 0x33333333 );
        return ((( n + (n >> 4) ) & 0x0f0f0f0f ) * 0x01010101) >> 24;
    }
};

> [name=Jerry Wu][time=Fir, Sep 1, 2023]

[回到題目列表](https://marsgoat.github.io/XNnote/coding/leetcodeEveryDay.html)