位运算技巧整理

判断x是否为 2 的幂

• (x&(x-1))
• 含义：去掉x最高位的1
• 0: 是 $2^n$ 其它：不是

「二进制枚举子集」

枚举二进制集合 x 的所有子集步骤：

• 令 sub 为当前枚举到的子集，初始时 sub=x
• 循环令 sub=(sub-1)&x，当 sub == 0 时枚举结束

示例代码

func main() {  
   x := 0b100111  
   for sub := x; sub != 0; sub = (sub - 1) & x {  
      fmt.Printf("%07b %d\n", sub, sub)  
   }  
}

lowbit

• x&(-x)
• 含义：仅保留最低位的1