XORDIF - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: apoorv_me
Tester: apoorv_me
Editorialist: iceknight1093

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)
2 Likes
2

#include<bits/stdc++.h>
using namespace std;

int main(){
long long t,n,m,a,b;
cin>>t;
while(t–){
cin>>n>>m;
if(n==m){
cout<<“0”<<endl;
continue;
}
if(n>m){
a=n;b=m;
}
else{
a=m;b=n;
}
long long x=0,i=0,temp=b;
while(a>0){
i++;
if((a&1) != (b&1)) x=i;
a = a>>1;
b=b>>1;
}
long long y=0;
while(x>1){
y=y<<1;
y++;
x–;
}
cout<<(y^temp)<<endl;

}

return 0;

}
what is wrong in my code
it is not accepting

3

Can anyone explain why output is (a ^ x), not (b ^ x) or x ?
A test case will also be appreciated

4

can somebody explain author’s code

5

It should make no difference, the question can be (a, b) and (b, a) both

1 Like
6

Why we have to do a^x, why can’t we just output x?