位运算
位运算不要背零散技巧，先抓住“位掩码就是一个超轻量状态数组”这个本质，再去套判断、压缩、分组和枚举四类问题。
核心思路
位运算题常见成分只有四种：
- 用
&判断某一位是不是 1。 - 用
|或^修改状态。 - 用
n & (n - 1)、n & -n提取最低位信息。 - 用
mask压缩一个集合或一个访问状态。
很多题看上去花哨，本质上都在回答两个问题：
- 我能不能用一个整数表示一组状态。
- 我能不能利用二进制性质把原来的
O(n)判断压到O(1)。
先记住的几个不变量
n & 1可以判断奇偶。n & (n - 1)会删掉最低位的一个1。n & -n会保留最低位的一个1。- 如果一个正整数是
2的幂，那么它的二进制里只会有一个1。 a ^ a = 0，a ^ 0 = a，所以异或特别适合“成对抵消”。
常用 Go 模板
基础位操作
func getBit(x, i int) int {
return (x >> i) & 1
}
func setBit(x, i int) int {
return x | (1 << i)
}
func clearBit(x, i int) int {
return x & ^(1 << i)
}
func isPowerOfTwo(n int) bool {
return n > 0 && (n&(n-1)) == 0
}
func countOnes(n int) int {
cnt := 0
for n != 0 {
n &= n - 1
cnt++
}
return cnt
}
func lowbit(n int) int {
return n & -n
}经典题：只出现一次的数字
func singleNumber(nums []int) int {
res := 0
for _, x := range nums {
res ^= x
}
return res
}这里的核心不是“异或很神奇”，而是“相同元素会两两抵消”。
位掩码枚举子集
func subsets(nums []int) [][]int {
n := len(nums)
res := make([][]int, 0, 1<<n)
for mask := 0; mask < (1 << n); mask++ {
path := make([]int, 0, n)
for i := 0; i < n; i++ {
if (mask & (1 << i)) != 0 {
path = append(path, nums[i])
}
}
res = append(res, path)
}
return res
}这个模板后面可以直接迁移到 状态压缩DP、TSP、集合搜索等题型。
常见题型
判断与构造
异或分组
状态压缩
易错点
位运算真正容易错的地方，不是公式本身，而是数据范围、符号位和语言细节。
- Go 里
^既是按位异或，也是单目按位取反，读代码时要分清上下文。 - 负数右移和补码细节容易出问题，做题时优先先把题目里的数据范围想清楚。
1 << n在n很大时可能溢出，状态压缩通常只适合n <= 20左右的题。- 用位掩码表示集合时，先约定“第
i位代表什么”，否则后面很容易写乱。
学习顺序
相关主题
返回：算法学习导航