#include<bits/stdc++.h>

#include<vector>

using namespace std;

//时间复杂度:O(N)

int f(int x)

{

    int dp[x+1];

    memset(dp,0,sizeof(dp));

    int sum=0;

    for(int i=1;i<=x;i++)

    {

        dp[i]=dp[i&(i-1)]+1;

        sum+=dp[i];

    }

    return sum;

}

/**

思路：

   i&(i-1)每次能去掉一个1,所以只要求出去掉1的数对应的二进制中1的个数

   再加上1就知道了i的二进制中1的个数

状态转移方程:

   dp[i]=dp[i&(i-1)]+1

dp[i]:

   数字i的二进制中1的个数

*/

int main()

{

    cout<<f(5)<<endl;

    return 0;

}