Bei einer XOR und SUM von zwei Zahlen, wie finde ich die Anzahl der Paare, die sie erfüllen?

Question

Ich denke, die Frage mag ein wenig verwirrend sein. Also werde ich versuchen, es zuerst zu erklären.

Nehmen wir an, die XOR und SUM von zwei Zahlen sind gegeben. (Beachten Sie, dass es mehrere Paare sind, die dies erfüllen kann.)

Zum Beispiel, wenn die XOR 5 ist und die Summe wird 9 gibt es 4 Paare die Summen- und XOR erfüllt. Sie sind (2, 7), (3, 6), (6, 3), (7, 2). So 2+7=9 und 2^7=5.

Ich möchte nur die Nummer von Paaren finden, die die SUM und XOR erfüllt. Also in dem Beispiel, das ich erwähnte, ist die Antwort 4 genug. Ich muss nicht wissen, welche Paare sie erfüllen.

Ich nahm dieses Problem von here.

Ich überprüft für eine Antwort here. Es liefert eine O (n) Lösung, die nicht genug ist.

Es gibt ein Editorial, das die Lösung für dieses Problem bietet. Es kann here gefunden werden. (Suchen Sie nach der Lösung von 627A)

Das Problem ist, dass ich die Lösung nicht verstehen kann. Von dem, was ich zusammenfassen könnte sie eine Formel wie folgt verwendet,
(Wenn es zwei Zahlen a und b) dann, a+b = (a XOR b) + (a AND b)*2

Wie komme ich darauf? Der Rest der Schritte ist mir unklar.

Wenn jemand eine Idee zur Verfügung stellen könnte, wie man das löst oder ihre Lösung erklärt, bitte helfen Sie.

Answer 1

Denken Sie an a+b = (a XOR b) + (a AND b)*2 genau das, was passiert, wenn Sie Binäraddition tun. Von Ihrem Beispiel a = 010 und b = 111:

010 
111 
--- 
1001 = 101 + 100 

Für jedes Bit, fügen Sie Bits aus a und b (0+0=0, 0+1=1, 1+0=1, 1+1=0, das ist genau das, a XOR bund die Übertrags-Bit aus dem vorherigen Zusätzlich, dh wenn beide vorherigen Bits für a und b 1 sind, dann fügen wir es auch hinzu. Dies ist genau (a AND b)*2. (Denken Sie daran, dass die Multiplikation mit 2 eine Verschiebung ist.)

Mit dieser Gleichung können wir berechnen a AND b.

Jetzt, um die gewünschte Anzahl zu zählen, betrachten wir nacheinander alle Bits von a XOR b und a AND b und multiplizieren alle Möglichkeiten. (Lassen Sie mich schreiben a[i] für die i -te Bit von a)

• Wenn a[i] XOR b[i] = 0 und a[i] AND b[i] = 0, dann a[i] = b[i] = 0. Nur eine Möglichkeit für dieses Bit.

• Wenn a[i] XOR b[i] = 0 und a[i] AND b[i] = 1, dann a[i] = b[i] = 1. Nur eine Möglichkeit für dieses Bit.

• Wenn a[i] XOR b[i] = 1 und a[i] AND b[i] = 0, dann a[i] = 1 und b[i] = 0 oder umgekehrt. Zwei Möglichkeiten.

• Es ist nicht möglich a[i] XOR b[i] = 1 und a[i] AND b[i] = 1 zu haben.

Von Ihrem Beispiel a XOR b = 101 und a AND b = 010. Wir haben die Antwort 2*1*2 = 4.

Answer 2

a AND b sind die Bits, die in beiden Zahlen enthalten sind. Also diese sind in der Summe verdoppelt. a XOR b sind die Bits, die nur in einer der Zahlen vorhanden sind, daher sollten diese nur einmal in der Summe gezählt werden. Hier

ein Beispiel:

• a = 4 = 1*2^2 + 0*2^1 + 0*2^0 (or just 100)
• b = 13 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 (or just 1101)
• a + b = (1*2^2 + 0*2^1 + 0*2^0) + (1*2^3 + 1*2^2 + 0*2^1 + 1*2^0) = 1*2^3 + 2*2^2 + 0*2^1 + 1*2^0

Hinweis auf der letzten Zeile, wie das Bit, das sowohl in den Zahlen (2^2) zweimal gezählt in der Summe während der Rest nur einmal gezählt wird!

Um Ihr Problem zu lösen, müssen Sie alle Paare (a, b) finden, die sich zur Summe addieren. Was möchten Sie tun, ist dies:

1. Subtrahieren Sie den XOR-Wert von der SUMME. Sie sind mit 2*(a AND b) verlassen.
2. Division durch 2. Sie haben nun alle Bits, die in a und b gesetzt werden sollen.
3. Da haben Sie den XOR-Wert, den Sie genau wissen, was Bits in genau eine von a und b festgelegt werden sollte, während die UND-Wert, den Sie gerade berechnet sind die Bits, die in beid von ihnen eingestellt werden sollen. Sie listen also alle Permutationen auf, um die Bits in a bzw. b zu setzen.

Zu meinem vorherigen Beispiel fortzufahren:

• a AND b = 0100 (in beiden immer gesetzt) ​​
• a XOR b = 1001

Wir bekommen diese Permutationen (wir alle Permutationen von diesen versuchen müssen) als Lösung:

• a = 0100 + 0000 = 0100, b = 0100 + 1001 = 1101 => (4, 13)
• a = 0100 + 0001 = 0101, b = 0100 + 1000 = 1100 => (5, 12)
• a = 0100 + 1000 = 1100, b = 0100 + 0001 = 0101 => (12, 5)
• a = 0100 + 1001 = 1101, b = 0100 + 0000 = 0100 => (13, 4)