Algorithmus, um eine Lösung für A xor X = B + X zu finden

46

Suchen Sie bei gegebener Ganzzahl A und B die Ganzzahl X, damit:

  • A, B <2 * 1e18
  • A x oder X = B + X.

Ich bezweifle sehr, dass es möglich ist, diese Gleichung mit Mathematik zu lösen. Dies ist ein Codierungsproblem, auf das ich vor 3 Jahren gestoßen bin, und selbst jetzt kann ich es nicht selbst lösen.

Mein bisheriger Code: (Dies ist die Brute-Force-Lösung.)

#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
quelle
11
Wenn Sie ein bisschen mehr über Exklusiv lesen oder die algebraische Äquivalenz finden sollten a xor b = a + b mod 2. Versuchen Sie, eine Weile über diese Äquivalenz nachzudenken.
Ein Programmierer
16
@Someprogrammerdude Das ist, wenn a und b boolesche Variablen sind, dh entweder 0 oder 1, und xor ein boolesches xor ist. Was ist die Verbindung zu bitweisem xor?
John Kugelman
1
fwiw, ich denke, hier ist Brute Force der richtige Weg, es sei denn, Sie möchten etwas schreiben, das allgemeinere Gleichungen beweisen kann. Bedenken Sie, dass Sie Ihren Code testen müssen, um sicherzugehen, dass er korrekt ist. Am einfachsten ist es, ihn gegen einen Brute-Force-Algorithmus zu testen. Dann können Sie die Brute-Force-Methode jedoch zuerst verwenden. Auf der anderen Seite macht es das Anwenden von Mathematik irgendwann unnötig, Code auszuführen.
idclev 463035818
1
@molbdnilo Oh, einer der Kommentare deutete darauf hin, dass a xor b = a + b mod 2 und ich dachte, dass es sich auch um ganze Zahlen handelt. Ich werde diesen Teil meines Beitrags entfernen.
AAaAa
1
@ JohnKugelman Er meinte das mod 2wie in der Mathematik (Mod 2), dh 3 === 7 (Mod 2). Der Punkt ist, dass Sie eine Gleichung für das erste Bit von X entdecken und dann zum nächsten Bit übergehen können, wo Sie (unter Berücksichtigung des Übertrags) eine Gleichung für das zweite Bit usw. erhalten, wie Daniels Antwort.
Max Langhof

Antworten:

45

Beachten Sie das A + X == (A xor X) + ((A and X)<<1). Damit:

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

Und wir haben:

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

Wenn die Bedingung erfüllt ist, ist für jede ganze Zahl Y, die keine in A gesetzten Bits hat, (((A - B) >> 1) oder Y) eine Lösung. Wenn Sie nur eine Lösung wünschen, können Sie ((A - B) >> 1) verwenden, wobei Y = 0. Andernfalls gibt es keine Lösung.

int solve(int a, int b){
    int x = (a - b) >> 1;
    if ((a ^ x) == b + x)
        return x;
    else
        return ERROR;
}
user23013
quelle
15
+1. Dies geschieht durch die Feststellung, dass dies A xor X"Addition ohne Übertrag" und ((A and X)<<1)"Übertragung in der Addition" ist. Da A + Xes sich um "Addition mit Übertrag" handelt, ist die erste Gleichung sinnvoll.
Nur die Hälfte des
3
(A and X)<<1ist im Grunde 2*(A and X)und weil dies gleich ist, A-Bheißt es, dass das Problem nur dann eine Lösung haben kann, wenn A und B beide ungerade oder beide Ereignisse sind.
Axiac
1
Ich dachte, es hätte etwas mit Subtraktion zu tun, aber ich bin nicht rechtzeitig dazu gekommen.
SS Anne
38

Es ist nicht sehr schwer, man muss nur klein denken muß: Angenommen , wir schreiben A, Bund Xin binären und Aᵢist der Wert auf den äußersten rechten 2 entsprechenden Bit.

Wir wissen das : Aₒ ⊕ Xₒ = Bₒ + Xₒ.

Lassen Sie uns anhand eines Beispiels herausfinden, wie dies bewertet werden kann: A = 15 und B = 6. Konvertieren in Binär:

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

Jetzt haben wir einige Möglichkeiten. Lassen Sie uns die am weitesten rechts liegenden Teile von A und B analysieren:

1  d = 0 + d

Wir wissen, dass ddas nur 0 oder 1 sein kann, also:

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)

Es fällt auf, dass sich XOR genau wie eine binäre Summe verhält (mit dem Unterschied, dass XOR keine Übertragung für die nächste Bitsumme erzeugt):

    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

Daher ist es nicht immer möglich, ein X zu finden, das erfüllt A ⊕ X = B + X, da es keinen Wert gibt d, der erfüllt 1 + d = 0 + d.

Wenn X existiert, können Sie es auf diese Weise von rechts nach links herausfinden und Stück für Stück finden.


VOLLSTÄNDIGES ARBEITSBEISPIEL

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 

Hier gelten sowohl d = 0 als auch d = 1, was dann? Wir müssen das nächste Bit überprüfen. Angenommen, 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)

In diesem Fall muss d also 0 sein.

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

aber was ist mit b? wir müssen wie immer das nächste Bit überprüfen:

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)

und jetzt für 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

hier akann 0 und 1 sein, aber es muss 0 sein, um eine Verschleppung in der Summe zu vermeiden B + X.

Dann ist X = 0 1 0 0also X = 4.


CODE

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

Sie können es hier testen .

Daniel
quelle