c++ - 求解 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

我非常怀疑是否有可能使用数学来解决这个方程。这是我 3 年前遇到的编码问题，即使现在我自己也无法解决。

到目前为止我的代码:
(这是蛮力解决方案)

#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

请注意 A + X == (A xor X) + ((A and X)<<1) .所以:

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

我们有:

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

如果满足条件，对于没有在 A 中设置位的任何整数 Y， (((A - B)>>1) 或 Y) 是一个解决方案。如果您只需要一个解决方案，您可以使用 ((A - B)>>1)，其中 Y = 0。否则没有解决方案。

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