Codeforces Round #647 (Div. 2) C. Johnny and Another Rating Drop（思维）

题目直通车 英文题解

题意

两个数的二进制不同的个数称为两个数的不公平度，求1-n个数所有相邻的两个数的不公平度的总和。

思路

首先分析n为2^k^时，以n=2^3^为例，n=1000~2~, 从0000~2~到1000~2~

一共有四位数字，我们把它拆出来单独看：

第一位变化为010101010…变化周期为1；

第二位变化为001100110…变化周期为2；

第三位变化为000011110…变化周期为4；

第四位变化为000000001…变化周期为8；

这其实很好理解，对二进制的变化有了解就不难发现第k位变化周期未2^k-1^，由此可得1-8的二进制变化总和为1+2+4+8，一般化不难推得n=2^k^的不公平度总和为2^k+1^-1=2n-1;

在考虑n为任意数字时，我们得到它的二进制数，以n=11=1011~2~为例：

可以拆成四个数看，把它看成从0-1，00-11，000-000，0000-1000四个过程去看，这里建议纸上多写几位二进制数找一下规律，思考一下

所以此题解法为判断n的第i位是不是1，如果是1则总和加上2^i+1^-1

AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
void solve()
{
    ll a;
    cin >> a;
    ll ans=0;
    for(int i=0;i<60;i++)
    {
        if(a&((ll)1<<i))//与运算判断第i位是否为0
            ans+= ((ll)1<<(i+1))-1;
    }
    cout << ans <<endl;
}

int main(){
    int t ;
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}