面接問題:異或去重

ソース:http://blog.csdn.net/ns_code/article/details/27568975
異或はバイナリベースのビット演算で、シンボルXORまたは^で表され、その演算アルゴリズムは演算子の両側数の各バイナリビットに対して、同値は0、異値は1をとる.ブール演算との違いは、演算子の両側が1の場合、ブール演算の結果は1であり、異または演算の結果は0である.

     ：         

1、   ：a^b = b^a；

2、   ：(a^b)^c = a^(b^c)；

3、     a：a^a=0，a^0=a，a^(-1)=~a。

以上のことを理解して、これを見て、とても重要で、後のプログラムはすべてこの結論を使います:もし複数の数が異なって、その中に繰り返しの数があるならば、これらの繰り返しの数が隣接しているかどうかにかかわらず、すべて異なった性質によってこれらの繰り返しの数を消去することができて、体にとって、繰り返しが偶数回現れたら、異なった後はすべて消去します.奇数回繰り返されると、例外は1つ残ります.
次の2つのテーマを見てみましょう.
1、1-1000は1001個の要素を含む配列に配置され、唯一の要素値のみが重複し、その他は1回しか現れない.各配列要素は一度しかアクセスできず、アルゴリズムを設計し、それを探し出すことができます.ストレージスペースを支援する必要がなく、アルゴリズムの実装を設計できますか?

  ，   ，           ，        ，  1+2+3+...+1000  ，
           ，        ，      ，        ，      ，      1000，       ，       。
          1-1000  n           ，   n     ，    1-1000  n         ，      n 。
             ，  T，      ：
T = 1^2^3^4...^n...^n...^1000 = 1^2^3...^1000（     n）
      T 1-1000       （     n）  ，
         n。    ：T^(a^2^3^4...^n...^1000) = T^(T^n) = 0^n = n

       。

しかし、この問題がこのように変化した後、1-1000とN(Nは任意の整数)は1001の要素を含む配列の中に置いて、最大1つの要素の値が繰り返して、その他はすべて1回しか現れなくて、Nの値を求めますか?答え:依然として上の2つの方法からできます.ただ异和を使うときは1^2...^1000と直接异和にするだけで结果が得られます.
2、1つの配列に1つの数字が1回しか現れず、他のすべてが2回現れ、この数字を求める.

            ，       ，             ，               ，               。

             ，      ：               ，          。