¿Busca los dos elementos no repetitivos en una matriz del operador XOR de elemento repetitivo?

Question

Supongamos que tengo una matriz con 2n + 2 elementos. n elementos en la matriz están ocurriendo dos veces y los dos elementos restantes son únicos. Tienes que resolver esto en O (n) tiempo y O (1) espacio. Una de las soluciones es usar XOR. Pero no soy capaz de entender eso. ¿Alguien puede ayudarme con eso o puede darme una mejor solución?

Enlace del problema y la solución es this

Answer 1

En primer lugar - en cuenta que a xor a == 0, para cada a.

Digamos que tiene dos números únicos: x,y.

Si haces xor en cada elemento, terminas con un solo número, que equivale a x xor y (porque cada par dupe se anula a sí mismo), y tiene al menos un bit "arriba". Elija este bit (no importa qué bit que tome si hay más de uno), y divida la lista en dos listas secundarias:
(1) Todos los números que tienen este bit establecido.
(2) todos los números que tienen este bit desarmado.

Uno de los números únicos tiene este bit, el otro no (de lo contrario, en primer lugar, no estaba "activo"), por lo que tiene un número único en cada lista.

Iterate cada lista una vez más, y hago xor en todos los elementos, el resultado es el número único en esta lista, ya que cada par duplicado se anula.