Count set bits in an integer

Problem: Write an efficient program to count number of 1s in binary representation of an integer.

For example:

Input: n = 5
Output: 2
Binary representation of 5 is (101). We see it has 2 set bits.

Input: n = 13
Output: 3
Binary representation of 13 is (1101). We see it has 3 set bits.

Method 1: Simple Method is to loop through all bits in the integer and check if a bit is set. If it is then increment the set bit count.

#include<bits/stdc++.h>
using namespace std;

/* function to get no of set bits in number */
int countSetBits(int n)
{
    int count = 0;
    while(n)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

/* driver function */
int main()
{
    int n = 10;

    cout<<countSetBits(n)<<"\n";

    return 0;
}

Output:

2

Time Complexity: (-)(logn) (Theta of logn)

Method 2: We can count bits in O(1) time using lookup table.

#include<bits/stdc++.h>
using namespace std;

/* function to get no of set bits in number */
int countSetBits(int n)
{
    int count = 0;
    while(n)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

/* driver function */
int main()
{
    int n = 10;

    cout<<countSetBits(n)<<"\n";

    return 0;
}

Output:

2
3

Time Complexity: O(1)

Note:  In GCC, we can directly count set bits using __builtin_popcount().

---

References:

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable