python异或运算

异或运算：

python自带的异或运算，可以分为三步：

• 把两个十进制整数转换成二进制，并让其长度相同（短的前面补0）；
• 将两个二进制数按位异或（相同时为1，不同时为0）；
• 将结果转换回十进制数，输出。

一个小应用：用异或，不用额外变量交换两个整数。

a = a ^ b
b = a ^ b
a = a ^ b

LeetCode问题461：汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数x和y，计算它们之间的汉明距离。

这题把x和y求异或，将结果转换为二进制，统计其中1出现的次数即可。

完整代码：

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        z = bin(x ^ y)[2:]
        count = 0
        for i in range(len(z)):
            if z[i] == '1':
                count += 1
        return count

运行结果：

LeetCode问题136：数组中唯一出现一次的元素

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

这题用异或，初始化re为0，将re与数组中全部元素异或一遍，则最后得到的值就是只出现一次的元素。

完整代码：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        re = 0
        for i in nums:
            re = re ^ i
        return re

运行结果：

LeetCode问题268：缺失数字

给定一个包含0, 1, 2, ..., n中n个数的序列，找出0, ..., n中没有出现在序列中的那个数。

这题用异或，初始化c为0，将c与数组中n个元素异或一遍，再与0到n这n+1个数全部异或一遍，则最后得到的值就是缺失的元素。

完整代码：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        c = 0
        for i in range(len(nums)):
            c ^= nums[i]
            c ^= i
        c ^= i+1
        return c

运行结果：