配列からペアでない2つの数字を見つける。XOR

• ペアでない数字は2つ(x, y)あるという設定
• 例

Input: {12, 23, 34, 12, 12, 23, 12, 45}
Output: 34 and 45

• ソートすれば O(n log n)
• しかしO(n)の解法がある
• https://www.geeksforgeeks.org/find-the-two-numbers-with-odd-occurences-in-an-unsorted-array/

解法

• 全てのXORを求める。x xor yだけ残る
• a = x ^ y とする
• LSB (Least Significant Bit) a & -a を求める

a = 01010
-aは反転して1を足したものなので、-a = 10110
LSB = 00010

• x = 0
• y = 0
• の単位元から始めて、LSB & A[i]なものをxにXOR, その他をyにXORする
• x, y以外はペアなので打ち消され、x, yそのものだけが残る

x = 0;
y = 0;
for(i = 0; i < size; i++)  
{  
    if(A[i] & LSB){
        x = x ^ A[i];  
    }
    else{
        y = y ^ A[i];  
    }
}