シーケンス内に見つからない番号を見つける

Question

私はn個の整数のリストを与えられていて、これらの整数は1からnの範囲です。リストに重複はありません。しかし、整数の1つがリストにありません。欠落している整数を見つけなければなりません。

Example: If n=8 
I/P [7,2,6,5,3,1,8] 
O/P 4 

I am using a simple concept to find the missing number which is to get the 
sum of numbers 
     total = n*(n+1)/2 
And then Subtract all the numbers from sum. 

ただし、数値の合計が最大許容整数を超えた場合、上記の方法は失敗します。

だから私は、第二の溶液を検索し、次のように私は方法を見つけました：？

1) XOR all the elements present in arr[], let the result of XOR be R1. 
2) XOR all numbers from 1 to n, let XOR be R2. 
3) XOR of R1 and R2 gives the missing number. 

をこのメソッドが動作しているどのように.. R1とR2のXORは、上記の場合には不足している整数を見つけている方法？

Answer 1

、あなただけ

A XOR B = C => C XOR A = B 

ことを覚えておく必要があり、すぐに

(PARTIAL SUM) XOR (MISSING ELEMENT) = (TOTAL) => 
(TOTAL) XOR (PATIAL SUM) = (MISSING ELEMNT) 

だけXORの真理値表を書き留め、最初のプロパティを証明するためにすることを、次のとおりです。

A B | A XOR B 
0 0 | 0 
0 1 | 1 
1 0 | 1 
1 1 | 0 

真理値表：両方のビットが同じ場合、XORの結果は偽であり、真であるそうです。

XORのこのプロパティは、シンプルではないが単純な暗号化形式の候補になります。

Answer 2

まず、整数オーバーフローが発生した場合でも（元のメソッドをがintに収まっている場合でも）機能させることができます。

XOR方式については、R1 xor M == R2（ここではMが欠落していること）を確認してください。このことから、R1 xor M xor R2 == 0であり、したがってM == R1 xor R2である。

Answer 3

XOR作品0とあなたはそれを反転1とあなたがXORたびに少し、そしてあなたXORたびビットは、それは同じままですので。だから、すべてのデータをXORの結果として失われた番号を保存すると、すべての数字をXORという「否定的な」印象を与えます。 XORこれらの2つを合わせると、失われた番号が復元されます。あなたの質問に答えるために

Answer 4

物事を単純にするために、下位ビット（LOB）のXORを見てみましょう。 xを欠落した整数とする。

リストの各整数は、R1（LOB（R1））のLOBを1または0にします。

範囲内の各整数は、LOB（R2）に1または0を与えます。

ここで、LOB（R1）== LOB（R2）とします。 R2 == R2 XOR xのため、これはLOB（x）== 0 == LOB（R1）XOR LOB（R2）の場合にのみ発生します。 （LOB（R1）== LOB（R2））これは、LOB（x）== 1 == LOB（R1）XORの場合にのみ発生する可能性があります（1 xor1 = 0、0 xor0 = 0）

しかし、XORはビットごとに独立して計算されるため、下位ビットはすべてのビットに対して機能します。