Counting the number of solutions for two related equations

Question

How to find the number of solutions for

s = a+b x = a^b 

When s and x given, and ^ means xor ?

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

I tried converting x to a binary string, but after that I am not sure where to go.

Answer 1

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

If there is a solution, the total number of solutions (in long ) is 2 degrees. Long.bitCount(x) .

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

  9 = 1001 15 = 1111 

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

This gives 3 more 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 not to write a method to return a HashSet all solutions, since in some cases these sets would be massive. However, you can write a method to create all possible solutions without storing them immediately in memory. See, for example, Generating All Binary Numbers Based on a Pattern

Answer 2

Denote by v_j the jth bit of the value v, where j = 0 is the least significant.

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

 s_j = a_j ^ b_j ^ c_j = x ^ c_j 

where c_j is the carry bit added to the jth position. To find out what happens with carry bits, note 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 essentially says 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 transfer and from this you can derive a formula for the number of solutions for each a_j, b_j depending on the values ​​of c_j and c_ (J-1).