1 #include <iostream>
 2 using namespace std;
 3 //最简单的思路，除2有余数
 4 int fun1(unsigned int a)
 5 {
 6     int count;
 7     count = 0;
 8     while (a)
 9     {
10         if (a % 2)
11             count++;
12         a /= 2;
13     }
14     return count;
15 }
16 //用位操作更快，但是时间复杂度仍为二进制的长度
17 int fun2(unsigned int a)
18 {
19     int count;
20     count = 0;
21     while (a)
22     {
23         //if (a & 1)
24             //count++;
25         count += a & 1;
26         a = a>>1;
27     }
28     return count;
29 }
30 //O(2)直接给答案，最快，但是空间复杂度会比较高
31 int fun3(unsigned int a)
32 {
33     int count;
34     count = 0;
35     int result[20] = {0, 1, 1, 2,
36                       1, 2, 2, 3,
37                       1, 2, 2, 3,
38                       2, 3, 3, 4};
39     while (a)
40     {
41         count += result[a & 15];
42         a = a >> 4;
43     }
44     return count;
45 }
46 //这方法想不起来了，时间复杂度跟二进制中1的个数有关，比前二种方法高效，相比第三种方法，没有用到多余的空间
47 int fun4(unsigned int a)
48 {
49     int count;
50     count = 0;
51     while (a)
52     {
53         a &= (a - 1);
54         count ++;
55     }
56     return count;
57 }
58 int main()
59 {
60     unsigned int a, b;
61     a = 11;
62     b = 63;
63     //测试
64     cout<<fun1(a)<<endl;
65     cout<<fun2(a)<<endl;
66     cout<<fun3(a)<<endl;
67     cout<<fun4(a)<<endl;
68 
69     cout<<fun1(b)<<endl;
70     cout<<fun2(b)<<endl;
71     cout<<fun3(b)<<endl;
72     cout<<fun4(b)<<endl;
73     system("pause");
74     return 0;
75 }