Shared code

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	// (popcount, cardinality)
	vector<vector<pair<int, int>>> memoized(63, vector<pair<int, int>>(2, make_pair(-1, -1)));
	
	function<pair<int, int>(int, bool)> recurse = [&](int index, bool ok) {
		if (index == -1) return make_pair(0ll, 1ll);
		auto &saved = memoized[index][ok];
		if (saved.first != -1) return saved;
		
		auto &[popcount, cardinality] = saved;
		
		popcount = 0;
		cardinality = 0;
		
		auto travel = [&](int next_bit) {
			if (ok)
			{
				auto [popcount1, cardinality1] = recurse(index - 1, true);
				popcount += popcount1;
				if (next_bit == 1)
					popcount += cardinality1;
				cardinality += cardinality1;
				return;
			}
			
			if (next_bit > ((n >> index) & 1)) return;
			if (next_bit < ((n >> index) & 1))
			{
				auto [popcount1, cardinality1] = recurse(index - 1, true);
				popcount += popcount1;
				if (next_bit == 1)
					popcount += cardinality1;
				cardinality += cardinality1;
				return;
			}
			
			auto [popcount1, cardinality1] = recurse(index - 1, false);
			popcount += popcount1;
			if (next_bit == 1)
				popcount += cardinality1;
			cardinality += cardinality1;
		};
		
		travel(0);
		travel(1);
		
		return saved;
	};
	
	cout << recurse(62, false).first << "\n";
}