Mikasa (Codeforces 1554C)
Tags: Greedy, bitmasks

You are given two integers $$$n$$$ and $$$m$$$. Find the $$$\operatorname{MEX}$$$ of the sequence $$$n \oplus 0, n \oplus 1, \ldots, n \oplus m$$$. Here, $$$\oplus$$$ is the bitwise XOR operator.$$$\operatorname{MEX}$$$ of the sequence of non-negative integers is the smallest non-negative integer that doesn't appear in this sequence. For example, $$$\operatorname{MEX}(0, 1, 2, 4) = 3$$$, and $$$\operatorname{MEX}(1, 2021) = 0$$$. 

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 30\,000$$$)  — the number of test cases.The first and only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$0 \le n, m \le 10^9$$$).

Output: For each test case, print a single integer  — the answer to the problem.

Note: In the first test case, the sequence is $$$3 \oplus 0, 3 \oplus 1, 3 \oplus 2, 3 \oplus 3, 3 \oplus 4, 3 \oplus 5$$$, or $$$3, 2, 1, 0, 7, 6$$$. The smallest non-negative integer which isn't present in the sequence i. e. the $$$\operatorname{MEX}$$$ of the sequence is $$$4$$$.In the second test case, the sequence is $$$4 \oplus 0, 4 \oplus 1, 4 \oplus 2, 4 \oplus 3, 4 \oplus 4, 4 \oplus 5, 4 \oplus 6$$$, or $$$4, 5, 6, 7, 0, 1, 2$$$. The smallest non-negative integer which isn't present in the sequence i. e. the $$$\operatorname{MEX}$$$ of the sequence is $$$3$$$.In the third test case, the sequence is $$$3 \oplus 0, 3 \oplus 1, 3 \oplus 2$$$, or $$$3, 2, 1$$$. The smallest non-negative integer which isn't present in the sequence i. e. the $$$\operatorname{MEX}$$$ of the sequence is $$$0$$$.

Sample Inputs:
5
3 5
4 6
3 2
69 696
123456 654321

Sample Outputs:
4
3
0
640
530866

Solution (Python):
import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.readline())

def LI():
    return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def LI1():
    return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
    return [LI1() for _ in range(rows_number)]

def SI():
    return sys.stdin.readline().rstrip()
inf = 10 ** 16
md = 10 ** 9 + 7

def solve():
    (n, m) = LI()
    if n > m:
        print(0)
        return
    ans = n ^ m
    cur = ans & n
    if cur:
        i = cur.bit_length()
        ans = ans >> i << i
    else:
        for i in range(32):
            if ans >> i & 1 == 0 and n >> i & 1 == 0:
                ans = ans >> i << i
                ans |= 1 << i
                break
    print(ans)
for testcase in range(II()):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline

def fun(n, m):
    nbin = bin(n)[2:]
    mbin = bin(m + 1)[2:]
    k = ''
    if len(nbin) > len(mbin):
        return 0
    elif len(mbin) > len(nbin):
        idx = len(mbin) - len(nbin)
        k = mbin[:idx]
        nbin = ''.join(['0'] * (len(mbin) - len(nbin))) + nbin
    else:
        idx = 0
    while idx < len(nbin):
        if nbin[idx] == mbin[idx]:
            k += '0'
        elif nbin[idx] == '0' and mbin[idx] == '1':
            k += '1'
        else:
            k = k + ''.join(['0'] * (len(nbin) - idx))
            break
        idx += 1
    return int(k, 2)
t = int(input())
for i in range(t):
    (n, m) = map(int, input().split())
    print(fun(n, m))

Solution (Python):
def solve():
    (n, m) = map(int, input().split())
    if n > m:
        return 0
    if n | m == m:
        return n ^ (n | m + 1)
    bm = bin(m)[2:]
    bn = bin(n)[2:]
    bn = '0' * (len(bm) - len(bn)) + bn
    to_transform = list(bn)
    for i in range(len(to_transform)):
        if to_transform[i] == '1' and bm[i] == '0':
            break
        elif to_transform[i] == '0' and bm[i] == '1':
            to_transform[i] = bm[i]
    ans = n ^ (n | int(''.join(to_transform), 2))
    return ans
t = int(input())
for _ in range(t):
    print(solve())