题解：CF2085C Serval and The Formula

· · 题解

简要说明题意：

已知 x,y，求 k 使得 (x+k)+(y+k) = (x+k) \space \textrm{xor} \space (y+k)，如果不存在输出 -1。

题目分析：

众所周知 a+b=2(a \space \textrm{bitand} \space b)+a \space \textrm{xor} \space b，那么只需要找到 k 满足 (x+k) \space \textrm{bitand} \space (y+k)=0，就能让条件成立。也就是说，x+k 和 y+k 的任意二进制位不能同时为1。所以输出 -1 的条件就是 x=y。

考虑到 k 可以大于 x,y，那么直接从低位开始扫，两数的某位如果同时为 1，就把大的那个加进位。这个过程可以迭代，可以解决问题。

代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int T;
    long long x,y,t,temp,cnt,k;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&x,&y),k=0ll,t=(x&y);
        if(x==y){
            printf("-1\n");
            continue;
        }
        while(t){
            temp=(t&(-t)),temp=(temp<<1)-1;
            cnt=min(((x&temp)^temp)+1,((y&temp)^temp)+1);//计算要加到进位差多少，可能有更简单的表达方式？
            k+=cnt,x+=cnt,y+=cnt;
            t=(x&y);
        }
        printf("%lld\n",k);
    }
    return 0;
}
/*
1
3 7
*/