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;
}
a xor b = a + b mod 2
. Spróbuj pomyśleć o tej równoważności przez chwilę.mod 2
co 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.Odpowiedzi:
Zauważ, że
A + X == (A xor X) + ((A and X)<<1)
. Więc:I mamy:
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.
źródło
A xor X
jest to „dodanie bez przeniesienia” i((A and X)<<1)
„przeniesienie w dodatku”. PonieważA + X
jest to „dodawanie z przenoszeniem”, pierwsze równanie ma sens.(A and X)<<1
jest w gruncie rzeczy,2*(A and X)
a ponieważ jest to równeA-B
, mówi, że problem może być rozwiązany tylko wtedy, gdy A i B są zdarzeniami nieparzystymi lub oba.To nie jest bardzo trudne, po prostu trzeba myśleć mały: załóżmy, że piszesz
A
,B
aX
binarnie iAᵢ
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ą:
Teraz mamy kilka możliwości. Przeanalizujmy najbardziej prawe bity A i B:
Wiemy, że
d
może to być tylko 0 lub 1, więc: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):
więc nie zawsze będzie możliwe znalezienie X, który spełnia
A ⊕ X = B + X
, ponieważ nie ma wartości,d
która spełnia1 + 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:
W tym przypadku obowiązują zarówno d = 0, jak i d = 1. Musimy sprawdzić następny bit. Załóżmy, że d = 1:
więc w tym przypadku d musi wynosić 0.
ale co z b? jak zwykle musimy sprawdzić następny bit:
a teraz dla
a
:tutaj
a
może być 0 i 1, ale musi to być 0, aby uniknąć przeniesienia w sumieB + X
.Zatem,
X = 0 1 0 0
więc X = 4.KOD
Możesz to przetestować tutaj .
źródło