Count total set bits in all numbers from 1 to n

Problem Statement

Given a positive integer N, count the total number of set bits (1s) in the binary representation of all numbers from 1 to N.

Example:

Noob-Friendly Explanation

Imagine you write down all numbers from 1 to N in binary on a whiteboard. Now you count every single "1" written on the board. That's it!

For N = 5, the board looks like:

Total 1s on the board = 7

The brute force counts each number's bits individually. The optimal approach uses a clever mathematical pattern to skip counting individual numbers.

Approach 1: Brute Force

Intuition

For each number from 1 to N, count its set bits using Brian Kernighan's algorithm. Sum them all up.

Algorithm

1. For each number i from 1 to N
2. Count set bits of i using n & (n-1) trick
3. Add to total

class Solution {
    private static int countBits(int n) {
        int count = 0;
        while (n > 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }

    public static int countTotalSetBits(int n) {
        int total = 0;
        for (int i = 1; i <= n; i++) {
            total += countBits(i);
        }
        return total;
    }

    public static void main(String[] args) {
        System.out.println(countTotalSetBits(5));  // 7
        System.out.println(countTotalSetBits(3));  // 4
        System.out.println(countTotalSetBits(10)); // 17
    }
}

Complexity Analysis

• Time Complexity: O(N * log N) — For each of N numbers, counting bits takes O(log N)
• Space Complexity: O(1) — Only using counters

Approach 2: Optimal (Bit Position Pattern)

Intuition

Instead of counting bits for each number individually, we observe a pattern:

• For numbers 0 to 2^k - 1, the total set bits = k * 2^(k-1)
• For N, find the highest power of 2 ≤ N, say 2^a. Then:
  • Numbers 0 to 2^a - 1 contribute a * 2^(a-1) set bits
  • The MSB (bit at position a) is set for numbers 2^a to N, that's (N - 2^a + 1) numbers
  • Recursively count for the remaining numbers (N - 2^a)

Algorithm

1. If n == 0, return 0
2. Find the highest bit position a such that 2^a ≤ n
3. Count bits from 1 to 2^a - 1: a * 2^(a-1)
4. Count the MSB contribution: n - 2^a + 1
5. Recursively count for numbers 1 to (n - 2^a)

class Solution {
    public static int countTotalSetBits(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;

        // Find highest bit position a where 2^a <= n
        int a = 0;
        while ((1 << (a + 1)) <= n) {
            a++;
        }

        // Total set bits in numbers from 0 to 2^a - 1
        // Each bit position contributes 2^(a-1) set bits, and there are 'a' positions
        int bitsUpToPowerOf2 = a * (1 << (a - 1));

        // Numbers from 2^a to n have MSB set
        // Count of such numbers = n - 2^a + 1
        int msbContribution = n - (1 << a) + 1;

        // Remaining: count bits in numbers from 1 to (n - 2^a)
        int remaining = n - (1 << a);

        return bitsUpToPowerOf2 + msbContribution + countTotalSetBits(remaining);
    }

    public static void main(String[] args) {
        System.out.println(countTotalSetBits(5));  // 7
        System.out.println(countTotalSetBits(3));  // 4
        System.out.println(countTotalSetBits(10)); // 17
        System.out.println(countTotalSetBits(1));  // 1
    }
}

Complexity Analysis

• Time Complexity: O(log N) — We reduce the problem by half (roughly) at each step
• Space Complexity: O(log N) — Recursion stack depth, can be made O(1) with iteration

Key Takeaways

1. Pattern in Binary: Numbers 0 to 2^k - 1 have exactly k * 2^(k-1) total set bits
2. Divide and Conquer: Split the problem at the highest power of 2 ≤ N
3. MSB Contribution: All numbers from 2^a to N have the most significant bit set
4. Interview Tip: This is a classic problem testing mathematical thinking with bit manipulation