前n个数字二进制中1的个数

183 阅读 0 评论 121 点赞

我是靠谱客的博主伶俐日记本，这篇文章主要介绍前n个数字二进制中1的个数，现在分享给大家，希望可以做个参考。

题目：给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
首先需要知道怎么判断一个数字二进制中1的个数.
利用性质n&(n-1)可以将n的最低位的1置0
经过多少次该运算可以把n置0，就表示n中有多少个1

 int numberOfOne(int n)//寻找每个数的二进制表示中1的个数
{
int ans=0;
while(n)
{
n&=(n-1);	//利用性质n&(n-1)
ans++;
//循环次数
}
return ans;
}
int* countBits(int n, int* returnSize){
*returnSize = 0;
int *ans = malloc(sizeof(int)*(n+1));
for(int i=0;i<=n;i++)	//遍历每一个数
{
ans[(*returnSize)++] = numberOfOne(i);
}
return ans;
}