XOR-distance (Codeforces 1918C)
Tags: Greedy, bitmasks

You are given integers $$$a$$$, $$$b$$$, $$$r$$$. Find the smallest value of $$$|({a \oplus x}) - ({b \oplus x})|$$$ among all $$$0 \leq x \leq r$$$.$$$\oplus$$$ is the operation of bitwise XOR, and $$$|y|$$$ is absolute value of $$$y$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case contains integers $$$a$$$, $$$b$$$, $$$r$$$ ($$$0 \le a, b, r \le 10^{18}$$$).

Output: For each test case, output a single number — the smallest possible value.

Note: In the first test, when $$$r = 0$$$, then $$$x$$$ is definitely equal to $$$0$$$, so the answer is $$$|{4 \oplus 0} - {6 \oplus 0}| = |4 - 6| = 2$$$.In the second test:  When $$$x = 0$$$, $$$|{0 \oplus 0} - {3 \oplus 0}| = |0 - 3| = 3$$$.  When $$$x = 1$$$, $$$|{0 \oplus 1} - {3 \oplus 1}| = |1 - 2| = 1$$$.  When $$$x = 2$$$, $$$|{0 \oplus 2} - {3 \oplus 2}| = |2 - 1| = 1$$$. Therefore, the answer is $$$1$$$.In the third test, the minimum is achieved when $$$x = 1$$$.

Sample Inputs:
10
4 6 0
0 3 2
9 6 10
92 256 23
165 839 201
1 14 5
2 7 2
96549 34359 13851
853686404475946 283666553522252166 127929199446003072
735268590557942972 916721749674600979 895150420120690183

Sample Outputs:
2
1
1
164
542
5
3
37102
27934920819538516
104449824168870225

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    t = int(input())
    for _ in range(t):
        (a, b, r) = map(int, input().split())
        if a < b:
            (a, b) = (b, a)
        diff = a - b
        i = 1 << 60
        while i:
            if diff > 2 * i and a & i and (not b & i) and (r >= i):
                diff -= i * 2
                r -= i
            i >>= 1
        print(diff)
main()

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    t = int(input())
    for _ in range(t):
        (a, b, r) = map(int, input().split())
        if a < b:
            (a, b) = (b, a)
        diff = a - b
        i = 1 << 60
        while i:
            if diff > 2 * i and a & i and (not b & i) and (r >= i):
                diff -= i * 2
                r -= i
            i >>= 1
        print(diff)
main()

Solution (Python):
import sys

def custom_read_int():
    return int(sys.stdin.readline().rstrip())

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

def custom_solution():
    t = custom_read_int()
    for _ in range(t):
        (a, b, c) = custom_read_int_list()
        if a < b:
            (a, b) = (b, a)
        ans = a - b
        cnt = 0
        mn = ans
        for i in range(60, -1, -1):
            if b >> i & 1 == 0 and a >> i & 1 == 1 and (cnt + (1 << i) <= c):
                if ans >= 2 * (1 << i):
                    cnt += 1 << i
                    ans -= 2 * (1 << i)
                else:
                    mn = min(mn, 2 * (1 << i) - ans)
        print(min(ans, mn))
if __name__ == '__main__':
    custom_solution()