Log inSign up
mediumGeeksforGeeksNot Started

Count Total Set Bits from 1 to N

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on GeeksforGeeks
Lesson

Problem Statement

You are given a positive integer n. Find the total count of set bits (1s) in the binary representations of all numbers from 1 to n, inclusive.

Example 1 · Example 1: Small Integer:

Input: n = 4
Output: 5
Explanation: 1 = 001 (1), 2 = 010 (1), 3 = 011 (2), 4 = 100 (1). Total = 1 + 1 + 2 + 1 = 5.

Example 2 · Example 2: Seven:

Input: n = 7
Output: 12
Explanation: Numbers 1 through 7 have 1, 1, 2, 1, 2, 2, 3 set bits respectively. Sum = 12.

Example 3 · Example 3: Boundary Case 1:

Input: n = 1
Output: 1
Explanation: Only 1 is considered, which has exactly 1 set bit.

Constraints:

  • 1 <= n <= 108

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Analyze binary column periodicity across consecutive integer sequences.
  • Derive the closed-form cycle formula for 1-bits at position i.
  • Transition from O(n log n) simulation to O(log n) mathematical aggregation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Aggregate sum of bit properties over range [1, N].
  • N is too large for O(N) iteration.
  • Binary representations exhibit recurring power-of-2 patterns.

Algorithmic Decision Tree:

  • Iterate column index i where (1 << i) <= n.
  • Compute full cycles: (n + 1) / (1 << (i + 1)) * (1 << i).
  • Add tail remainder: max(0, ((n + 1) % (1 << (i + 1))) - (1 << i)).

Connected Patterns:

Counting BitsCount Set BitsDigit DP

1. Sequential Popcount Summation

Intuition

Initialize total = 0. For every integer i from 1 to n, count its set bits using val &= (val - 1) and add to total.

When to apply: Verification for small n (n <= 105).

Algorithm

  1. Step 1: Set total = 0.
  2. Step 2: Loop i from 1 to n.
  3. Step 3: Count set bits of i and add to total.
  4. Step 4: Return total.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5long long countTotalSetBitsBrute(int n) {
6 long long total = 0;
7 for (int i = 1; i <= n; ++i) {
8 int temp = i;
9 while (temp > 0) {
10 temp &= (temp - 1);
11 total++;
12 }
13 }
14 return total;
15}
16
17int main() {
18 cout << "Brute (4): " << countTotalSetBitsBrute(4) << endl; // 5
19 cout << "Brute (7): " << countTotalSetBitsBrute(7) << endl; // 12
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(n log n)
  • Space complexity: O(1)

2. Recursive Largest Power of Two

Intuition

Find x such that 2^x <= n < 2^(x + 1). The numbers 0 to 2^x - 1 have x * 2^(x - 1) set bits. For the remaining numbers 2^x to n, their most significant bit is set (n - 2^x + 1 bits), and their lower bits repeat the problem for n - 2^x. Recurse until n == 0.

When to apply: When thinking in terms of hypercube symmetries.

Algorithm

  1. Step 1: If n == 0, return 0.
  2. Step 2: Find highest power x where (1 << x) <= n.
  3. Step 3: bitsUpToPower = x * (1 << (x - 1)).
  4. Step 4: msbBits = n - (1 << x) + 1.
  5. Step 5: Return bitsUpToPower + msbBits + countSetBits(n - (1 << x)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int findLargestPower(int n) {
6 int x = 0;
7 while ((1 << (x + 1)) <= n) {
8 x++;
9 }
10 return x;
11}
12
13int countSetBitsRecursive(int n) {
14 if (n <= 0) return 0;
15 int x = findLargestPower(n);
16 int bitsUpTo2PowX = x * (1 << (x - 1));
17 int msbFrom2PowXToN = n - (1 << x) + 1;
18 int remainder = n - (1 << x);
19 return bitsUpTo2PowX + msbFrom2PowXToN + countSetBitsRecursive(remainder);
20}
21
22int main() {
23 cout << "Recursive (4): " << countSetBitsRecursive(4) << endl; // 5
24 cout << "Recursive (7): " << countSetBitsRecursive(7) << endl; // 12
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(log n)
  • Space complexity: O(log n) call stack

3. Column-wise Periodicity Formula

Intuition

Consider numbers from 0 to n (total n + 1 numbers). For bit position i, numbers form cycles of length 2^(i + 1). Each full cycle contains 2^i ones. The remaining tail numbers (n + 1) % 2^(i + 1) contribute max(0, remainder - 2^i) ones. Sum this contribution across all i where 2^i <= n.

When to apply: Optimal for production and competitive programming: strictly O(1) space, 30 iterations.

Algorithm

  1. Step 1: Set total = 0, nPlus1 = n + 1.
  2. Step 2: Loop i from 0 while (1LL << i) <= n.
  3. Step 3: cycleLen = 1LL << (i + 1), onesInCycle = 1LL << i.
  4. Step 4: fullCycles = nPlus1 / cycleLen.
  5. Step 5: remainder = nPlus1 % cycleLen.
  6. Step 6: total += fullCycles * onesInCycle + max(0LL, remainder - onesInCycle).
  7. Step 7: Return total.

Column Periodicity Trace for n = 4

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Step 1: Column 0 (weight 1)
Visual state
Values and pointers at this exact step
pointers
S
2
0
↑ col 0
Check / comparison
Column 0 ones = 2
Decision / next transition
Add 2 to total.
Why this step matters

Step 1: Column 0 (weight 1). Cycle length = 2. Total numbers = 5. Full cycles = 5 / 2 = 2. Remainder = 5 % 2 = 1. Ones = 2 * 1 + max(0, 1 - 1) = 2.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8 int countSetBits(int n) {
9 long long total = 0;
10 long long nPlus1 = (long long)n + 1;
11 for (int i = 0; (1LL << i) <= n; ++i) {
12 long long cycleLen = 1LL << (i + 1);
13 long long onesInCycle = 1LL << i;
14 long long fullCycles = nPlus1 / cycleLen;
15 long long remainder = nPlus1 % cycleLen;
16 total += fullCycles * onesInCycle + max(0LL, remainder - onesInCycle);
17 }
18 return (int)total;
19 }
20};
21
22int main() {
23 Solution sol;
24 cout << "Optimal (4): " << sol.countSetBits(4) << endl; // 5
25 cout << "Optimal (7): " << sol.countSetBits(7) << endl; // 12
26 cout << "Optimal (17): " << sol.countSetBits(17) << endl; // 35
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(log n)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear PopcountO(n log n)O(1)Loop i from 1 to n, calling Brian Kernighan's popcount on each number and summing the counts.Iterating through every number individually.
2.Better — Recursive Largest Power of TwoO(log n)O(log n)Find largest power of 2 <= n (say 2x). Numbers [0, 2x - 1] have x * 2^(x - 1) ones. Add (n - 2x + 1) for MSBs, and recurse on remainder.Logarithmic recursion.
3.Optimal — Column-wise Periodicity FormulaOptimalO(log n)O(1)Iterate over each bit position from 0 to 30. Calculate full cycle contribution + remainder in pure O(1) arithmetic.Arithmetic per bit position.

Common Pitfalls & Crucial Edge Cases

Using O(n) brute force

Calling popcount from 1 to n will get TLE for n >= 107.

Off-by-one in MSB count

Forgetting the + 1 in (n - 2^k + 1) misses the MSB contribution of 2k itself.

Integer overflow in powers of 2

Left-shifting 1 << 31 overflows signed 32-bit integers in C++/Java.

Crucial Edge Cases to Validate:

  • n = 0 — Range [1, 0] is empty, total set bits = 0.
  • n = 1 — Only one number with 1 set bit; returns 1.
  • n = 2^k - 1 (All bits set up to k) — Directly evaluates to k * 2^(k - 1) without deep recursion.
  • n = 10^9 (Large input) — O(n) brute force does 109 popcounts and times out; O(log n) math finishes in microseconds.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the binary table of 0 to 7 to show the interviewer the column-wise periodicity of bits (periods 2, 4, 8...).
  2. Explain the divide-and-conquer recurrence clearly: f(n) = k * 2^(k-1) + (n - 2^k + 1) + f(n - 2^k).
  3. Contrast the iterative column-counting method with the recursive MSB reduction method.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.For numbers from 0 to 2k - 1, how many total set bits are there?

2.How do you count total set bits for an arbitrary n using the largest power of 2 (2k <= n)?

3.What is the time complexity of the recursive / bit-by-bit optimal solution?

Back to DSA Sheet