Dato uno XOR e SUM di due numeri, come trovare il numero di coppie che li soddisfano?

Question

Penso che la domanda potrebbe essere un po 'confusa. Quindi, proverò a spiegarlo prima.

Diciamo che XOR e SUM di due numeri sono dati. (Si noti che ci sono coppie multiple che possono soddisfare questo.)

Ad esempio, se XOR è 5 e la somma è 9 ci sono 4 coppie soddisfano SUM e XOR. Sono (2, 7), (3, 6), (6, 3), (7, 2). Quindi 2+7=9 e 2^7=5.

Voglio solo trovare il numero di coppie che soddisfa SUM e XOR. Quindi nell'esempio che ho citato è sufficiente la risposta 4. Non ho bisogno di sapere quali coppie li soddisfano.

Ho preso questo problema da here.

Ho controllato la risposta here. Fornisce una soluzione O (n) che non è sufficiente.

C'è un editoriale che fornisce la soluzione a questo problema. Può essere trovato here. (Cerca la soluzione di 627A)

Il problema è che non riesco a capire la soluzione. Da quello che ho potuto riassumere hanno usato una formula come questo,
(Se ci sono due numeri a e b) poi, a+b = (a XOR b) + (a AND b)*2

Come posso arrivare a questo? Il resto dei passaggi non mi è chiaro.

Se qualcuno può fornire un'idea su come risolvere questo o spiegare la sua soluzione, per favore aiutatemi.

Answer 1

Pensate a+b = (a XOR b) + (a AND b)*2 come esattamente ciò che succede quando si fanno somma binaria. Dal tuo esempio, a = 010 e b = 111:

010 
111 
--- 
1001 = 101 + 100 

per ogni bit, si aggiungono i bit da a e b (0+0=0, 0+1=1, 1+0=1, 1+1=0, che è esattamente a XOR bpiù il carry-in bit dal precedente Inoltre, se entrambi i bit precedenti per a e b sono 1, quindi lo aggiungiamo anche. Questo è esattamente (a AND b)*2. (Ricorda che la moltiplicazione per 2 è uno spostamento a sinistra.)

Con questa equazione possiamo calcolare a AND b.

Ora per contare il numero desiderato, esaminiamo ogni bit di a XOR b e uno per uno e moltiplica tutte le possibilità. (Lasciatemi scrivere a[i] per la i po '-esimo di a)

• Se a[i] XOR b[i] = 0 e a[i] AND b[i] = 0, quindi a[i] = b[i] = 0. Una sola possibilità per questo bit.

• Se a[i] XOR b[i] = 0 e a[i] AND b[i] = 1, quindi a[i] = b[i] = 1. Una sola possibilità per questo bit.

• Se a[i] XOR b[i] = 1 e , quindi a[i] = 1 e b[i] = 0 o viceversa. Due possibilità

• Non è possibile avere a[i] XOR b[i] = 1 e a[i] AND b[i] = 1.

dal vostro esempio, a XOR b = 101 e a AND b = 010. Abbiamo la risposta 2*1*2 = 4.

Answer 2

a AND b sono i bit che si trovano in entrambi i numeri. Quindi questi sono raddoppiati nella somma. a XOR b sono i bit che sono presenti solo in uno dei numeri, quindi questi devono essere conteggiati una sola volta nella somma.

Ecco un esempio:

• 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

Nota sull'ultima riga come il bit che è in entrambi i numeri (2^2) è conteggiato due volte nella somma mentre il resto viene conteggiato una sola volta!

Per risolvere il problema è necessario trovare tutte le coppie (a, b) che sommano alla somma. Quello che vuoi fare è questo:

1. Sottrarre il valore XOR dalla SUM. Ti rimane con 2*(a AND b).
2. Dividi per 2. Ora disponi di tutti i bit che devono essere impostati in a e b.
3. Dal momento che hai il valore XOR si sa esattamente cosa bit devono essere impostati in esattamente un di A e B, mentre la E valore che avete appena calcolati sono i bit che dovrebbero essere impostati in sia di essi. Quindi elenca tutte le permutazioni di impostazione dei bit rispettivamente in aeb.

per continuare la mia precedente esempio:

• a AND b = 0100 (impostato in entrambi sempre)
• a XOR b = 1001 (abbiamo bisogno di provare tutte le permutazioni di questi)

otteniamo queste permutazioni come soluzione:

• 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)