How to solve the XORABC problem

Can anyone explain the logic behind this problem?

The editorial of the problem proves that if X is odd or power of 2, then no solution exits. Otherwise, one of the possible solutions is A = 0, B = \frac{X}{2} and C = 2^p, where B.C \ne 0. It follows that A \oplus B = \frac{X}{2}, B \oplus C = \frac{X}{2}-2^p, C \oplus A = 2^p, and the summation of these three expressions is equal to X.

I don’t understand, why can’t X be a power of 2? Please explain! @codingknight

Because if X is power of 2, the only valid value for C = 2^p that satisfies B = \frac{X}{2} and B.C \ne 0 is C = B which violates the constraint that A, B and C are distinct values.

Thanks! Just want to ask a question, In this problem, you found that B should be equal to X/2 and C = 2^p. Now, how can this thing click in someone’s mind?

Excuse me, there is no mind-clicking button in this choice. It is driven by mathematical analysis as follows.

  1. If (A,B,C) is a valid solution for the equation, then it can be shown that (Y \oplus A, Y \oplus B, Y \oplus C) is also a valid solution for any 0 \le Y < 2^{30}. By choosing Y=A, it follows that (0,U,V) is a valid solution where U = A \oplus B and V = A \oplus C. The problem is then reduced to solving the equation (U+V) + (U \oplus V) = X, where U,V > 0 and U \ne V.

  2. Using the fact that U+V = (U \oplus V) + 2 (U\cdot V) for any U and V, the equation can be rewritten as 2 (U \cdot V) + 2 (U \oplus V) = X. If X is an odd number, then the problem has no solution. Otherwise, let W = \frac{X}{2}. The equation can be rewritten as (U \cdot V) + (U \oplus V) = W, where W > 0.

  3. Let f(u,v) = u \cdot v and g(u,v) = u \oplus v be two Boolean functions in u and v. It follows that f(u,v) \cdot g(u,v) = 0 for any u and v, and that the previous equation can be decomposed into 30 independent bit equations f(u_i,v_i) + g(u_i,v_i) = w_i whose solution is u_i = v_i = 0 if w_i = 0 and u_i | v_i = 1 if w_i = 1. The reason for the independence of the bit equations is that it never happens that f(u_i,v_i) = g(u_i,v_i) = 1, and therefore the arithmetic bit addition operation f(u_i,v_i)+g(u_i,v_i) never produces a carry bit that affects the result of subsequent more significant bit operation.

  4. Finally, let p be chosen such that w_p = 1. It follows that U = 2^p and V = W is a valid solution if X is not power of 2, as U \cdot V = U, U \oplus V = W-U and V \ne U. In fact, when the choice of V is fixed at W, any positive value U such that U \cdot W = U and U < W is also a valid choice for U. In this case, U is a proper sub-mask of the ones in W, i.e. if U \cdot 2^i = 2^i for some position 0 \le i < 30, then W \cdot 2^i = 2^i as well, and there exists at least one position i such that U \cdot 2^i = 0 and W \cdot 2^i = 2^i.

2 Likes

proof for u+v = u xor v + 2uv?

It is simple to prove that u \oplus v can be expressed in arithmetic form as follows.

u \oplus v = u \cdot (1-v) + (1-u) \cdot v

This equation can be rewritten as

u + v = u \oplus v + 2 u v

1 Like