编程之美 2.1 求二进制数中1的个数

本文主要是介绍编程之美 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的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---