Counting the number of solutions for 2 related equations

Question

How do I find the number of solutions for

s = a+b
x = a^b

When s and x are given, and ^ means xor?

So for like (0,0) or (31,31) or (15,10)?

I've tried converting x into a binary string but after that I'm unsure where to go with it.

Answer 1

The method solution returns null if there are no solutions. If there is a solution, it returns a (for just one solution). You can get b by doing s - a or x ^ a.

If a solution exists, the total number of solutions (in long) is 2 to the power of Long.bitCount(x).

For example, the solution found for s = 24, x = 6 is a = 9, b = 15. In binary:

 9 = 1001
15 = 1111

These numbers differ in 2 positions, so there are Math.pow(2, 2) = 4 solutions in total. You can get all possible solutions by interchanging the bits of a with the corresponding bits of b for some or all of these positions.

This gives 3 further solutions.

11 = 1011     13 = 1101     15 = 1111
13 = 1101     11 = 1011      9 = 1001

Here is the code:

public static Long solution(long s, long x) {
    return recursive(s, x, false);
}

private static Long recursive(long s, long x, boolean carry) {
    boolean s1 = (s & 1) == 1;
    boolean x1 = (x & 1) == 1;
    if ((s1 == x1) == carry)
        return null;
    if ((s == 0 || s == -1) && (x == 0 || x == -1))
        return s;
    Long a;
    if (x1)
        return (a = recursive(s >> 1, x >> 1, carry)) == null ? null : a << 1;
    if ((a = recursive(s >> 1, x >> 1, false)) != null)
        return a << 1;
    if ((a = recursive(s >> 1, x >> 1, true)) != null)
        return 1 + (a << 1);
    return null;
}

I decided against writing a method to return a HashSet of all solutions, as these sets would, in some cases, be massive. However, you could write a method for generating all possible solutions, without storing them all in memory at once. See, for example, Generating all binary numbers based on the pattern

Answer 2

Let's denote by v_j the j-th bit of value v with j=0 being the least significant bit.

The key observation is that the arithmetic sum a+b can be expressed in terms of xor operation a ^ b and the carry bits of the addition. We have

s_j = a_j ^ b_j ^ c_j = x ^ c_j

where c_j is the carry bit added to j-th position. To figure out what happens with carry bits, notice that

c_0 = 0
c_1 = a_0 & b_0   (so c_1 is one when both a_0 and b_0 are one)
c_j = 1 if and only if at least two of a_j, b_j, c_(j-1) are one.

The last condition is essentially saying that

c_j = Majority(a_j, b_j, c_(j-1)) = a_j & b_j ^ a_j & c_(j-1) ^ b_j & c_(j-1)

Having both a + b and a ^ b you can determine the bits c_j of the carry and from that you should be able to deduce the formula for the number of solutions for each a_j, b_j depending on the values of c_j and c_(j-1).