algorithm - 给定 n-1*n 数组，找到缺失的数字

Question

这里每一行都包含一个数字的位表示。这些数字来自1..N正好缺少一个数字。找到缺失数字的位表示。
面试官问了我这个问题。
我说:“我们可以找到给定数字的总和，然后从前 n 个数字的总和(我们知道为 (N*(N+1))/2) 中减去它”
他说这涉及从 10 进制更改为 2 进制。
你能告诉我如何在不改变碱基的情况下解决这个问题吗？

Answer 1

您可以XOR0..N范围内的所有数字，然后XOR范围内的数字大批。结果将是缺失的数字。

解释: XOR一个数字与它本身的结果总是零。上面的算法 XOR 将每个数字恰好两次，除了丢失的那个。缺失的数字将与零恰好进行一次异或，因此结果将等于缺失的数字。

注意:面试官关于需要转换基数才能进行加法的说法是错误的:添加二进制数既简单又有趣 - 事实上，计算机一直都在这样做:-)