位運算這類題目奇思妙招很多，優化方法更是非常考驗經驗積累。

常用小技能：

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=0for i in range(mx):cnt=sum(x>>i&1 for x in nums)if cnt>=k:ans|=1<<ireturn 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]*mfor 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=0for x in nums:# 可能有多個子數組，子數組里都是最大值，要取最長的子數組if x==mx:cnt+=1ans=max(ans,cnt)else:cnt=0return ans

這題要求按位與最大的值，那肯定是最大值跟最大值自己與最大了，所以就是求全是由最大值組成的子數組的最大長度。注意，可能會有多個全是由最大值組成的子數組，我們要找出其中長度最大的。

# 2401. 最長優雅子數組
class Solution:def longestNiceSubarray(self, nums: List[int]) -> int:ans=all=left=0for i,x in enumerate(nums):while all&x:# 通過異或把左邊界刪掉all^=nums[left]left+=1all|=xans=max(ans,i-left+1)return ans

本題巧妙地通過異或把窗口左邊界的值刪掉，通過或拓展窗口的右邊界，太妙了！適合反復練習體會。

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

本題適合跟前后綴題目一起練習

# 3133. 數組最后一個元素的最小值
class Solution:def minEnd(self, n: int, x: int) -> int:ans, cnt = x, n-1i = 0while cnt:if x >> i & 1 == 0:if cnt & 1 == 1:ans |= 1 << icnt >>= 1i += 1return 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/