Algorytm znajdowania rozwiązania dla A xor X = B + X

46

Biorąc pod uwagę liczby całkowite A i B, znajdź liczbę całkowitą X, aby:

  • A, B <2 * 1e18
  • Xor X = B + X

Bardzo wątpię, czy możliwe jest rozwiązanie tego równania za pomocą matematyki. Jest to problem z kodowaniem, na który natknąłem się 3 lata temu i nawet teraz nie mogę sam go rozwiązać.

Mój kod do tej pory: (jest to rozwiązanie brutalnej siły)

#include <iostream>

using namespace std;

int main()
{

    unsigned long long a, b;
    cin >> a >> b;
    for (unsigned long long x = 1; x < max(a, b); x++) {
        unsigned long long c = a ^ x;
        unsigned long long d = b + x;
        if (c == d) {
            cout << x << endl;
            break;
            return 0;
        }
    }

    cout << -1; //if no such integer exists

    return 0;
}
AAaAa
źródło
11
Jeśli przeczytasz trochę więcej o wyłączności lub powinieneś znaleźć równoważność algebraiczną a xor b = a + b mod 2. Spróbuj pomyśleć o tej równoważności przez chwilę.
Jakiś programista koleś
16
@Someprogrammerdude to jeśli i b są zmienne logiczne, czyli 0 lub 1, a xor jest logiczna XOR. Jaki jest związek z bitowym xor?
John Kugelman
1
fwiw, myślę, że można tu użyć brutalnej siły, chyba że chcesz napisać coś, co może udowodnić bardziej ogólne równania. Weź pod uwagę, że musisz przetestować kod, aby upewnić się, że jest poprawny, a najłatwiej byłoby przetestować go przy użyciu algorytmu brutalnej siły, ale wtedy możesz użyć brutalnej siły w pierwszej kolejności. Z drugiej strony zastosowanie matematyki sprawi, że uruchomienie dowolnego kodu nie będzie konieczne.
idclev 463035818
1
@molbdnilo Och, jeden z komentarzy sugerował, że xor b = a + b mod 2 i myślałem, że odnosi się również do liczb całkowitych. Usunę tę część mojego postu.
AAaAa
1
@JohnKugelman Miał na myśli to, mod 2co w matematyce (mod 2), tj. 3 === 7 (mod 2). Chodzi o to, że możesz odkryć równanie dla pierwszego bitu X, a następnie przejść do następnego bitu, w którym (uwzględniając przeniesienie) otrzymujesz równanie dla drugiego bitu itp., Na przykład odpowiedź Daniela.
Max Langhof

Odpowiedzi:

45

Zauważ, że A + X == (A xor X) + ((A and X)<<1). Więc:

A xor X = A + X - ((A and X)<<1) = B + X
A - B = (A and X)<<1

I mamy:

(A - B) and not (A<<1) = 0    (All bits in (A - B) are also set in (A<<1))
(A - B)>>1 = A and X

Jeśli warunek jest spełniony, dla dowolnej liczby całkowitej Y, która nie ma bitów ustawionych w A, ((((A - B) >> 1) lub Y) jest rozwiązaniem. Jeśli chcesz tylko jedno rozwiązanie, możesz użyć ((A - B) >> 1), gdzie Y = 0. W przeciwnym razie nie ma rozwiązania.

int solve(int a, int b){
    int x = (a - b) >> 1;
    if ((a ^ x) == b + x)
        return x;
    else
        return ERROR;
}
użytkownik23013
źródło
15
+1. Odnotowuje się, że A xor Xjest to „dodanie bez przeniesienia” i ((A and X)<<1)„przeniesienie w dodatku”. Ponieważ A + Xjest to „dodawanie z przenoszeniem”, pierwsze równanie ma sens.
justhalf
3
(A and X)<<1jest w gruncie rzeczy, 2*(A and X)a ponieważ jest to równe A-B, mówi, że problem może być rozwiązany tylko wtedy, gdy A i B są zdarzeniami nieparzystymi lub oba.
axiac
1
Myślałem, że to będzie miało związek z odejmowaniem, ale nie przyszedłem do tego na czas.
SS Anne
38

To nie jest bardzo trudne, po prostu trzeba myśleć mały: załóżmy, że piszesz A, Ba Xbinarnie i Aᵢjest to wartość odpowiadająca skrajnej prawej 2 bit.

Wiemy, że: Aₒ ⊕ Xₒ = Bₒ + Xₒ.

Użyjmy przykładu, aby dowiedzieć się, jak to ocenić: A = 15 i B = 6. Konwersja na binarną:

A = 1 1 1 1           B = 0 1 1 0
X = a b c d           X = a b c d

Teraz mamy kilka możliwości. Przeanalizujmy najbardziej prawe bity A i B:

1  d = 0 + d

Wiemy, że dmoże to być tylko 0 lub 1, więc:

for d = 0
1  d = 0 + d    =>    1  0 = 0 + 0    =>    1 = 0 (not possible)

for d = 1
1  d = 0 + d    =>    1  1 = 0 + 1    =>    0 = 1 (not possible)

Można zauważyć, że XOR zachowuje się jak suma binarna (z tą różnicą, że XOR nie tworzy przeniesienia dla następnej sumy bitowej):

    XOR           SUM
0  0 = 0  |   0 + 0 = 0
0  1 = 1  |   0 + 1 = 1
1  0 = 1  |   1 + 0 = 1
1  1 = 0  |   1 + 1 = 0

więc nie zawsze będzie możliwe znalezienie X, który spełnia A ⊕ X = B + X, ponieważ nie ma wartości, dktóra spełnia 1 + d = 0 + d.

W każdym razie, jeśli X istnieje, możesz to po prostu znaleźć w ten sposób, od prawej do lewej, znajdując krok po kroku.


PRACUJ PEŁNY PRZYKŁAD

A = 15, B = 7:

A = 1 1 1 1           B = 0 1 1 1
X = a b c d           X = a b c d

1  d = 1 + d 

W tym przypadku obowiązują zarówno d = 0, jak i d = 1. Musimy sprawdzić następny bit. Załóżmy, że d = 1:

A = 1 1 1 1           B = 0 1 1 1
X = a b c d           X = a b c d

1  d = 1 + d    =>    1  1 = 1 + 1    =>    0 = 0 (possible)

BUT 1 + 1 = 0 generates a carryover for the next bit sum:

Instead of 1  c = 1 + c, we have 1  c = 1 + c (+1) =
                                   1  c = c  (not possible)

więc w tym przypadku d musi wynosić 0.

carryover                              0
         A = 1 1 1 1           B = 0 1 1 1
         X = a b 0 0           X = a b 0 0
        -----------------------------------
                   0                     0

we know that c must be 0:

carryover                            0 0
         A = 1 1 1 1           B = 0 1 1 1
         X = a b 0 0           X = a b 0 0
        -----------------------------------
                 1 1                   1 1

ale co z b? jak zwykle musimy sprawdzić następny bit:

if b = 0, there won't be a carryover, so we'll have:

1  a = 0 + a  (and this is not possible)

so we try b = 1:

1  b = 1 + b    =>    1  1 = 1 + 1    =>    0 = 0 (with carryover)

a teraz dla a:

carryover                          1 0 0
         A = 1 1 1 1           B = 0 1 1 1
         X = a 1 0 0           X = a 1 0 0
        -----------------------------------
               0 0 0                 0 0 0


1  a = 0 + a (+1)    =>    1  a = 1 + a

tutaj amoże być 0 i 1, ale musi to być 0, aby uniknąć przeniesienia w sumie B + X.

Zatem, X = 0 1 0 0więc X = 4.


KOD

#include <iostream>
using namespace std;

inline int bit(int a, int n) {
    if(n > 31) return 0; 
    return (a & ( 1 << n )) >> n; 
}

int main(){
    int A = 19;
    int B = 7;

    int X = 0;
    int carryover = 0;
    int aCurrent, aNext, bCurrent, bNext;

    for(int i = 0; i < 32; i++){
        aCurrent =  bit(A, i);      bCurrent =  bit(B, i);
        aNext =     bit(A, i + 1);  bNext =     bit(B, i + 1);

        if(aCurrent == 0 && bCurrent == 0){
            if(carryover) {X = -1; break;}
            if(aNext != bNext){
                X += 1 << i;
            }
            carryover = 0;
        }
        else if(aCurrent == 0 && bCurrent == 1){
            if(!carryover) {X = -1; break;}
            if(aNext == bNext){
                X += 1 << i;
            }
            carryover = 1;
        }
        else if(aCurrent == 1 && bCurrent == 0){
            if(!carryover) {X = -1; break;}
            if(aNext != bNext){
                X += 1 << i;
                carryover = 1;
            }
            else {
                carryover = 0;
            }
        }
        else if(aCurrent == 1 && bCurrent == 1){
            if(carryover) {X = -1; break;}
            if(aNext != bNext){
                X += 1 << i;
                carryover = 1;
            }
            else {
                carryover = 0;
            }
        }

    }

    if(X != -1) cout<<"X = "<<X<<endl;
    else cout<<"X doesnt exist"<<endl;

    return 0;
}

Możesz to przetestować tutaj .

Daniel
źródło