题目描述

难度分:$1600$

输入$T(\leq 2000)$表示$T$组数据。

每组数据输入$n(0 \leq n \leq 10^{18})$和$x(0 \leq x \leq 10^{18})$。

输出最小的$m$，使得$[n,m]$中的所有整数的AND等于$x$，注意$m$不能低于$n$。

即$n \land (n+1) \land (n+2) \land … \land m=x$。

如果不存在这样的$m$，输出$-1$。

输入样例

5
10 8
10 10
10 42
20 16
1000000000000000000 0

输出样例

12
10
-1
24
1152921504606846976

算法

二分答案+按位贪心

比较容易看出单调性，因为随着与的数越多，按位与的结果是单调不增的，对于一个给定的上界$m$：

1. 如果$[n,m]$内所有数字按位与的结果大于$x$，说明$m$太小了，往右搜索。
2. 否则$m$有可能是答案，往左搜索。

当二分收敛之后，检查一下此时得到的$m$是否满足$\land_{i=n}^{m}i =x$即可，满足就输出$m$，不满足就输出$-1$。

问题就在于怎么快速计算$[left,right]$中所有元素按位与的结果？这是一个经典问题，$LeetCode201.$数字范围按位与就是这个问题。找到$left$和$right$从高位到低位第一个不一样的位，区间内所有数按位与的结果就是从这一位开始后面都是$0$，前面都不变，解释如下：

令$left=$xxxxx0xxxxx，$right=$xxxxx1xxxxx。而xxxxx011111$\gt left$，xxxxx100000 $\lt right$，xxxxx011111和xxxxx100000按位与之后就是xxxxx000000。

复杂度分析

时间复杂度

二分答案的时间复杂度为$O(log_2A)$，本题中$A=5 \times 10^{18}$（原题中$m$的上界），它与$n$是同规模的，因此写成$O(log_2n)$也可以。一共$T$组数据，因此算法整体的时间复杂度为$O(T(log_2n)^2)$（$log_2n$最大就是$60$出头，每次$check$的常数操作为$60$，也是$log_2n$级别），在极限情况下，计算量的常数操作次数为$2000 \times 60^2=7.2 \times 10^6$，是可以过的。

空间复杂度

仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
int t;
LL n, x;

LL rangeBitwiseAnd(LL left, LL right) {
    LL ans = 0;
    for(int i = 60; i >= 0; i--) {
        if((left>>i&1) != (right>>i&1)) break;
        if(left>>i&1) ans |= 1LL<<i;
    }
    return ans;
}

bool check(LL left, LL right) {
    return rangeBitwiseAnd(left, right) > x;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld", &n, &x);
        LL l = n, r = 4e18;
        while(l < r) {
            LL m = l + ((r - l)>>1);
            if(check(n, m)) {
                l = m + 1;
            }else {
                r = m;
            }
        }
        if(rangeBitwiseAnd(n, r) == x) {
            printf("%lld\n", r);
        }else {
            puts("-1");
        }
    }
    return 0;
}