Count total set bits

Problem Link

Problem Statement

Given a positive integer n, return the total number of set bits (1s) in the binary representations of all numbers from 1 to n.

Examples

Example 1:

Input: n = 3
Output: 4
Explanation:
1 -> 01 → 1 set bit  
2 -> 10 → 1 set bit  
3 -> 11 → 2 set bits  
Total = 1 + 1 + 2 = 4

Example 2:

Input: n = 6
Output: 9
Explanation:
1 → 1, 2 → 1, 3 → 2, 4 → 1, 5 → 2, 6 → 2  
Total = 9

Constraints

0 <= n <= 10⁶

Intuition

A brute-force method would iterate over every number from 1 to n and count the set bits one-by-one. However, that approach would be O(n log n), which is too slow for large inputs.

The optimized solution uses pattern-based counting by observing how set bits are distributed across each bit position from LSB to MSB over the full range.

Approach: Pattern-based Bit Count per Position

Let’s understand how bits flip across numbers:
- For bit position i, the pattern of 0s and 1s repeats every 2^i numbers.
- In each such block, half the numbers have the i-th bit set.
Iterate through each bit position up to the MSB of n:
- For bit i (represented by x = 2^i):
  - q = n / x → Number of full blocks of size x
  - Each full block contributes x / 2 set bits
  - Total from full blocks = q * (x / 2)
  - rem = n % x → Remaining numbers not completing the block
  - If rem >= x / 2, then (rem - x / 2) more numbers have this bit set
- Add all contributions to the total count.
n is incremented at the start because this pattern works from 0 to n-1. So to include n, we use n + 1.

Java Code

class Solution{
    
    public static int countSetBits(int n){
        n += 1;
        int cnt = 0;

        for (int x = 2; x / 2 < n; x = x * 2) {
            int q = n / x;
            int fg = x / 2;
            cnt += q * fg;

            int rem = n % x;
            if (rem > fg) {
                cnt += rem - fg;
            }
        }

        return cnt;
    }
}

Time and Space Complexity

Metric	Value
Time Complexity	O(log n)
Space Complexity	O(1)
Explanation	Loop runs log(n) times (each time x doubles), and no extra space is used

Dry Run

Input: `n = 6`

Increment n → n = 7
Bit position x = 2:
- q = 7 / 2 = 3, fg = 1 → cnt = 3
- rem = 7 % 2 = 1 → > 1? no → skip
x = 4:
- q = 7 / 4 = 1, fg = 2 → cnt += 2 → total = 5
- rem = 7 % 4 = 3 → rem > 2 → cnt += 1 → total = 6
x = 8:
- q = 7 / 8 = 0, fg = 4 → cnt += 0
- rem = 7 % 8 = 7 → rem > 4 → cnt += 3 → total = 9

Output: 9

Conclusion

This bitwise pattern-based solution is a powerful optimization over the brute-force approach and achieves logarithmic time performance.

This technique is commonly used in problems involving cumulative set bit counts and is a frequent interview topic to test understanding of:

Bit patterns
Powers of 2
Efficient iteration over bit positions