Official Editorial (C++)

Explanation

A good strategy to tackle these problems is just to simulate and try to spot a pattern. Also, keep in mind what matters in each step and construct cases around it. Finally, process queries in a way so that you can differentiate between all of the cases.

Here, we can query from the most significant to the least significant bit. This is because in bitwise, since higher bits always take priority, it is hard to bypass the effects of the higher bits if you don't already know them.

First, we can submit a query $(c, d) = (0, 0)$ to figure out whether $a$ or $b$ is greater (this will become helpful later on). Now, loop from most to least significant bits. Let $\mathtt{curA}$ and $\mathtt{curB}$ be the values for the bits of $a$ and $b$ we already know. We can try to differentiate the two numbers at this bit. We can submit two queries, in the form $(\mathtt{curA}| 2^B, \mathtt{curB})$, and $(\mathtt{curA}, \mathtt{curB} | 2^B)$ where we are currently looping on bit $B$. We also know that there are the following four cases we have to consider:

1. Both $a$ and $b$ has bit $B$ activated
2. Neither $a$ and $b$ has bit $B$ activated
3. Only $a$ has bit $B$ activated
4. Only $b$ has bit $B$ activated

When it is the first two cases, the results for the two queries will be different. This is because the since we are using XOR on an activated bit in one number and not the other, there will always be one query greater, since they have the same bit at this position. If the first query yields $-1$ or second query yields a $1$, both $a$ and $b$ must have bit $B$ activated.

Thus for the last two cases, the results for the two queries will be different. To differentiate which number will take the bit, remember we know which number is greater so far! In this case, the greater number must take this bit, or else the smaller number must take it and that leads to a contradiction since higher bits take priority. Now, we have to update which is greater based on our current query to remove the effect of the more significant bits.

Implementation

Time Complexity: $\mathcal{O}(1)$

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

int ask(int a, int b) {
	cout << "? " << a << " " << b << endl;
	int res;
	cin >> res;
	return res;
}

Copy
import java.io.*;
import java.util.*;

public class EhabAndXOR {
	public static void main(String[] args) {
		Kattio io = new Kattio();

		boolean aGreaterThanB = (ask(0, 0) == 1 ? true : false);
		int a = 0;
		int b = 0;

Copy
def ask(a: int, b: int):
	print(f"? {a} {b}")
	res = int(input())
	return res


a_greater_than_b = ask(0, 0) == 1
a, b = 0, 0

# 2^29 is the maximum bit due to constraints