简单的找规律题目，我却找到比赛结束。。

题意

0 ~ n 的序列，全部用二进制表示，计算每个相邻的数之间有多少位不同。求和。

我找的规律

枚举一下相差位数： 1，2，1，3，1，2，1，4……
在2^k位时左右是对称的, 求这一位的前缀和 a[k] = a[k-1]*2 + k。
n可以由2^k组成，答案对应的求和。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1050;

typedef long long ll;

ll poww(ll x,ll y)
{
    ll ans = 1;
    while(y)
    {
        if(y&1) ans *= x;
        y >>= 1;
        x *= x;
    }
    return ans ;
}

ll n;
ll a[100];
void solve()
{
    cin >> n;
    ll ans = 0;
    for(int i=60;n > 0;i --)
        if(poww(2,i) <= n)
        {
            n -= poww(2,i);
            ans += a[i] + i + 1;
        }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin >>t;

    a[1] = 1;
    for(int i=2; i<=61; i++)
        a[i] =  a[i-1]*2 + i;
    while(t--)
        solve();
}

大佬的规律

000
001
010
011
100
101
110
111
前几位的二进制，可以看出第一位二进制一直是0101所以第一位相差n。
第二位每两位不同，所以相差n/2，同理向下。

大佬代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n;
void solve()
{
    cin >> n;
    ll ans = 0;
    while(n)
    {
        ans += n;
        n >>= 1;
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin >>t;

    while(t--)
    {
        solve();
    };
}