leetcode338：比特位计数（counting-bits）

[carloscn]

问题描述

给你一个整数 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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/counting-bits

[carloscn]

问题分析：

生成匹配大小的数组，对每个数组计数即可：

static int32_t counting_bits(size_t in, int32_t **out)
{
    int32_t ret = 0;
    size_t i = 0;

    UTILS_CHECK_LEN(in);
    UTILS_CHECK_PTR(out);

    *out = (int32_t *)malloc(sizeof(int32_t) * (in + 1));
    UTILS_CHECK_PTR(*out);

    for (i = 0; i < in + 1; i ++) {
        int32_t count = 0;
        int32_t e = i;
        do {
            count += e & 1;
            e >>= 1;
        } while (e);
        (*out)[i] = count;
    }

finish:
    return ret;
}

[carloscn]

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/array/29_counting-bits_338.c

result: