Counting set bits in a number

You are given a number; you need to create an array to fill the number of 1’s present in their binary format.

Example:

Input n = 3
Output = [0, 1, 1, 2]

Because for 0, the number of set bits is 0.
For 1, it’s binary format is 001, set bits is 1.
For 2, it’s binary format is 010, set bits is 1.
For 3, it’s binary format is 011, set bits is 2.

First we shall see if we can find any pattern

From the above image, we can see a pattern. The pattern is

arr[i] = arr[i/2] + i % 2
arr[0] = 0

arr[1] = arr[1/2] + 1 % 2
           = 0 + 1 = 1

arr[2] = arr[2/2] + 2 % 2
       = 1 + 0 = 1

arr[3] = arr[3/2] + 3 % 2
       = 1 + 1 = 2

arr[4] = arr[4/2] + 4 % 2
       = 1 + 0 = 1

So how can we do this by bit manipulation?

It can be done as below:

1. To get the mod value, as we are getting the modulo of 2, the remainder will be either 0 or 1.

Hence we can achieve it by (i & 1)

2. To divide the i value by 2, we can just right shift the value by 1. As we know that if you right shift the value by 1, then it is equivalent to divide the number by 2.

[i >> 2]

Solution in C++

#include<iostream>
#include<vector>

using namespace std;

vector<int> count_bits(int num) 
{
    vector<int> res(num + 1, 0);
    for (int i = 1; i <= num; ++i) 
    {
        res[i] = res[i >> 1] + (i & 1);
    }
    return res;
}


int main()
{
	int num = 3;

	cout<<"Output = "<<endl;

	std::vector<int> v = count_bits(num);

    for (int i = 0; i < v.size(); i++)
    {
        cout <<v[i] << " ";
    }
    cout<<endl;


}