Count total set bits in all numbers from 1 to n
Problem
Return the total number of 1 bits across the binary forms of every integer from 1 to n. Aim for better than looping over each number.
Example 1
Input: n = 4 Output: 5
1 (1) + 10 (1) + 11 (2) + 100 (1).
Also asked as: Count total set bits in all numbers from 1 to n
Test cases
Case 1
Input: 4 Expected: 5
Case 2
Input: 17 Expected: 35
Case 3
Input: 7 Expected: 12
Case 4
Input: 1 Expected: 1
Case 5
Input: 0 Expected: 0
View solutionHide solution1 approach
1. Per-bit contribution
Time O(log n)Space O(1)
For bit position b, the bit cycles with period 2^(b+1): 2^b zeros then 2^b ones. Count full cycles × 2^b plus the partial remainder.
function countTotalSetBits(n) { let total = 0; for (let b = 0; (1 << b) <= n; b++) { const period = 1 << (b + 1); const full = Math.floor((n + 1) / period) * (1 << b); const rem = Math.max(0, ((n + 1) % period) - (1 << b)); total += full + rem; } return total;}