[leetcode] 位运算

位运算这类题目奇思妙招很多，优化方法更是非常考验经验积累。

常用小技能：

1. bit_count()：返回整数的二进制表示中1的个数，e.g.

x = 7
x.bit_count() # 3

2.bit_length()：返回整数的二进制表示的长度，e.g.

x = 5
x.length() # 3

3.bin(x)[2:]：返回整数的二进制表示的字符串，[2:]是为了去除开头的0b，e.g.

x = 5
bin(x)  # 0b101
bin(x)[2:]  # 101

4.int(s, 2)：返回二进制表示的字符串对应的整数，e.g.

s = "111"
int(s, 2) # 7

5.统计每一位上1的个数：

nums = [1,2,3]
# 第32位是符号位
for i in range(31):
	cnt = sum(x>>i&1 for x in nums)

运算优先级

位运算题目中涉及大量的运算符级联，如果没有处理好运算优先级，结果会相差甚远。因此，要适时地添加括号。

1.指数运算符（**）
2.一元运算符（如 +、-、~）
3.乘法、除法、取模和整除（*、/、%、//）
4.加法和减法（+、-）
5.位移运算符（<<、>>）
6.位与运算符（&）
7.位异或运算符（^）
8.位或运算符（|）
9.比较运算符（如 <、<=、>、>=、==、!=）
10.身份运算符（is、is not）
11.成员运算符（in、not in）
12.逻辑运算符（not、and、or）
13.赋值运算符（如 =、+=、-=、*= 等）

一、基础题

3370. 仅含置位位的最小整数
3226. 使两个整数相等的位更改次数
1356. 根据数字二进制下 1 的数目排序
461. 汉明距离
2220. 转换数字的最少位翻转次数
1342. 将数字变成 0 的操作次数
476. 数字的补数
1009. 十进制整数的反码
868. 二进制间距
2917. 找出数组中的 K-or 值
693. 交替位二进制数
2657. 找到两个数组的前缀公共数组
231. 2 的幂
342. 4 的幂
191. 位 1 的个数
338. 比特位计数
2595. 奇偶位数
2154. 将找到的值乘以 2
3211. 生成不含相邻零的二进制字符串

# 3370. 仅含置位位的最小整数
class Solution:
    def smallestNumber(self, n: int) -> int:
        ans = 1 << n.bit_length()
        return (1 << n.bit_length()) - 1

本题的方法经常用来求与整数x二进制表示相同长度且各位都是1的数。注意，一定要加括号，减号优先级比<<高，不加括号求值顺序是错的。

# 461. 汉明距离
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return (x^y).bit_count()

本题的方法经常用来求两个整数二进制表示中不同位的个数

# 476. 数字的补数
class Solution:
    def findComplement(self, num: int) -> int:
        return ((1<<num.bit_length())-1)^num

本题的方法经常用来求与整数x的二进制表示中各位相反的数

# 2917. 找出数组中的 K-or 值
class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        mx=max(x.bit_length() for x in nums)
        ans=0
        for i in range(mx):
            cnt=sum(x>>i&1 for x in nums)
            if cnt>=k:
                ans|=1<<i
        return ans

本题是求数组中所有数的每一位上1的总数的经典做法

可以看出，位运算的题目虽然总是可以通过逐个遍历各个位上的值来解决，但如果能巧用位运算，可以极大地提升效率。

二、异或(XOR)

异或(XOR)常用的性质有：

1. a ⊕ a = 0
2. a ⊕ b = c
   ==> a = c ⊕ b
3. 扩展到多个数：
   假设An = a[1] ⊕ a[2] ⊕ … ⊕ a[n]
   那么 a[n] = An ⊕ Am (其中，m = n-1)

1486. 数组异或操作
1720. 解码异或后的数组
2433. 找出前缀异或的原始数组
1310. 子数组异或查询
2683. 相邻值的按位异或

# 1720. 解码异或后的数组
class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        m=len(encoded)
        ans=[first]+[0]*m
        for i in range(1,m+1):
            ans[i]=ans[i-1]^encoded[i-1]
        return ans

题目中，encoded[i] = arr[i] XOR arr[i + 1]，那么可得：arr[i] = encoded[i-1] XOR arr[i-1]

# 2433. 找出前缀异或的原始数组
class Solution:
    def findArray(self, pref: List[int]) -> List[int]:
        return [pref[0]]+[x^y for x,y in pairwise(pref)]

题目中，pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]，那么pref[i-1] = arr[0] ^ arr[1] ^ ... ^ arr[i-1]，可得：arr[i] = pref[i] ^ pref[i-1]

# 1310. 子数组异或查询
class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n=len(arr)
        pre=[arr[0]] + [0]*(n-1)
        # 前缀异或
        for i in range(1,n):
            pre[i]=arr[i]^pre[i-1]
            
        return [pre[r]^pre[l-1] if l>0 else pre[r] for l,r in queries]

三、与(&) 和 或(|)

“AND 的数越多，结果越小。OR 的数越多，结果越大。” - 灵神

2980. 检查按位或是否存在尾随零
1318. 或运算的最小翻转次数
2419. 按位与最大的最长子数组
2871. 将数组分割成最多数目的子数组
2401. 最长优雅子数组
2680. 最大或值
3133. 数组最后一个元素的最小值

# 2419. 按位与最大的最长子数组
class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        mx=max(nums)
        
        ans=cnt=0
        for x in nums:
            # 可能有多个子数组，子数组里都是最大值，要取最长的子数组
            if x==mx:
                cnt+=1
                ans=max(ans,cnt)
            else:
                cnt=0
        return ans

这题要求按位与最大的值，那肯定是最大值跟最大值自己与最大了，所以就是求全是由最大值组成的子数组的最大长度。注意，可能会有多个全是由最大值组成的子数组，我们要找出其中长度最大的。

# 2401. 最长优雅子数组
class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        ans=all=left=0
        for i,x in enumerate(nums):
            while all&x:
                # 通过异或把左边界删掉
                all^=nums[left]
                left+=1
            all|=x
            ans=max(ans,i-left+1)
        return ans

本题巧妙地通过异或把窗口左边界的值删掉，通过或拓展窗口的右边界，太妙了！适合反复练习体会。

# 2680. 最大或值
class Solution:
    def maximumOr(self, nums: List[int], k: int) -> int:
        n=len(nums)
        # 后缀
        suf=[0]*n
        for i in range(n-2,-1,-1):
            suf[i]=suf[i+1]|nums[i+1]
            
        ans=pre=0
        for i,x in enumerate(nums):
            ans=max(ans,pre|x<<k|suf[i])
            pre|=x
        return ans

本题适合跟前后缀题目一起练习

# 3133. 数组最后一个元素的最小值
class Solution:
    def minEnd(self, n: int, x: int) -> int:
        ans, cnt = x, n-1
        i = 0
        while cnt:
            if x >> i & 1 == 0:
                if cnt & 1 == 1:
                    ans |= 1 << i
                cnt >>= 1
            i += 1
        return ans

本题要求数组的所有元素按位与的结果等于x，那就是说凡是x的二进制表示中是位1的，数组中所有元素对应的位置也必须是1。要求数组是严格递增的，那只能在x的二进制表示中位置是0的逐个置1。假设把x中位置是0的全部抽出来：…00000，那么逐个置1就是按照 0001, 0010, 0011, 0100, … 的顺序往上递增。因为x已经是数组中的最小值了，所以需要往上递增n-1次。那只要把n-1的二进制表示中1的位置按序或到x的位0位置就可以了。

整理自leetcode 灵神题单：https://leetcode.cn/discuss/post/3580371/fen-xiang-gun-ti-dan-wei-yun-suan-ji-chu-nth4/