写在最前

计算机中，对数进行位操作，数以补码方式参与运算

&与操作

与0相与得0，与1相与为本身

• 1.实现对特定位清0

10001000最高位清0
10001000 & 01111111 = 00001000

• 2.取一个数的若干特定位数

10001000取低4位
10001000 ^ 00001111 = 00001000

• 3.tips

-n = ~n+1

源于：负数的补码 = 对应正数的反码 + 1

获取整数a的二进制中最后一个1: a & ( -a )

a = 6，-a = 1001 + 1 = 1010
a & -a = 0110 & 1010 = 0010，对应数为3

去掉整数a的二进制中最后一个1：a &(a-1)

a=0110，a-1=0101，a & ( a-1 )=0100

二进制数最高位1的索引位置

int c = -1;
while(n)
{
  n >>= 1;
  c++;
}

^异或操作巧用

A ^ B：当A、B相异且A或B为1时，A ^ B = 1，否则A ^ B = 0
异或就是先相异，再看或
按位异或的3个特点:

(1) 0^0=0,0^1=1  **0异或任何数＝任何数**
(2) 1^0=1,1^1=0  **1异或任何数 = 任何数取反**
(3) **任何数异或自己＝把自己置0**

• 1.自异或实现消偶

一个数num异或自身，等于0.。可以利用这个性质进行消偶
例1：
一个数组nums里只有一个数出现一次，其他数都出现2次，要求时间复杂度O(N)，空间复杂度O(1)求解
思路：利用异或的特性，遍历nums的所有元素，逐一异或，最后的值就是这个单次数

class Solution:
    def singleNumbers(self, nums: List[int]):
        res = 0
        for ele in nums:
            res = res ^ ele
        return res

例2：
一个数组nums里只有2个数出现一次，其他数都出现2次，要求时间复杂度O(N)，空间复杂度O(1)求解
思路：本题在上题的基础上多了一个单次数，那么大方向还是通过异或。但异或最后得到的值是两个单次数的异或值，得不到两个数，那么能不能转换成上一题的样子呢？假设一轮异或得到的值为res，这个res二进制下肯定有某些位值为1，而1就表示两个单次数a,b在这一位上不相等。那么我们以这一位为分类条件，该位上为1的分为一组，为0的分为另外一组，两组内部各自异或一轮，就得到答案了

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        res = 0
        for ele in nums:
            res = res ^ ele
        
        # 用res来分组, index标记从右往左最近的1的下标
        index = 0
        while res & 1 == 0:
            index += 1
            res >>= 1

        # 分组后两组内部分别再异或
        a, b = 0, 0
        for ele in nums:
            if ele & 2**index == 0:
                a ^= ele
            else:
                b ^= ele

        return [a, b]

• 2.不借助临时变量交换两个数的值

本质上是自异或

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

• 3.二进制数局部取反

利用与1异或等于取反

00110110右起第3\4位取反:
00110110 ^ 00001100 = 00111010