subject

Give you an integer  n , about  0 <= i <= n  Each of the  i , Calculate its binary representation  1  The number of  , Returns a length of  n + 1  Array of  ans  As the answer .

Example

Ideas

Direct traversal
Traversing integers n, Position each element with itself -1, Until 0, There are as many as the number of times 1

Dynamic programming
utilize 0001 0010 0100 1000 Dynamically update the data of each segment

Code

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int countBit(int x)
{
    int count = 0;
    while(x)
    {
        x &= (x-1);
        count++;
    }
    return count;
}
int* countBits(int n, int* returnSize){
    int * bit_nums = malloc(sizeof(int) * (n + 1));
    *returnSize = n + 1;
    for(int i = 0; i <= n; i++)
    {
        bit_nums[i] = countBit(i);
    }
    return bit_nums;
}

Dynamic programming  

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

/*
*int* countBits(int n, int* returnSize)
int* countBits： seek 0-n In the integer of bit position 1 The number of 
int n： Integers 
int* returnSize： Length of return value 
 Return value ：bit Number of bits to go   Array 
*/
int* countBits(int n, int* returnSize) {
    int* bits = malloc(sizeof(int) * (n + 1));
    *returnSize = n + 1;
    bits[0] = 0;
    int highBit = 0;
    for (int i = 1; i <= n; i++) {
        if ((i & (i - 1)) == 0) {
            highBit = i;
        }
        bits[i] = bits[i - highBit] + 1;
    }
    return bits;
}

Time and space complexity