位运算枚举子集

位运算

说明

反复计算 (sub−1)&mask 可枚举非零子集；枚举一个掩码耗时 O(2^k)。

分析

给定 mask，(sub−1)&mask 会得到下一个更小且只包含原掩码置位的子集。循环直到 sub 为零，能枚举全部非空子集。

图解推演

mask=101 时可使用第 0、2 位，非空子掩码依次为 101、100、001。减一会借位并填充低位，再与 mask 交集，清除不属于原集合的位。若需要空集，必须另行输出 0；在 0 上继续执行公式会重新回到 mask，造成循环。

查看图表代码

适用前提与边界

包含 k 个置位时共有 2ᵏ−1 个结果，指数增长仍然不可避免。

示例输入与调用

fmt.Println(Submasks(0b101))

运行输出

[5 4 1]

完整 Go 示例

package main

import "fmt"

func Submasks(mask uint) []uint {
	out := []uint{}
	for sub := mask; sub > 0; sub = (sub - 1) & mask {
		out = append(out, sub)
	}
	return out
}

func main() {
	fmt.Println(Submasks(0b101))
}