解説

X,A,CX, A, Cii ビット目をそれぞれ Xi,Ai,CiX_i, A_i, C_i と表記することにします。

A=C&(YXA)A = C \& (Y \oplus X \oplus A) をビット毎に考えると AiCi(Yi+Xi+Ai)mod2A_i \equiv C_i (Y_i + X_i + A_i) \mod 2 となり、

これより CiYiCiXi+Ai(1+Ci)mod2C_i Y_i \equiv C_i X_i + A_i (1 + C_i) \mod 2 となります。

ここで求めたいのは最小となる YY であるため、 Ci=0C_i = 0 であれば Yi=0Y_i = 0 としてよいです。

Ci=1C_i = 1 なら、 Yi=XiY_i = X_i となります。

よって Yi=CiXiY_i = C_i X_i となり、 Y=C&XY = C \& XO(1)O(1) で求めることができました。

YiY_i を探索する方法も可能で、こちらは O(logY)O(\log Y) となります。