Count the number of bits that are set to 1, in a 64-bit signed integer.

CountBits

Given a 64-bit signed number, count the number of bits that are set to 1. Bonus: In
addition to the obvious approach, continue exploring till you find other efficient
approaches.

Example Inputs:
0
-1
14


Outputs (respectively):
0
64
3


Solution Guidance:
Let k be the bit width (maximum number of bits) of the primitive.
Easy: O(k) time.
Moderate: O(number of bits whose value is 1) time.
Very Hard: O(log(k)) time

Note:- I have explored till now 4 methods which are below, in a form of program just have a  look, pretty easy to understand.

1:- Count Bit with Complexity K..
 
#include <iostream>
 
using namespace std;
 
int CountBit(long long int n)
{
  int count=0;
 int temp=1;
 long long int k=1;
 while(n)
 {
     if(n&k)
     {count++;
      n=n^k;
     }
     k=k<<temp;
}
return count;
}
 
int main()
{  long long int N=-7;
    cin>>N;
   cout <<endl<<"count bit is "<<CountBit(N) << endl; 
   
   return 0;
}

2:- Count Bit with Complexity as equal to number of 1 bits out of a.

#include <iostream>
 
using namespace std;
 
int CountBit(long long int n)
{
  int count=0;
 int temp=1;
 long long int k=1;
 while(n)
 {
  count++;
  n=n&n-1;   
}
return count;
}
 
int main()
{  long long int N=127;
   cin>>N;
   cout <<endl<<"count bit is "<<CountBit(N) << endl; 
   
   return 0;
}

3:-by taking mode 2....

#include <iostream>
 
using namespace std;
 
 
int CountBit(long long int n)
{
 int Table[]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
 int count=0;
 int temp=4;
 long long int k=8;
 long long int a=1;
 a=a<<63;
 if(n&a)
 {a=~a;
  n=n&a;
  count++;
 }
 
 while(n)
 {
  count=count+Table[n%k];
 
  n=n/k;
}
return count;
}
 
int main()
{  long long int N=-7;
   cin>>N;
   cout <<endl<<"count bit is "<<CountBit(N) << endl; 
   
   return 0;
}
 

4:-Count Bit with quadratic(n/4) complexity.... using a little extra space.

#include <iostream>
 
using namespace std;
 
 
int CountBit(long long int n)
{
 int Table[]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
 int count=0;
 int temp=4;
 long long int k=8;
 long long int a=1;
 a=a<<63;
 if(n&a)
 {a=~a;
  n=n&a;
  count++;
 }
 
 while(n)
 {
  count=count+Table[n%k];
 
  n=n/k;
}
return count;
}
 
int main()
{  long long int N=-1;
   cin>>N;
   cout <<endl<<"count bit is "<<CountBit(N) << endl; 
   
   return 0;
}

//Happy coding

//If you do know other better approaches feel free to acknowledge.