算法:XOR运算

Question

你得到一个和S和X,你需要找到,如果它存在两个数a和b使得a + b = S和a ^ b = XI使用一个循环到S/2并检查它是否可能或不

for(int i=0;i<=s/2;i++)
{
   if(i^(s-i)==X)
    return true;
}

复杂性:O(n)

需要一些更好的方法

Answer 1

鉴于a+b = (a XOR b) + (a AND b)*2(从这里)我们可以计算(a AND b):

如果S <X =>不可能,否则采取SX.如果这是奇数=>不可能,否则(a AND b)=(SX)/ 2.

现在我们可以单独查看a和b的位.检查所有四种组合,我们看到只有一种结果是不可能的,即XOR和AND都是1.

因此,如果(一个XOR b)AND(a AND b)!= 0则没有解决方案.否则,人们可以找到解决方程的a和b.

if (S < X) return false;
Y = S - X;
if (Y is odd) return false;
if ((X & (Y/2)) != 0) return false;
return true;