class Solution {
public:
long long countBits(long long N) {
// code here
long long ans = 0;
N += 1;
int D = log2(N) + 1;
vector<long long> pow2(D+1,0);
pow2[0] = 1;
pow2[1] = 2;
for(int i = 2; i <=D; i++){
pow2[i] = 2*pow2[i-1];
}
for(int i = 1 ; i <= D ; i++){
long long t = 0;
int gN = (N + pow2[i] - 1)/pow2[i];
t += (gN - 1) * pow2[i-1];
int v = N%pow2[i];
long long p = (v == 0) ? pow2[i] : v;
t += max(0LL , p - pow2[i-1]);
ans += t;
}
return ans;
}
};