Tencent interview: can you find the number of 1 in binary?

Hello everyone , I'm brother Tao .

today , Let's look at a Tencent interview question ： It is known that n Is a non negative integer , In the binary system 1 The number of , The efficiency of the algorithm is required to be as high as possible .

What exactly does this topic mean ？ We assume that n = 20, Then its binary is ：10100, So binary is 1 The number of is 2 individual .

The problem seems extremely simple , But finding efficient algorithms is not easy . Next , Let's look at the specific solution step by step , And do extended exercises .

                                                          Night view of Tencent Binhai building

Routine solution

We can find out directly n The binary value of , Then count the value as 1 Bit , In this way, the functions in the topic can be realized , The procedure is as follows ：

#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; //  The result is 2
   return 0;
}

  The result is 2, The answer right . however , This is to traverse every bit of binary , The efficiency is not high , Unable to pass the interview of Tencent .

Shift solution

Each bit of binary can be associated with 1 Operation and operation , It also traverses binary values one by one , The answer right , But I can't pass the Tencent interview .

#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; //  The result is 2
   return 0;
}

The recursive method

If not necessary , Please don't use recursive algorithm in the interview , This is especially true in practical work . The following answer is correct , But I can't pass the Tencent interview .

#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; //  The result is 2
   return 0;
}

in addition , Some friends may question , Why is the recursive relation like this ？ Don't worry , Keep looking down and you will understand .

The optimal solution

We set up n = 20, You can work out n - 1 Value , Please pay attention to n The last bit of binary 1 And behind it 0, This string of numbers must be 100... In the form of , that n - 1 The value of must be 00...1 In the form of .

When executed n & (n - 1) when , Obviously, you can see , The result is the elimination of n The last one in the class 1 Value , The rest of the bits remain unchanged , This is a very important feature . Look at the picture below , You'll see ：

( explain , There's something wrong with this picture ,n-1 Should be 10011, But it doesn't affect the results )

remember f(n) by n Binary is 1 The number of , It's easy to get ：f(n) = f(n & (n - 1)) + 1, therefore , The corresponding procedure is as follows ：

#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; //  The result is 2
   return 0;
}

The result is 2, Absolutely right , And avoid bit by bit operation , It's a very efficient algorithm , You can pass the interview of Tencent .

Extended exercises

Next , Let's look at the extended exercises , Please judge whether a positive integer is 2 Omega to an integer power , Let's take a direct look at the following procedure ：

#include<iostream>
using namespace std;
 
bool bestSolution(int n) 
{
  if (n == 0)
  {
    return false;
  }

  if ((n & (n - 1)) == 0) //  Indicates that there is only one... In the binary 1
  {
    return true;
  }
    
  return false;
}

int main()
{
  for(int n = 0; n < 100; n++)
  {
    if (bestSolution(n))
    {
      cout << n << endl;
    }
  }

    return 0;
}

The result is ：

1

2

4

8

16

32

64

well ,bestSolution The solution is very clever , Must understand and master . Some friends may want to say ： Who wants this method at the scene ？

you 're right , Only when you are well prepared can you think of , The questions to brush , Still brush , Otherwise, the interview site is basically confused . I wish you all a smooth journey through the written examination and interview .