1. 位运算算法专题概述在算法竞赛和面试准备中位运算因其独特的运算特性和极高的执行效率始终占据着特殊地位。这个专题将系统梳理LeetCode中经典的位运算问题解法从基础操作到高阶技巧层层递进。不同于普通的算术运算位运算直接对整数在内存中的二进制表示进行操作这种原子级的操作方式使得它在处理特定类型问题时具有无可比拟的优势。我最初接触位运算是在解决一个简单的判断奇偶问题时当看到别人用n 1替代n % 2的写法时那种惊艳感至今难忘。后来在解决更复杂的问题如只出现一次的数字、二进制中1的个数时才真正体会到位运算的精妙之处——它往往能用O(1)的时间复杂度解决看似复杂的问题。2. 位运算核心操作精解2.1 基础运算符全景位运算包含六种基本操作每种都有其独特的应用场景# 按位与()两位同时为1时结果为1 0b1100 0b1010 0b1000 # 12 10 8 # 按位或(|)任意一位为1时结果为1 0b1100 | 0b1010 0b1110 # 12 | 10 14 # 按位异或(^)两位不同时结果为1 0b1100 ^ 0b1010 0b0110 # 12 ^ 10 6 # 按位取反(~)所有位取反 ~0b1100 -0b1101 # ~12 -13 (补码表示) # 左移()所有位向左移动低位补0 0b1100 2 0b110000 # 12 2 48 # 右移()所有位向右移动 0b1100 2 0b0011 # 12 2 3特别注意右移操作在多数语言中是算术右移保留符号位但在某些场景下可能是逻辑右移高位补0。Python中的右移是算术右移。2.2 高频位操作技巧实际编码中以下位操作技巧需要熟练掌握判断奇偶n 1比n % 2快约50%交换两个数a ^ b; b ^ a; a ^ b无需临时变量取最低位的1lowbit x -x补码特性消除最低位的1x x (x - 1)Brian Kernighan算法判断是否为2的幂(x (x - 1)) 0绝对值运算mask x 31; (x ^ mask) - mask这些技巧在LeetCode题目中频繁出现例如n (n-1)这个操作在191. 位1的个数和231. 2的幂中都是核心解法。3. LeetCode经典题型解析3.1 基础应用题型136. 只出现一次的数字这是位运算最经典的入门题给定非空整数数组除了某个元素只出现一次外其余每个元素均出现两次。找出那个只出现一次的元素。def singleNumber(nums): res 0 for num in nums: res ^ num return res这个解法利用了异或运算的三个性质任何数和0异或都是它本身任何数和自身异或都是0异或运算满足交换律和结合律时间复杂度O(n)空间复杂度O(1)是最优解法。3.2 中等难度题型201. 数字范围按位与给定范围[m, n]返回此范围内所有数字的按位与结果。暴力解法是从m到n逐个做与运算但当范围很大时如0到2147483647会超时。高效解法是找到m和n的公共前缀def rangeBitwiseAnd(m, n): shift 0 while m ! n: m 1 n 1 shift 1 return m shift这个解法的关键在于范围内的数字按位与的结果就是这些数字的二进制表示的公共前缀后面的位会因为连续数字的变化而被抵消为0。3.3 高阶综合题型371. 两整数之和不使用运算符和-计算两整数之和。def getSum(a, b): MASK 0xFFFFFFFF MAX 0x7FFFFFFF while b ! 0: carry (a b) 1 a (a ^ b) MASK b carry MASK return a if a MAX else ~(a ^ MASK)这个解法模拟了硬件加法器的实现原理异或运算得到无进位和与运算后左移得到进位值循环直到没有进位处理Python的整数溢出问题32位整数模拟4. 位运算优化技巧进阶4.1 状态压缩与位掩码位运算在状态压缩方面有独特优势例如78. 子集给定一组不含重复元素的整数数组nums返回所有可能的子集。def subsets(nums): n len(nums) res [] for mask in range(1 n): subset [] for i in range(n): if mask (1 i): subset.append(nums[i]) res.append(subset) return res这里用n位二进制数表示每个元素的选取状态总共有2^n种可能。这种方法比回溯更直观但当n较大时20会受限于内存。4.2 位图算法应用187. 重复的DNA序列找出DNA分子中所有出现超过一次的10-letter长的序列。def findRepeatedDnaSequences(s): L, n 10, len(s) if n L: return [] # 将ACGT映射为2位二进制 to_int {A: 0, C: 1, G: 2, T: 3} nums [to_int.get(s[i]) for i in range(n)] bitmask 0 seen, output set(), set() for start in range(n - L 1): if start 0: for i in range(L): bitmask 2 bitmask | nums[i] else: bitmask 2 bitmask | nums[start L - 1] bitmask ~(3 2 * L) # 清除高位 if bitmask in seen: output.add(s[start:startL]) seen.add(bitmask) return list(output)这个解法将DNA序列编码为20位整数每个碱基2位利用位掩码实现滑动窗口空间效率极高。5. 位运算的边界问题与调试技巧5.1 常见陷阱与解决方案符号位问题右移操作在负数时的行为可能不符合预期解决方案明确使用逻辑右移或算术右移整数溢出Python整数无固定位数而其他语言如Java/C需要考虑解决方案使用掩码限制位数如 0xFFFFFFFF运算符优先级位运算符优先级通常低于比较运算符解决方案多用括号明确优先级5.2 调试位运算的实用方法二进制打印函数def print_binary(num, bits32): print(bin(num (2**bits-1))[2:].zfill(bits))分步验证法将复杂位操作拆解为多个步骤逐步验证边界测试特别注意0、-1、INT_MAX、INT_MIN等边界值6. 位运算在算法竞赛中的高阶应用6.1 快速幂算法计算a^b mod m的高效算法def quick_pow(a, b, m): res 1 a a % m while b 0: if b 1: res (res * a) % m a (a * a) % m b 1 return res这个算法将时间复杂度从O(n)降到O(logn)是许多数论问题的基础。6.2 布隆过滤器实现布隆过滤器是一种空间效率极高的概率型数据结构import mmh3 # MurmurHash3 class BloomFilter: def __init__(self, size, hash_count): self.size size self.hash_count hash_count self.bit_array 0 def add(self, string): for seed in range(self.hash_count): index mmh3.hash(string, seed) % self.size self.bit_array | (1 index) def contains(self, string): for seed in range(self.hash_count): index mmh3.hash(string, seed) % self.size if not (self.bit_array (1 index)): return False return True虽然这个简化实现用单个整数代替了位数组但展示了位运算在概率数据结构中的核心作用。7. 位运算与其他算法的结合应用7.1 动态规划中的状态压缩847. 访问所有节点的最短路径这是一个典型的旅行商问题(TSP)变种可以用状态压缩DP解决def shortestPathLength(graph): n len(graph) target (1 n) - 1 queue deque((i, 1 i) for i in range(n)) visited set(queue) steps 0 while queue: for _ in range(len(queue)): node, state queue.popleft() if state target: return steps for neighbor in graph[node]: new_state state | (1 neighbor) if (neighbor, new_state) not in visited: visited.add((neighbor, new_state)) queue.append((neighbor, new_state)) steps 1 return -1这里用二进制数的每一位表示是否访问过对应节点大大节省了空间。7.2 位运算优化搜索算法51. N皇后问题传统回溯解法时间复杂度高可以用位运算加速def solveNQueens(n): def backtrack(row, cols, diags, anti_diags, state): if row n: res.append([.join(row) for row in state]) return for col in range(n): curr_diag row - col curr_anti_diag row col if (cols (1 col)) or \ (diags (1 curr_diag)) or \ (anti_diags (1 curr_anti_diag)): continue state[row][col] Q backtrack(row1, cols | (1 col), diags | (1 curr_diag), anti_diags | (1 curr_anti_diag), state) state[row][col] . res [] empty_board [[.]*n for _ in range(n)] backtrack(0, 0, 0, 0, empty_board) return res这种解法通过位运算快速判断位置是否可用比传统的数组检查更高效。8. 位运算实战经验总结在实际编码面试中位运算问题往往考察以下几个方面的能力基础操作熟练度能否快速写出各种位操作问题转化能力能否将问题转化为位运算可解决的模式边界处理意识特别是负数、溢出等特殊情况效率优化思维如何用位运算替代普通运算提升性能我建议按照以下步骤系统准备位运算题目熟练掌握所有基本操作和常用技巧分类刷题基础应用、数学性质、状态压缩等总结每种题型的解题模板特别注意Python与其他语言在位运算上的差异对于想深入理解位运算的读者推荐研究《Hackers Delight》这本书它包含了大量精妙的位操作技巧。在实际工程中位运算常用于以下场景高性能计算如图形处理、密码学嵌入式开发寄存器操作压缩存储如位图索引算法优化如快速幂、状态压缩最后分享一个调试位运算问题的小技巧当结果不符合预期时把关键变量的二进制表示打印出来往往能快速定位问题所在。位运算就像算法的微积分虽然学习曲线较陡但一旦掌握就能在解决特定问题时展现出惊人的威力。