1501: 奶牛学算术

题目描述：

天啊，奶牛居然学会了算术，不服气的你为了证明奶牛超不过人类，于是来了一场正面的算术对决。不过还好，人类拥有计算机这个好东西。对决的题目是一个等式x+y=x|y(‘|’表示或运算)。奶牛会给出一个数x，和一个数k表示第k小满足等式的y。请你为了人类的尊严，计算出y。其中(0<x,y,k<10^18,且,x,y,k均为整数)

输入：

输入t表示有t组数据(t<100)

每组数据输入x和k

输出：

输出y

样例输入

1
4 2

样例输出

2

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
首先我想到的是肯定有规律，先打表，然而并没有什么发现。然后从等式发现有位运算操作就联想到二进制，写了前两组，感觉有些发现。
但是如果从每一位去判断两种情况还是太复杂，不好做。结果忽然间想起以前做的一道题，似曾相识，就是x的二进制里面插入k的二进制。
*/
#include <iostream>
using namespace std;

int main()
{
    /*打表，x从1开始的第5小数
    for(int i = 1; i < 10; i++) {
        cout << "x = " << i << ' ';
        int k = 0;
        for(int j = 1; ; j++) {
            if((i + j) == (i | j)) k++;
            if(k == 5) {
                cout << j <<endl;
                break;
            }
        }
    }
    */
    long long x, k, t; cin >> t;
    while(t--) {
        cin >> x >> k;
        int ans[55], bx[55], bk[55], dex = 0, dek = 0, tag = 0;
        while(x) {
            bx[dex++] = x % 2;
            x >>= 1;
        }
        while(k) {
            bk[dek++] = k % 2;
            k >>= 1;
        }
        int tmp = 0;
        for(int i = 0; i < dex; i++) {
            if(bx[i] == 1) ans[tag++] = 0;
            else if(tmp < dek) ans[tag++] = bk[tmp++];
        }
        while(tmp < dek) ans[tag++] = bk[tmp++];
        long long ret = 0, bin = 1;
        for(int i = 0; i < tag; i++) {
            ret += bin * ans[i];
            bin <<= 1;
        }
        cout << ret <<endl;
    }
    return 0;
}