Liczenie liczby rozwiązań dla 2 związanych równań

Question

Jak znaleźć liczbę rozwiązań dla

s = a+b 
x = a^b 

Kiedy s i x są podane, a ^ oznacza xor?

Tak dla jak (0,0) lub (31,31) lub (15,10)?

Próbowałem przekonwertować x na ciąg znaków binarnych, ale po tym nie jestem pewien, gdzie z tym skończyć.

Answer 1

Jeśli nie ma rozwiązań, metoda zwraca . Jeśli istnieje rozwiązanie, zwraca a (tylko dla jednego rozwiązania). Możesz uzyskać b, wykonując s - a lub x^a.

Jeśli istnieje rozwiązanie, całkowita liczba rozwiązań (w long) wynosi 2 do potęgi Long.bitCount(x).

Na przykład rozwiązanie znalezione dla s = 24, x = 6 to a = 9, b = 15. binarnie:

9 = 1001 
15 = 1111 

Liczby te różnią się w 2 pozycji, więc istnieje Math.pow(2, 2) = 4 rozwiązania w całości. Możesz uzyskać wszystkie możliwe rozwiązania, wymieniając bity z a z odpowiednimi bitami b dla niektórych lub wszystkich tych pozycji.

Daje to 3 dalsze rozwiązania.

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

Oto kod:

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

postanowiłem przeciwko pisaniu metodę zwrócić HashSet wszystkich rozwiązań, jak te zestawy będą w niektórych przypadkach być ogromny. Można jednak napisać metodę generowania wszystkich możliwych rozwiązań, bez jednoczesnego przechowywania ich wszystkich w pamięci. Zobacz na przykład: Generating all binary numbers based on the pattern

Answer 2

Oznaczmy przez v_j j-ty bit wartości v, przy czym j = 0 jest najmniej znaczącym bitem.

Kluczową obserwacją jest to, że suma arytmetyczna a + b może być wyrażona w postaci operacji xor a^b i bitów carry dodatku. Mamy

s_j = a_j^b_j^c_j = x^c_j 

gdzie c_j jest nieco carry dodany do pozycji j-tego. Aby dowiedzieć się, co dzieje się z bitów carry zauważyć, że

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. 

Ostatni warunek jest zasadniczo mówi, że

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

uwzględniając zarówno a + b a^b można określić bity c_j Spośród carry i od tego powinieneś być w stanie wydedukować formułę dla liczby rozwiązań dla każdego a_j, b_j w zależności od wartości c_j i c_ (j-1).