# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* apoorv_me

*apoorv_me*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

1962

# PREREQUISITES:

None

# PROBLEM:

You’re given integers A and B. Find any 0 \leq X \lt 2^{30} such that |(A\oplus X) - (B\oplus X)| is minimized.

# EXPLANATION:

Let A_i denote the i-th bit of A. Similarly define B_i and X_i.

We’ll try to figure out how to minimize |(A\oplus X) - (B\oplus X)|, that will also tell us how to find an X that achieves that.

Note that minimizing that difference is equivalent to making (A\oplus X) and (B\oplus X) as close together as possible.

Consider the i-th bit (0 \leq i \lt 30). Note that:

- If A_i = B_i, then it doesn’t matter what X_i is: (A\oplus X)_i will always equal (B\oplus X)_i, so they’ll cancel out in the difference anyway. We can just leave X_i = 0.
- If A_i \neq B_i, we’ll always obtain a difference of 2^i - the only thing we can choose is whether this is +2^i or -2^i.

For example, if A_i = 1 and B_i = 0, then choosing X_i = 0 will give us +2^i and choosing X_i = 1 will give us -2^i.

So, let i_1, i_2, \ldots, i_k be the bits where A and B differ, in *descending order*.

We have the differences 2^{i_1}, 2^{i_2}, \ldots, 2^{i_k} and we’d like to assign \pm signs to them so that the overall absolute value is as small as possible.

That can be done greedily: just do 2^{i_1} - 2^{i_2} - 2^{i_3} - \ldots - 2^{i_k}

That is, assign + to the highest power, and - to *all* the other powers.

## Proof of optimality

Now that we know for each power which sign it receives, it’s not hard to set the bits of X to achieve this:

- Assign X_{i_1} such that (A\oplus X)_{i_1} is set.

This is done by setting X_{i_1} = 0 if A_{i_1} = 1, and X_{i_1} = 1 otherwise. - For each 1 \lt j \leq k, assign X_{i_j} such that (B\oplus X)_{i_j} is set.

This is done by setting X_{i_j} = 0 if B_{i_j} = 1, and X_{i_j} = 1 otherwise.

Each testcase is thus solved in \mathcal{O}(30) time.

Though not necessary, it’s also possible to obtain a solution in \mathcal{O}(1) time in languages such as C++, by utilizing certain `builtin`

functions and bitwise operations to work on all the bits simultaneously — see the author’s code for this.

# TIME COMPLEXITY

\mathcal{O}(1) per testcase.

# CODE:

## Author's code (C++)

```
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
auto __solve_testcase = [&](int testcase) -> void {
int a, b; cin >> a >> b;
if(a == b) {
cout << a << '\n';
return;
}
int x = (a & b);
x |= 1 << (31 - __builtin_clz(a ^ b));
cout << (a ^ x) << '\n';
};
int no_of_tests; cin >> no_of_tests;
for(int test_no = 1 ; test_no <= no_of_tests ; test_no++)
__solve_testcase(test_no);
return 0;
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
a, b = map(int, input().split())
ans, flag = 0, 0
for bit in reversed(range(30)):
abit, bbit = a & (1 << bit), b & (1 << bit)
if abit == bbit: continue
if flag == 0:
if abit == 0: ans = 1 << bit
flag = 1
else:
if bbit == 0: ans += 1 << bit
print(ans)
```