Подсчет количества решений для 2 связанных уравнений

Question

Как найти число решений для

s = a+b 
x = a^b 

Когда s и x приведены, и ^ означает xor?

Значит, для (0,0) или (31,31) или (15,10)?

Я попытался преобразовать x в двоичную строку, но после этого я не уверен, куда идти.

Answer 1

Метод solution возвращает null, если нет решений. Если есть решение, оно возвращает a (только для одного решения). Вы можете получить b, выполнив s - a или x^a.

Если существует решение, общее количество решений (в long) равно 2 до Long.bitCount(x).

Например, решение проблемы с s = 24, x = 6 is a = 9, b = 15. в двоичном:

9 = 1001 
15 = 1111 

Эти цифры различаются в 2-х положениях, так что есть Math.pow(2, 2) = 4 решения в общей сложности. Вы можете получить все возможные решения, заменив биты a соответствующими битами b для некоторых или всех этих позиций.

Это дает еще 3 решения.

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

Вот код:

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

Я решил писать метод возвращает HashSet всех решения, так как эти наборы будут, в некоторых случаях могут быть массивными. Тем не менее, вы можете написать метод для создания всех возможных решений, не сохраняя их сразу в памяти. См., Например, Generating all binary numbers based on the pattern

Answer 2

Обозначим через v_j j-й бит значения v, где j = 0 является младшим значащим разрядом.

Главное наблюдение заключается в том, что арифметическая сумма a + b может быть выражена в терминах операции xor a^b и битов переноса сложения. Мы

s_j = a_j^b_j^c_j = x^c_j 

где c_j является бит переноса добавляется в j-й позиции. Чтобы выяснить, что происходит с кэрри битами, обратите внимание, что

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. 

Последнее условие, по существу говоря, что

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

Имея как а + Ь и а^Ь можно определить биты c_j из и из этого вы должны иметь возможность вывести формулу для числа решений для каждого a_j, b_j в зависимости от значений c_j и c_ (j-1).