腾讯面试：你会求二进制中1的个数吗？- C

大家好，我是涛哥。

今天，我们来看一道腾讯面试题：已知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; // 结果为2
   return 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; // 结果为2
   return 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; // 结果为2
   return 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; // 结果为2
   return 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;
}