Count Total Set Bits in All Numbers From 1 to N

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

Constraints: N can be large, so an O(N log N) or naive O(N) per-number bit count may be too slow; an O(log N) formula-based approach is expected for the optimal solution.

Example: N=4 -> binary of 1,2,3,4 = 1,10,11,100 -> set bits = 1+1+2+1 = 5.

Approach: Naive: for each number 1..N, count bits via Brian Kernighan's algorithm, O(N log N) total. Optimal: use the pattern that in every block of 2^(i+1) numbers, exactly half have bit i set, giving a closed-form recursive formula computable in O(log N).