这道看似非常简单的题其实有很多奇妙的解法，看到网上一些神牛的解法实在是叹为观止！
不过我们还是按部就班的来：
1、最容易想到的方法
1 int count_one(unsigned int x) {
2 int count = 0;
3 while (x) {
4 if (x & 1 == 1) {
5 count++;
6 }
7 x >>= 1;
8 }
9 return count;
10 }
没有多少可以讲的，非常简单，不过这样做会发现，该算法时间复杂度是O(logN)的
2、为了优化上面算法，尽量做到降低时间复杂度，但是O(logN)的复杂度再降低会是什么样子呢？O(1)？那就直接建索引？但是毕竟32位整数想要建索引的话那内存耗费就太大了，所以我们先看看能不能使得复杂度将到O(m)，其中m是x中1的个数，那么怎么样才能每进行一次循环x的1的个数就减1呢？比较难想到的地方就是它了：x & (x - 1)，比如x为12，即1100b，如果进行一次x = x & (x - 1)运算则x的值为1000b。因此代码如下：
1 int count_one(unsigned int x) {
2 int count = 0;
3 while (x) {
4 count++;
5 x &= x - 1;
6 }
7 return count;
8 }
上面的代码看似和方法1中的代码相似，但是每次循环使问题减小的规模是不一样的。
3、
该方法是从网上借鉴的，确实不太容易想到，非常的巧妙，采用典型的分治思想：比如我们有一个数字11111111b，基础情况是先计算每一位的1的个数（这个步骤可以省略，类似归并排序的基础情况，对一个元素的排序是不需要排）；再归并，计算相邻两位的1的个数，即第0位和第1位的1的个数为2个，第2位和第3位的1的个数为2个，...，第6位和第7位的1的个数为2个；这样得到10 10 10 10b，然后再归并，计算第0,1,2,3位的1的个数，计算第4,5,6,7位的1的个数，得到0100 0100b；然后再归并得到第0,1,2,3,4,5,6,7位的1的个数为1000b。上面分析的是8位二进制情况，对于32位二进制，同理，只需要继续归并即可，代码如下：
1 int count_one(unsigned int x) {
2 x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
3 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
4 x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
5 x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
6 x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
7 return x;
8 }
对于方法3，时间复杂度可以认为是O(1)的，不过真实速度和方法2的pk我确实没有比较过，因为我们要求的数的位数总不会太大，所以时间差距不会太多，甚至在这种小规模位数的情况下会出现相反结果，不过方法3的思想实在是巧妙，如果没有对分治算法的透彻理解，是很难想到用分治去解决该题的
领教了！
posted on 2012-09-04 10:52
myjfm 阅读(611)
评论(0) 编辑 收藏 引用 所属分类:
算法基础