Algorithm to find a solution for A xor X = B + X

Question

Given integer A and B, find integer X so that:

• A,B < 2*1e18
• A xor X = B + X

I highly doubt it is possible to solve this equation using maths. This is a coding problem I came across 3 years ago and even now I can't solve this myself.

My code so far: (this is the brute force solution)

#include <iostream>  using namespace std;  int main() {      unsigned long long a, b;     cin >> a >> b;     for (unsigned long long x = 1; x < max(a, b); x++) {         unsigned long long c = a ^ x;         unsigned long long d = b + x;         if (c == d) {             cout << x << endl;             break;             return 0;         }     }      cout << -1; //if no such integer exists      return 0; } 

Answer 1

Note that A + X == (A xor X) + ((A and X)<<1). So:

A xor X = A + X - ((A and X)<<1) = B + X A - B = (A and X)<<1 

And we have:

(A - B) and not (A<<1) = 0    (All bits in (A - B) are also set in (A<<1)) (A - B)>>1 = A and X 

If the condition is met, for any integer Y that doesn't have bits that are set in A, (((A - B)>>1) or Y) is a solution. If you want just one solution, you could use ((A - B)>>1), where Y = 0. Otherwise there is no solution.

int solve(int a, int b){     int x = (a - b) >> 1;     if ((a ^ x) == b + x)         return x;     else         return ERROR; }