题目描述

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

问题分析

因为每一个数在计算机内存部的存储方式都是二进制的存储方式，所以我们只需要每一次将数字使用右移操作符进行移一位，然后查看这一位是否为1即可，是1就统计上，这种方法查看一个数字的每一位需要$lo{g}_{2}n$的时间复杂度，共有n+1个数字，所以时间复杂度为$O(n)=nlo{g}_{2}n$.
这是我能想到的最好的方法了。如果后面我能想到更好的方法我会更新出来的。

代码

int* countBits(int n, int* returnSize) {int *ans = (int *)malloc(sizeof(int)*(n+1));for(int i=0; i<=n; i++){int num = i;int count = 0;while(num!=0){if(num%2==1){count += 1;}num = num>>1;}ans[i] = count;}*returnSize = n+1;return ans;
}

提交结果截图