首页 > 代码库 > 编程之美 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的时候会用到
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。