Total Number of Set Bits in all numbers from 1 to n


Q. We have to find the total number of set bits in all numbers from 1 to n

Approach 1 (Brute Force)

We could iterate over all the numbers from 1 to n and count the number of set bits in each number using __builtin_popcount(i) for each i from 1 to n. The time complexity is O (n log n) since we iterate over n numbers and each iteration requires log n time (because the time complexity of __builtin_popcount is log n). Note that there are other similar methods to __builtin_popcount which do the same function in O (log n).

Code In C++ –

Time Complexity = O (n log n)


Approach 2 (Dynamic Programming)

Let dp[i] denote the number of set bits in the ith number. We will calculate dp[i] in O (1) and thus get an overall time complexity of O(n).

Case 1 (n is even): -

Observe that if n is even then the number of set bits in n is the same as the number of set bits in n/2. For example, if n = 6 = 110 (in base 2) then on dividing by 2 we get n = 11 (in base 2). As a result, only the last non-zero bit is removed and the number of set bits does not change. Thus, in this case dp[n] = dp[n/2].

Case 2 (n is odd): -

If n is odd then the last bit will be set. Thus, we can subtract 1 from n and all the other bits will be the same except the last bit which will be 0. For example, if n = 101001(in base 2) and we subtract 1 then we are left with n = 101000(in base 2) . As a result, we go back to case 1 and our answer is dp[n] = 1+dp[n-1] because there is 1 more set bit in this number than in n-1 and the rest of the bits remain the same.

Thus, we can easily compute the values by simply iterating from 1 to n with the base case that dp[0] = 0.

Now we just need to sum up all the dp values

Code In C++ –

Time Complexity = O(n)


It is highly recommended to solve below problems, they are handpicked by Programmers Army:

Practice Problems :-

https://www.hackerearth.com/practice/basic-programming/bit-manipulation/basics-of-bit-manipulation/practice-problems/algorithm/count-the-bits/

https://leetcode.com/problems/counting-bits/


This article is contributed by Adarsh Agrawal

So that’s it for this article we will be coming up with our next article on further topics of Algorithms very soon till then keep learning, keep coding, keep reading and keep improving !!

Happy Coding

By Programmers Army 😊