math - Given XOR & SUM of two numbers. How to find the numbers?

Question

Given XOR & SUM of two numbers. How to find the numbers? For example, x = a+b, y = a^b; if x,y are given, how to get a, b? And if can't, give the reason.

Answer 1

This cannot be done reliably. A single counter-example is enough to destroy any theory and, in your case, that example is 0, 100 and 4, 96. Both of these sum to 100 and xor to 100 as well:

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

Hence given a sum of 100 and an xor of 100, you cannot know which of the possibilities generated that situation.

For what it's worth, this program checks the possibilities with just the numbers 0..255:

#include <stdio.h>

static void output (unsigned int a, unsigned int b) {
    printf ("%u:%u = %u %u
", 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;
}

You can then take that output and massage it to give you all the repeated possibilities:

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

which gives:

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

Even in that reduced set, there are quite a few combinations which generate the same sum and xor, the worst being the large number of possibilities that generate a sum/xor of 255/255, which are:

255:255 = 0 255
255:255 = 1 254
255:255 = 2 253
255:255 = <n> <255-n>, for n = 3 thru 255 inclusive