大家好，我是涛哥。

今天，我们来看一道腾讯面试题：已知n是一个非负整数，求其二进制中1的个数，要求算法效率尽可能高。

这个题目具体什么意思呢？我们假定n = 20，则其二进制为：10100，那么二进制中为1的个数是2个。

这道题看似极其简单，但要找到高效的算法并非易事。接下来，我们循序渐进地看具体解法，并做扩展练习。

                                                         腾讯滨海大厦夜景

常规解法

我们可以直接求出n的二进制值，然后数出值为1的位，这样就能实现题目中的功能，程序如下：

#include<iostream>
using namespace std;int getNumber1(int n)
{int r = 2, sum = 0;while(n) {if(1 == n % r)sum++;n /= r;}return  sum;
}int main()
{cout << getNumber1(20) << endl; // 结果为2return 0;
}

 结果为2，答案正确。但是，这是对二进制的每一位进行遍历，效率不高，无法通过腾讯的面试。

移位解法

可把二进制每一位与1进行与运算，也是逐个遍历二进制值，答案正确，但无法通过腾讯面试。

#include<iostream>
using namespace std;int getNumber2(int n)
{int sum = 0;while(n){if(1 == (n & 1)) sum++;n  >>= 1;}return  sum;
}int main()
{cout << getNumber2(20) << endl; // 结果为2return 0;
}

递归解法

若非必要，请不要在面试中用递归算法，实际工作更是如此。如下答案正确，但无法通过腾讯面试。

#include<iostream>
using namespace std;int getNumber3(int n)
{if(0 == n){return 0;}return  getNumber3(n & (n - 1)) + 1;
}int main()
{cout << getNumber3(20) << endl; // 结果为2return 0;
}

另外，有的朋友可能会疑问，为什么递归关系是这样的呢？先别着急，继续往下看你就会明白了。

最优解法

我们设 n = 20，可以算出 n - 1 的值，请关注n的二进制最后一位1及其后面的0，这一串数字必然是100...的形式，那么 n - 1 的值必然是00...1的形式。

当执行 n & (n - 1) 时，很显然可以看到，其结果就是消掉了n中的最后一位1的值，其余的位保持不变，这是一个很重要的特性。看下面这幅图，你就明白了：

(说明，这个图有点问题，n-1应该是10011，不过不影响结果)

记f(n)为n中二进制为1的个数，则容易得出：f(n) = f(n & (n - 1)) + 1，所以，对应程序如下：

#include<iostream>
using namespace std;int bestSolution(int n) 
{int sum = 0;while(n){sum++;n = n & (n - 1);}return  sum;
}int main()
{cout << bestSolution(20) << endl; // 结果为2return 0;
}

结果是2，完全正确，而且避免了逐位进行操作，是非常高效的算法，可以通过腾讯的面试。

扩展练习

接下来，我们看看扩展练习，请判断一个正整数是否为2的整数次幂，直接来看如下程序吧：

#include<iostream>
using namespace std;bool bestSolution(int n) 
{if (n == 0){return false;}if ((n & (n - 1)) == 0) // 表明二进制中只有一个1{return true;}return false;
}int main()
{for(int n = 0; n < 100; n++){if (bestSolution(n)){cout << n << endl;}}return 0;
}

结果为：

1

2

4

8

16

32

64

好的，bestSolution的解法挺巧妙，必须理解并掌握。有的朋友可能要说：现场谁想得到这种方法啊？

没错，准备充分才能想到，该刷的题，还是要刷，不然面试现场基本懵圈。祝愿大家笔试面试一路顺利。