COUNT BITS

/*
    *  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
*/
 
#include <iostream>
using namespace std;
 
inline bool isSet(long long int n,int i)
{
     long long int x = 1;
     x <<=i;
     if(x&n)
         return true;
     return false;
}
 
int countBitsEASY(long long int n)
{
    int size = sizeof(n)*8;
    int count = 0;
    for(int i=0; i<size; i++)
    {
        if(isSet(n,i))
            count++;
    }
    return count;
}
 
int countBitsMODERATE(long long int n)
{
    int size = sizeof(n) * 8;
    int count = 0;
    if(n<0)
    {
        n &= n^(1LL<<size-1);
        count = 1;
    }
    for(; n > 0; count++)
        n &= n-1;
    return count;
}
 
//found it to be Hamming weight problem on wiki.
int countBitsVERYHARD(long long int n)
{
    long long int result = (n & 0x5555555555555555LL) + (n>>1 & 0x5555555555555555LL);
    result = (result & 0x3333333333333333LL) + ((result>>2) & (0x3333333333333333LL));
    result = (result & 0x0f0f0f0f0f0f0f0fLL) + ((result>>4) & (0x0f0f0f0f0f0f0f0fLL));
    result = (result & 0x00ff00ff00ff00ffLL) + ((result>>8) & (0x00ff00ff00ff00ffLL));
    result = (result & 0x0000ffff0000ffffLL) + ((result>>16)& (0x0000ffff0000ffffLL));
    result = (result & 0x00000000ffffffffLL) + ((result>>32)& (0x00000000ffffffffLL));
    return result;
}
 
int main()
{
    long long int n = 15;
    int testCases ;
    cin>>testCases;
    for(int i=0; i<testCases; i++)
    {
        cin>>n;
        cout<<"\nEASY       : "<<countBitsEASY(n);
        cout<<"\nMODERATE   : "<<countBitsMODERATE(n);
        cout<<"\nVERY HARDS : "<<countBitsVERYHARD(n)<<endl;
    }
}