Efficiently Count Set Bits from 1 to N (Up to 10^15) — A Greedy Bit-by-Bit Approach

Counting set bits (1s in binary) from 1 to N=10^15 naively would take O(N) = 10^15 operations—impossible for competitive programming. The key insight: process each bit position independently using greedy largest-first strategy.

ll n; cin>>n;
         vector<ll>v; ll sm = 0;
         for (ll i = 0; i <= 50; i++)
         {
            if(n & (1ll<<i)){
                v.pb(i); sm += (1ll<<i);
            }
         }

         sort(v.rbegin(),v.rend());


         ll ans = 0;
         while(!v.empty()){

            ll a = *v.begin();

            ll b = (1ll<<a);

            ll c = (b*a)/2;

            ans += c;

            ll d = sm - (b-1);

            ans += d;

            sm -= b;

          //  cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;

            v.erase(v.begin());
         }cout<<ans<<endl;

       // by Hritik

The Core Mathematical Insight

For any bit position k (where 2^k is the bit value), when counting 1s from 1 to N:

1 => Full cycles contribution: Numbers with bit k set in complete 2^(k+1) cycles contribute (2^k * k)/2 ones

2 => Remaining suffix: After removing highest bit b=2^a, count ones in remaining sum (N — b + 1)

For bit position a where b = 2^a:

• c = (b * a) / 2 // Complete cycles contribution
• d = sm — (b — 1) // Remaining numbers after this bit Total = c + d

Time & Space Complexity

Time: O(60 log 60) = O(1) [60 bits max, sorting negligible]

Space: O(60) = O(1)