在这里给出求一个数2进制下1的个数的方法。
int count(int n)
{
/*unsigned int c = 0;
for (c = 0; n; ++c)
{
n &= (n - 1);
}
return c;*/
int ans = 0;
while (n) {
n -= n & (-n);
ans++;
}
return ans;
}
最后一种可应用DP,dp[i]:表示i的二进制有多少个1。状态转移方程:dp[i]=dp[i>>1]+i%2。
for(int i=1; i<=10000000; i++) {
s[i]=s[i>>1]+i%2;
}