二进制 & 位运算

python 运算符优先级

运算符	描述
**	指数 (最高优先级)
~ + -	按位翻转, 一元加号和减号 (最后两个的方法名为 +@ 和 -@)
* / % //	乘，除，取模和取整除
+ -	加法减法
>> <<	右移，左移运算符
&	位 'AND'
^ |	位运算符
<= < > >=	比较运算符
<> == !=	等于运算符
= %= /= //= -= += *= **=	赋值运算符
is is not	身份运算符
in not in	成员运算符
not and or	逻辑运算符

---

二进制位运算

运算符	说明
<<	按位左移，左移n位相当于乘以2的n次方
>>	按位右移 ，左移n位相当于除以2的n次方
&	按位与，同1为1
l	按位或 ，有1为1，没1为0
^	按位异或xor （exclusive OR） ，同为0，异为1
~	按位取反，二进制位0和1结果位互换

异或 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/