我被要求从python中的一个数字列表中找出这个数字，这个列表中只存在一次。像往常一样，我可以用正常的方法很容易地解决它，然后马上就出来了：
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in nums:
if(nums.count(i) == 1):
return i
return nums[0]为了找到另一种更好的方法，internet建议我使用按位异或运算，并提供了以下更快、更高效的代码。代码如下：
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a = 0
for i in nums:
a^=i
print(a)
return a逻辑是，如果我们对两个相同的位（0,0或1,1）执行异或运算，答案将始终为0，如果位不同，答案将为1。利用这一点，它提出了这样一种方法。
我的头脑陷入了困境，试图意识到xor操作的正常概念在这里是如何有用的！我理解他们所说的相同和不同位的逻辑，但根据他们的代码，每次我对下一位执行异或运算时，都会弹出一个新的数字，那么我们如何保证只有出现一次的数字才会进化？
我感到不知所措。发布代码片段然后要求解释可能不是一个好方法，但我觉得这个解决方案非常有趣，我渴望了解按位异或是如何帮助解决的！如果有人有主意，请帮忙！提前谢谢。
注意：在列表中，除一个数字外，所有数字都出现两次。
3条答案
按热度按时间qfe3c7zg1#
此xor解决方案的一般约束有点不同：
您有一个列表，其中正好有一个数字出现奇数次，而所有其他数字出现偶数次，需要找到奇数。
如果位相同，则xor翻转位：
您有一个任意的起始值（列表中的第一个数字），例如：
如果所有其他数字出现偶数次，则每个位模式至少出现两次。
当你第一次有一对比特和
每0,1位翻转一次到1
每1,0位翻转1
每1,1位翻转一次到0
然后您再次遇到相同的数字（因为其中有偶数次）：
上次翻转后有1位，再次遇到1位，因此翻转为0
您上次翻转时有一个1位，再次遇到一个0位，所以您保持在1
上次翻转后有0位，再次遇到1位，因此翻转为1
现在您又回到了原来的数字，因为偶数次出现的数字会抵消：
如果你将任何其他数字与000000000进行异或运算，你会得到另一个数字。
nzrxty8p2#
异或运算的相关属性为：
它是关联的，所以
(a ^ b) ^ c == a ^ (b ^ c)它是可交换的，所以a ^ b == b ^ a它有0作为一个身份元素，所以a ^ 0 == 0 ^ a == a每个元素都是它自己的逆，所以a ^ a == 0因此，考虑当输入列表类似时会发生什么情况。[3, 4, 5, 4, 3]. 从前两个属性中，我们得到了(((3 ^ 4) ^ 5) ^ 4) ^ 3与(3 ^ 3) ^ (4 ^ 4) ^ 5，从第四个属性开始，这与0 ^ 0 ^ 5，从第三个属性中，结果为5. 实际上，每一个出现偶数次的元素都会与自身抵消，只留下出现一次（或奇数次）的元素。rhfm7lfc3#
我认为如果不知道xor操作的属性，就很难理解该代码的功能
这是xor操作的属性
如果位相同，则结果为0。如果位不同，则结果为1。
下表将给出上述xor属性的清晰概念。
您的问题的解决方案基于此概念。
xor的一个有趣特性是
当你对同一个数进行异或运算，偶数次你得到一个零
当你对同一个数字本身进行异或运算时，奇数次你就得到了这个数字本身
以数字2为例（二进制中的2是-0010）
让我们
执行2的异或运算（偶数次）
执行2的异或运算（奇数次）
偶数次出现的任何数字最终都将导致零和零XORD，奇数次出现的数字将给出相同的数字（奇数次出现）
原因是什么
a初始化为0是因为—0异或x将给予x它本身假设x=3
编辑-基于op的怀疑
输入
arr = [1,2,2,4,1]您会问为什么会得到任意值-1,3,1,5,4它们不是武断的。它们是之间异或运算的结果a及i.初始值
a= 0第一次迭代：i=1（0001）；a=0（0000）
第二次迭代：i=2（0010）；a=1（0001）
第三次迭代：i=2（0010）；a=3（0011）
第四次迭代：i=4（0100）；a=1（0001）
第五次迭代：i=1（0001）；a=5（0101）