状压枚举子集

发布时间 2023-10-31 16:46:35作者: muzqingt

状压枚举子集

状压枚举子集就是从右往左删除 \(1\) 的过程,删除一个 \(1\) 并把 \(1\) 右边的 \(0\) 变成 \(1\)

可以发现这就是状压后的数减 \(1\),与原集合进行按位与来去掉多余的 \(1\)

例如 \((10110)_2​\to(10100)_2​\to(10010)_2​\to(10000)_2​\to(110)_2​\to(100)_2​\to(10)_2​\)

code

//i为原集合,j为子集
for(int j=i;j;j=(j-1)&i)