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;
    }
    
};