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.

Kenn

If you had actually cut-and-pasted the assignment, the grammar would be better. – Progestational

You can't. Counterexample: x=9, y=5: 3+6==9, 3^6==5. 2+7==9, 2^7==5. – Fluidextract

Also, why is this tagged bitwise-and? – Fluidextract

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\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;
}

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

Kessel

Answer 2

It has already been shown that it can't be done, but here are two further reasons why.

For the (rather large) subset of a's and b's (a & b) == 0, you have a + b == (a ^ b) (because there can be no carries) (the reverse implication does not hold). In such a case, you can, for each bit that is 1 in the sum, choose which one of a or b contributed that bit. Obviously this subset does not cover the entire input, but it at least proves that it can't be done in general.

Furthermore, there exist many pairs of (x, y) such that there is no solution to a + b == x && (a ^ b) == y, for example (there are more than just these) all pairs (x, y) where ((x ^ y) & 1) == 1 (ie one is odd and the other is even), because the lowest bit of the xor and the sum are equal (the lowest bit has no carry-in). By a simple counting-argument, that must mean that at least some pairs (x, y) must have multiple solutions: clearly all pairs of (a, b) have some pair of (x, y) associated with them, so if not all pairs of (x, y) can be used, some other pairs (x, y) must be shared.

Porter

Answer 3

Here is the solution to get all such pairs

Logic: let the numbers be a and b, we know

s = a + b
x = a ^ b

therefore

x = (s-b) ^ b

Since we know x and we know s, so for all ints going from 0 to s - just check if this last equation is satisfied

here is the code for this

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 is defined as

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;
    }
}

Code to test this:

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

Output:

0,100
4,96
32,68
36,64
64,36
68,32
96,4
100,0

Oersted

Answer 4

if you have a , b the sum = a+b = (a^b) + (a&b)*2 this equation may be useful for you

Aquatint