繰り返し要素XOR演算子の配列内の2つの非繰り返し要素を検索しますか？

Question

2n + 2要素の配列があるとします。配列内のn個の要素は2回発生し、残りの2個の要素は一意です。あなたはO（n）時間とO（1）空間でこれを解決しなければなりません。解決策の1つがXORを使用しています。しかし、私はそれを理解することができません。誰かがそれについて私を助けることができる、または私にはより良い解決策を与えることができる？問題と解決策の

リンクはthis

Answer 1

まずある - 各aのために、そのa xor a == 0に注意してください。

2つの固有の番号（x,y）があるとします。

各要素でxorを実行すると、x xor yになります（各デュプリケートペア自体が無効になるため）。少なくとも1つのビットが「上」になります。このビットを選択します（複数のビットがある場合は、どのアップビットを使用するかは関係ありません）。
（1）このビットが設定されているすべての数値。
（2）このビットが設定されていないすべての番号。ユニークな数字の

一つは、このビットを持って、他はありません（そうでない - それは、最初の場所で「UP」ではなかった）ので、あなたは、各リスト内の1つの一意の番号を持っています。

各リストをもう一度繰り返し、すべての要素に対してxorを実行すると、結果はそれぞれの重複するペアが無効になるため、このリスト内の一意の数になります。