Count total set bits in all numbers from 1 to n

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}