异或的应用。（提取出数字中最右侧的1，面试中经常用的到）

我们都知道，在计算机系统中，所有数字的存储方式都是二进制，那么我们需要提取数字中的最右侧的1该怎么办呢？

一、背景

异或的应用十分的重要。比如当我们面试时，面试官问了一个问题：在一堆数字中，只有两个数字出现的次数为奇数次，其他的数字出现的次数都为偶数次，要求求出奇数次的数字a和b，要求时间复杂度O（N），额外空间复杂度O（1）.

二、解题思路

首先，我们需要异或一遍数组，这样得到的结果就是a^b，然后怎么算呢？
然后a^b肯定是不为0的，我们需要知道a或者b的数值就可以算出结果，那么怎么知道a或者b呢？
a和b在计算机的存储形式中都是以二进制的方式存储的，又因为a一定不等于b，所以我们知道a和b中的某一位绝对是不相同的。利用这个特点，假设我们找到最右侧的不相同的位（也就是a的那一位数字为0，而b的那一位数字为1，或者相反），那我们怎么找到最右侧的1呢？

right_one = arr & (~arr + 1)  # 提取最右侧的1

这行代码就很好的找到了最右侧的1，下面我来解释一下，首先arr的数值是a^b的结果，那么我们给这个结果取反，然后加1，此时的arr的最右侧的1就是答案。
比如arr的结果是000111001100.取反之后为111000110011，加上1之后为111000110100，那么此时的最右侧的1就是最终答案。
找到之后，我们可以利用这个来再次遍历数组，此时的结果就是a或者b，然后让这个结果异或arr，这样就得到了两个数字。

三、完整的代码

nums = [10, 10, 10, 5, 6, 6, 7, 7, 8, 8, 9, 9, 55, 55, 66, 66, 33, 33, 5, 888, 888, 888]
arr = 0
for i in range(len(nums)):
    arr ^= nums[i]   # 此时的arr为a^b

right_one = arr & (~arr + 1)  # 提取最右侧的1
eor = 0
for i in range(len(nums)):
    if nums[i] & right_one == 0:
        eor ^= nums[i]
print(f'两个数字为{
      eor}和{
      arr^eor}')

输出：

两个数字为888和10