c - 繰り返し要素の XOR 演算子の配列で、繰り返しのない 2 つの要素を見つけますか?

Question

2n+2 要素の配列があるとします。配列の n 要素が 2 回出現し、残りの 2 つの要素は一意です。これを O(n) 時間と O(1) 空間で解決する必要があります。解決策の 1 つは、XOR を使用することです。しかし、私はそれを理解することができません。誰かがそれに関して私を助けてくれますか、それともより良い解決策を教えてくれますか?

問題と解決策のリンクはこちら

Answer 1

a xor a == 0まず、それぞれについて注意してくださいa。

2 つの一意の番号があるとします - x,y.

各要素に対して xor を実行すると、1 つの数値が得られます。これはx xor y(各重複ペアがそれ自体を無効にするため) 等しく、少なくとも 1 ビット「アップ」しています。このビットを選択し (1 つ以上のビットがある場合は、どのビットを使用してもかまいません)、リストを 2 つのサブリストに分割します。
(1) このビットが設定されているすべての数値。
(2) このビットが設定されていないすべての数値。

一意の番号の 1 つにはこのビットがあり、もう 1 つにはありません (それ以外の場合は、そもそも「アップ」ではありませんでした)。そのため、各リストには 1 つの一意の番号があります。

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