Count complete set bits in all numbers from 1 to n | Set 2

Given a optimistic integer N, the duty is to rely the sum of the variety of set bits within the binary illustration of all of the numbers from 1 to N.

Examples:

Input: N = three
Output: four

Decimal
Binary
Set Bit Count
1
01
1
2
10
1
three
11
2

1 + 1 + 2 = four

Input: N = 16
Output: 33

Approach: Some different approaches to unravel this drawback has been mentioned right here. In this text, one other method with time complexity O(logN) has been mentioned.
Check the sample of Binary illustration of the numbers from 1 to N within the following desk:

Decimal
E
D
C
B
A
zero
zero
zero
zero
zero
zero
1
zero
zero
zero
zero
1
2
zero
zero
zero
1
zero
three
zero
zero
zero
1
1
four
zero
zero
1
zero
zero
5
zero
zero
1
zero
1
6
zero
zero
1
1
zero
7
zero
zero
1
1
1
eight
zero
1
zero
zero
zero
9
zero
1
zero
zero
1
10
zero
1
zero
1
zero
11
zero
1
zero
1
1
12
zero
1
1
zero
zero
13
zero
1
1
zero
1
14
zero
1
1
1
zero
15
zero
1
1
1
1
16
1
zero
zero
zero
zero

Notice that,

Every alternate bits in A are set.
Every 2 alternate bits in B are set.
Every four alternate bits in C are set.
Every eight alternate bits in D are set.
…..
This will carry on repeating for each energy of two.

So, we’ll iterate until the variety of bits within the quantity. And we don’t must iterate each single quantity within the vary from 1 to n.
We will carry out the next operations to get the specified consequence.

, First of all, we’ll add 1 to the quantity with a purpose to compensate zero. As the binary quantity system begins from zero. So now n = n + 1.
We will hold the observe of the variety of set bits encountered until now. And we’ll initialise it with n/2.
We will hold one variable which is an influence of two, with a purpose to hold observe of bit we’re computing.
We will iterate until the ability of two turns into larger than n.
We can get the variety of pairs of 0s and 1s within the present bit for all of the numbers by dividing n by present energy of two.
Now now we have so as to add the bits within the set bits rely. We can do that by dividing the variety of pairs of 0s and 1s by 2 which is able to give us the variety of pairs of 1s solely and after that, we’ll multiply that with the present energy of two to get the rely of ones within the teams.
Now there could also be an opportunity that we get a quantity as variety of pairs, which is someplace in the course of the group i.e. the variety of 1s are lower than the present energy of two in that exact group. So, we’ll discover modulus and add that to the rely of set bits which shall be clear with the assistance of an instance.

Example: Consider N = 14
From the desk above, there shall be 28 set bits in complete from 1 to 14.
We shall be contemplating 20 as A, 21 as B, 22 as C and 23 as D

First of all we’ll add 1 to quantity N, So now our N = 14 + 1 = 15.

Calculation for A (20 = 1)
15/2 = 7
Number of set bits in A = 7 ————> (i)
Calculation for B (2^1 = 2)
15/2 = 7 => there are 7 teams of 0s and 1s
Now, to compute variety of teams of set bits solely, now we have to divide that by 2.
So, 7/2 = three. There are three set bit teams.
And these teams will comprise set bits equal to energy of two this time, which is 2. So we’ll multiply variety of set bit teams with energy of two
=> three*2 = 6 —>(2i)
Plus
There could also be some further 1s on this as a result of 4th group shouldn’t be thought of, as this division will give us solely integer worth. So now we have so as to add that as effectively. Note: – This will occur solely when variety of teams of 0s and 1s is odd.
15%2 = 1 —>(2ii)
2i + 2ii => 6 + 1 = 7 ————>(ii)
Calculation for C (2^2 = four)
15/four = three => there are three teams of 0s and 1s
Number of set bit teams = three/2 = 1
Number of set bits in these teams = 1*four = four —> (3i)
As three is odd, now we have so as to add bits within the group which isn’t thought of
So, 15%four = three —> (3ii)
3i + 3ii = four + three = 7 ————>(iii)
Calculation for D (2^three = eight)
15/eight = 1 => there may be 1 group of 0s and 1s. Now on this case there is just one group and that too of solely zero.
Number of set bit teams = half = zero
Number of set bits in these teams = zero * eight = zero —> (4i)
As variety of teams are odd,
So, 15%eight = 7 —> (4ii)
4i + 4ii = zero + 7 = 7 ————>(iv)

At this level, our energy of two variable turns into larger than the quantity, which is 15 in our case. (energy of two = 16 and 16 > 15). So the loop will get terminated right here.
Final output = i + ii + iii + iv = 7 + 7 + 7 + 7 = 28
Number of set bits from 1 to 14 are 28.

Below is the implementation of the above method:

#embrace

utilizing namespace std;

  

int relySetBits(int n)

  

int foremost()

    int n = 14;

  

    cout << relySetBits(n);

  

    return zero;

If you want GeeksforGeeks and wish to contribute, you can even write an article utilizing contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article showing on the GeeksforGeeks foremost web page and assist different Geeks.

Please Improve this text if you happen to discover something incorrect by clicking on the “Improve Article” button under.

Article Tags :

thumb_up
Be the First to upvote.

Please write to us at contribute@geeksforgeeks.org to report any situation with the above content material.

Post navigation

Previous

first_page Decimal to Binary utilizing recursion and with out utilizing energy operator

Next

last_page Partition an array of non-negative integers into two subsets such that common of each the subsets is equal