题目2 : 二进制翻转

/*

    Name: rev x& count num 1 of x in binary

    Copyright: @2017 shenben

    Author: shenben

    Date: 25/04/17 16:47

    Description:

//枚举当前要计算的数的位数，考虑从左右往中间dp

//f[i][j][k][cmp1][cmp2]表示考虑了前 i 位和后 i 位，前 i 位需要 j 个进位，后 i 位的进位为 k，前 i 位和后 i 位和上限的大小情况分别是 cmp1，cmp2

//转移时，同时枚举第 i+1 位和倒数第 i+1 位的值，枚举该位最后是否是 1 ，根据这个判断是否需要进位即可

//时间复杂度 O((logn)^2)

//(来自官方题解)

*/

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=;

ll n,ans;int m,dig[N];

ll f[N][N][][][];

ll s[N][N][][][];

inline int fun(int b,int x,int y){

    if(x==y) return b;

    if(x<y) return ;

    return ;

}

void solve(){

    memset(f,,sizeof f);

    memset(s,,sizeof s);

    if(m==){ans++;return ;}

    f[][][][fun(,,dig[])][]=;

    f[][][][fun(,,dig[])][]=;

    s[][][][fun(,,dig[])][]=;

    s[][][][fun(,,dig[])][]=;

    for(int i=;i<=m/;i++){

        for(int j=;j<=m;j++){

            for(int a=;a<;a++){

                for(int b=;b<;b++){

                    for(int c=;c<;c++){

                        ll k=f[i-][j][a][b][c];

                        ll l=s[i-][j][a][b][c];

                        if(!k) continue;

                        //0,0

                        f[i][][a|(dig[m-i+]==)][fun(b,,dig[i])][]+=k;

                        s[i][][a|(dig[m-i+]==)][fun(b,,dig[i])][]+=l;

                        //0,1

                        f[i][j+][a|(dig[m-i+]==)][fun(b,,dig[i])][c]+=k;

                        s[i][j+][a|(dig[m-i+]==)][fun(b,,dig[i])][c]+=l+k*(-c);

                        if(a|(dig[m-i+]==)){

                            //1,0

                            f[i][j+][a][fun(b,,dig[i])][c]+=k;

                            s[i][j+][a][fun(b,,dig[i])][c]+=l+k*(-c);

                            //1,1

                            f[i][][a][fun(b,,dig[i])][]+=k;

                            s[i][][a][fun(b,,dig[i])][]+=l+k*(-j);

                        }

                    }

                }

            }

        }

    }

    if(m&){

        int i=m+>>;

        for(int j=;j<=m;j++){

            for(int a=;a<;a++){

                for(int b=;b<;b++){

                    for(int c=;c<;c++){

                        ll k=f[i-][j][a][b][c];

                        ll l=s[i-][j][a][b][c];

                        if(!k) continue;

                        //

                        f[i][][a|(dig[m-i+]==)][b][]+=k;

                        s[i][][a|(dig[m-i+]==)][b][]+=l;

                        //

                        if(a|(dig[m-i+]==)){

                            f[i][][a][b][]+=k;

                            s[i][][a][b][]+=l+k*(-j);

                        }

                    }

                }

            }

        }

    }

    int i=m+>>;

    for(int j=;j<=m;j++){

        for(int a=;a<;a++){

            for(int b=;b<;b++){

                for(int c=;c<;c++){

                    if(!a&&!b) continue;

                    ll k=f[i][j][a][b][c];

                    ll l=s[i][j][a][b][c];

                    if(!k) continue;

                    ans+=l;

                    if(c) ans-=k*j;

                }

            }

        }

    }

}

int main(){

    cin>>n;

    for(ll t=n;t;t>>=) dig[++m]=t&;

    for(solve();--m;){

        for(int i=;i<=m;i++) dig[i]=;

        solve();

    }

    cout<<ans;

    return ;

}