17

我得到了一个包含 n 个整数的列表，这些整数在 1 到 n 的范围内。列表中没有重复项。但是列表中缺少一个整数。我必须找到丢失的整数。 

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 如何找到丢失的整数？

4

4 回答 4

31

要回答你的问题，你只需要记住

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 的这一属性使其成为简单（但并非微不足道）加密形式的不错选择。

于 2013-08-20T13:05:53.280 回答
4

首先，即使存在整数溢出，您也可以使您的原始方法工作（只要n适合int）。

至于 XOR 方法，请注意R1 xor M == R2（M缺少的数字在哪里）。从这它遵循那R1 xor M xor R2 == 0和因此M == R1 xor R2。

于 2013-08-20T13:04:49.410 回答
4

之所以XOR有效，是因为每次您XOR使用1它时都会翻转它，并且每次XOR使用0它时都会保持不变。所以XORing 所有数据保存丢失的数字的结果给你 ing 所有数字的“负面”印象XOR。 XOR将这两个一起恢复您丢失的号码。

于 2013-08-20T13:05:33.413 回答
1

让我们看一下低位 (LOB) 的 XOR 以保持简单。令 x 为缺失的整数。

列表中的每个整数都对 R1 的 LOB (LOB(R1)) 贡献 1 或 0。

范围内的每个整数都对 LOB(R2) 贡献 1 或 0。

现在假设 LOB(R1) == LOB(R2)。由于 R2 == R2 XOR x，只有当 LOB(x) == 0 == LOB(R1) XOR LOB(R2) 时才会发生这种情况。(1 异或 1 = 0, 0 异或 0 = 0)

或者假设 (LOB(R1) == LOB(R2)。只有当 LOB(x) == 1 == LOB(R1) XOR LOB(R2) (1 xor 0 = 1, 0 xor 1 = 1) 时才会发生这种情况.

但是对低位有效的方法对所有这些都有效，因为 XOR 是独立计算的，逐位计算。

于 2013-08-20T13:11:48.480 回答