Last Updated: 28 Jan, 2021

Count Set Bits

Hard

Asked in companies

Solve now

Problem statement

You are given a positive integer ‘N’. Your task is to find the total number of ‘1’ in the binary representation of all the numbers from 1 to N.

Since the count of ‘1’ can be huge, you are required to return it modulo 1e9+7.

Note:

Do not print anything, just return the number of set bits in the binary representation of all integers between 1 and ‘N’.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. 
Then the next ‘T’ lines represent the ‘T’ test cases.

The first line of each test case contains a single integer ‘N’.

Output Format

For each test case, return an integer that is equal to the count of set bits in all integers from 1 to n modulo 1e9+7.

Output for each test case will be printed in a new line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 10^9

Time limit: 1 second

Solve now

Approaches

01 Approach

The key idea is to count the number of set bits in each number from 1 to n and return the sum of all set bits.

The algorithm will be -

For each i from 1 to N -
- We find the number of set bits for each i.
- This can be done using a built-in function (for eg builtin_popcount in c++) or by simply using a loop and left shifting the number and finding if the last place is set or not.
Finally we store the count of set bits in a variable called ‘count’ , take its mod and return it.

Solve now

02 Approach

Let us take the following example:

Let N = 7;

Then ,

0 = 0000

1 = 0001

2 = 0010

3 = 0011

4 = 0100

5 = 0101

6= 0110

7 = 0111

Observe the last the bits get flipped after (2^0 = 1)

The second last bit gets flipped after( 2^1=2)

The third last bit gets flipped after (2^2=4)

We can use the above observation to get the result. The algorithm will be:

We add 1 to the given number to ensure correctness as the binary number system starts from 0. Thus, we increment n by 1.
We need to keep the count of set bits. Let us do that in a ‘count’ variable.
We initialize count with N / 2 as we know that there will be N / 2 odd numbers between 1 to N and the last bit of odd numbers is set.
Now, for each, i starting from 0, till 2 ^ i becomes greater than n we do-
- We will get the pairs of numbers of 1s and zeros ‘totalpairs’ for the current bit by dividing ‘N’ by 2 ^ i.
- Now, multiplying ‘totalpairs / 2’ with the current power of 2 will give us the number of 1s in that position. Thus we add, (‘totalpairs / 2’ * current power of 2) to count.
- If ‘totalpairs’ is odd we necessarily miss a few ones, so we add ‘N’ modulo current power of 2 to ‘count’.
Don't forget to take mod!.
Finally, we return count.

Solve now