本文主要是介绍编程之美 2.1 求二进制数中1的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
假设有数n
以前用除二取余法 复杂度logn 不多说
有一个logv的方法 v为1的个数 复杂度比logn小
int Count(int x)
{int ans = 0;while(x){x &= (x-1);ans++;}return ans;
}
这里用到了位运算 x&(x-1)每次去掉一个1 举个例子
100010001000&(100010001000-1) = 100010000000
100010000000&(100010000000-1) = 100000000000
100000000000&(100000000000-1) = 000000000000
总共3次 每次去掉一个1
然后补充一下
for(int i = s; i; i = (i-1)&s)这个循环枚举了所有s的子集 例如 S = 10101
10101 -> 10100 -> 10001 -> 10000 -> 00101 ->00100 ->00001 -> 00000
这样枚举了所有S的子集
这个在状态压缩DP的时候会用到
这篇关于编程之美 2.1 求二进制数中1的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
