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

来源丨经授权转自 涛歌依旧（ID：ai_taogeyijiu_2021）

作者丨涛歌依旧

大家好，我是涛哥。

今天，我们来看一道腾讯面试题：已知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的值，其余的位保持不变，这是一个很重要的特性。看下面这幅图，你就明白了：

记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;}

结果为：

1

2

4

8

16

32

64

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

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

点分享

点点赞

点在看