2

给定两个数字的 XOR & SUM。如何找到数字？例如，x = a+b，y = a^b；如果给定 x，y，如何得到 a，b？如果不能，请给出原因。

4

4 回答 4

9

这不能可靠地完成。一个反例足以摧毁任何理论，在你的情况下，这个例子是0, 100and 4, 96。这两个总和100和异100或也是：

  0 = 0000 0000            4 = 0000 0100
100 = 0110 0100           96 = 0110 0000
      ---- ----                ---- ----
xor   0110 0100 = 100    xor   0110 0100 = 100

因此，给定 的总和100和 的异或100，您无法知道哪种可能性产生了这种情况。

对于它的价值，这个程序只用数字检查可能性0..255：

#include <stdio.h>

static void output (unsigned int a, unsigned int b) {
    printf ("%u:%u = %u %u\n", a+b, a^b, a, b);
}

int main (void) {
    unsigned int limit = 256;
    unsigned int a, b;
    output (0, 0);
    for (b = 1; b != limit; b++)
        output (0, b);
    for (a = 1; a != limit; a++)
        for (b = 1; b != limit; b++)
            output (a, b);
    return 0;
}

然后，您可以获取该输出并对其进行按摩，以提供所有重复的可能性：

testprog | sed 's/ =.*$//' | sort | uniq -c | grep -v ' 1 ' | sort -k1 -n -r

这使：

255 255:255
128 383:127
128 319:191
128 287:223
128 271:239
128 263:247
:
and so on.

即使在那个简化的集合中，也有相当多的组合会产生相同的和和异或，最糟糕的是产生 的和/异或的大量可能性255/255，它们是：

255:255 = 0 255
255:255 = 1 254
255:255 = 2 253
255:255 = <n> <255-n>, for n = 3 thru 255 inclusive
于 2013-09-11T03:59:36.723 回答
3

已经表明它无法完成，但这里有两个进一步的原因。

对于 a's 和 b's 的（相当大的）子集(a & b) == 0，你有a + b == (a ^ b)（因为不能有进位）（相反的含义不成立）。在这种情况下，对于总和中为 1 的每个位，您可以选择哪个位a或b贡献该位。显然这个子集并没有覆盖整个输入，但至少证明了一般情况下是做不到的。

此外，存在许多对，(x, y)因此没有解决方案a + b == x && (a ^ b) == y，例如（不止这些）所有对（(x, y)即((x ^ y) & 1) == 1一个是奇数，另一个是偶数），因为 xor 的最低位和总和相等（最低位没有进位）。通过一个简单的计数论证，这必须意味着至少一些对(x, y)必须有多个解决方案：显然所有对(a, b)都有一些(x, y)与它们相关联的对，所以如果不是所有对(x, y)都可以使用，那么(x, y)必须共享一些其他对。

于 2013-09-11T08:36:26.467 回答
1

这是获得所有此类对的解决方案

逻辑：让数字是a和b，我们知道

s = a + b
x = a ^ b

所以

x = (s-b) ^ b

因为我们知道 x 并且我们知道 s，所以对于从 0 到 s 的所有整数 - 只需检查最后一个方程是否满足

这是这个的代码

public List<Pair<Integer>> pairs(int s, int x) {
    List<Pair<Integer>> pairs = new ArrayList<Pair<Integer>>();
    for (int i = 0; i <= s; i++) {
        int calc = (s - i) ^ i;
        if (calc == x) {
            pairs.add(new Pair<Integer>(i, s - i));
        }
    }
    return pairs;
}

类对定义为

class Pair<T> {
    T a;
    T b;

    public String toString() {
        return a.toString() + "," + b.toString();
    }

    public Pair(T a, T b) {
        this.a = a;
        this.b = b;
    }
}

测试这个的代码：

public static void main(String[] args) {
    List<Pair<Integer>> pairs = new Test().pairs(100,100);
    for (Pair<Integer> p : pairs) {
        System.out.println(p);
    }
}

输出：

0,100
4,96
32,68
36,64
64,36
68,32
96,4
100,0
于 2016-03-29T11:26:46.253 回答
0

如果你有 a , b 总和 = a+b = (a^b) + (a&b)*2 这个等式可能对你有用

于 2016-03-01T19:06:17.607 回答