常见的位运算技巧有哪些？

Question

常见的位运算技巧有哪些？

Accepted Answer

**Bit manipulation** 使用 AND、OR、XOR、NOT 和移位直接对整数的二进制表示进行操作。它实现了紧凑、无分支和超快速的运算。 ## Core operations ```python x & 1 # is x odd? (lowest bit) x << 1 # multiply by 2 x >> 1 # integer divide by 2 x & (1 << k) # is bit k set? x | (1 << k) # set bit k x & ~(1 << k) # clear bit k x ^ (1 << k) # toggle bit k ``` ## Useful tricks ```python x & (x - 1) # clears the lowest set bit x & (x - 1) == 0 # is x a power of two? (x>0) x & (-x) # isolates the lowest set bit bin(x).count('1') # popcount (number of set bits) ``` ## 示例：找到单个数字（XOR 技巧） ```python def single_number(nums): result = 0 for n in nums: result ^= n # pairs cancel: a ^ a == 0 return result # the lone unpaired value remains single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## Complexity 位运算是 O(1)；上面的 XOR 扫描是 **O(n) time、O(1) space**。 ## 何时使用 / 注意事项用于 **bitmasks**（子集枚举、DP over states）、标志位、快速数学运算和低级/嵌入式代码。注意符号位、语言特定的移位行为和可读性——为非显而易见的技巧添加注释。 ## 为什么这很重要位运算产生优雅的 O(1) 空间解决方案（例如 XOR 单数字技巧），在面试中令人印象深刻。 Bitmask DP 使许多组合状态空间问题变得可行。它在系统、图形、压缩和性能关键代码中是必不可少的，其中每个周期都至关重要。