#include<stdio.h> /* 求num 二进制中1 的个数,复杂度为o(count) , num&(num-1) 每次消除右起第一个1 考虑 num=1110 num-1=1101 num&(num-1)=1100 */ int numCount(int num) { int count = 0; while(num) { num&=(num-1); // 将num 右起第一个 1 给消除掉 count++; } return count; } int main() { int num; while(scanf("%d",&num)!=EOF) printf("%d\n",numCount(num)); return 0; }
扩展问题2
#include<stdio.h> /* 给定两个整数A,B ,那么把A变成B需要改变多少位(bit) ? 也是求A B 的二进制的形式有多少不同的 那么将A ,B 异或之后得到C ,求C的二进制中有多少个1(相同的0) */ int numChange(int A,int B) { int C = A^B; int count=0; while(C) { C &= (C-1) ; count++; } return count; } int main() { int A ,B; while(scanf("%d %d",&A,&B)!=EOF) { printf("%d\n",numChange(A,B)); } return 0; }