给出两个数字的XOR和SUM.如何找到这些数字？

Question

给出两个数字的XOR和SUM.如何找到这些数字？例如,x = a + b,y = a ^ b; 如果给出x,y,如何获得a,b？如果不能,给出原因.

Answer 1

这不能可靠地完成.一个单一的反例就足以摧毁任何理论,在你的情况,例如是0, 100和4, 96.这两者总和100和xor 100相同:

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

因此,给定一个100和的xor 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.

即使在减少的集合中,也有相当多的组合产生相同的和和xor,最差的是产生sum/xor的大量可能性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