Trova i due elementi non ripetibili in una matrice di operatore XOR dell'elemento ricorrente?

Question

Supponiamo di disporre di un array con 2n + 2 elementi. n elementi nella matrice si verificano due volte e due elementi rimanenti sono unici. Devi risolverlo nel tempo O (n) e nello spazio O (1). Una delle soluzioni sta usando XOR. Ma non sono in grado di capirlo. Qualcuno può aiutarmi a riguardo o può darmi una soluzione migliore?

link del problema e la soluzione è this

Answer 1

In primo luogo - notare che a xor a == 0, per ogni a.

Supponiamo di avere due numeri univoci: x,y.

Se si esegue xor su ciascun elemento, si finisce con un numero singolo, che equivale a x xor y (poiché ogni coppia dupe annulla automaticamente) e ha almeno un bit "su". Scegli questo bit (Non importa quale bit prendi se ce ne sono più di uno) e dividi l'elenco in due sotto-elenchi:
(1) Tutti i numeri con questo bit impostato.
(2) tutti i numeri con questo bit disattivato.

Uno dei numeri univoci ha questo bit, l'altro no (altrimenti - non era "in alto" in primo luogo), quindi hai un numero univoco in ciascuna lista.

Iterate ogni elenco ancora una volta e eseguite xo su tutti gli elementi, il risultato è il numero univoco in questo elenco, poiché ciascuna coppia duplicata annulla automaticamente.