写在最前
计算机中，对数进行位操作，数以补码方式参与运算
&与操作
与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
