二进制 & 位运算

python 运算符优先级

二进制位运算

异或 xor （exclusive OR）

同为0，异为1
也叫半加运算，其运算法则相当于不带进位的二进制加法

136. 只出现一次的数字

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

全员异或即可：
同0异1，成对出现的数字会抵消为0，结果就是出现了一次的数字

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

面试题56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

思路：
记两数为A B。所有数字异或的结果也就是 A^B 肯定不为 0，至少有一位是 1（A != B）
随便取一位不同点X，代表A,B在X这位上肯定是一个0一个1.
然后遍历数组，在X上为0的分一组，X上为1的分一组，就可以把A，B分到不同组中。
对这两组分别进行异或操作就能找到这两个数

算法：

1. 先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
2. 在异或结果中找到任意为 1 的位。
3. 根据这一位对所有的数字进行分组
4. 在每个组内进行异或操作，得到两个数字。

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        xor_all = 0
        for num in nums:
            xor_all ^= num          # = A ^ B
        div = 1
        while div & xor_all == 0:   # 该位为0
            div <<= 1               # 左移，直到找到第一个1, 就是AB的第一个不同点
        
        a, b = 0, 0
        for num in nums:
            if num & div:
                a ^= num            # 含有 div 的数
            else:
                b ^= num            # 不含 div 的数
        return [a,b]

Reference

[1] Python运算符 - 菜鸟教程
[2] https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-by-leetcode/