枚举大小为k的子集
这种位操作不大可能分析出来，先看代码再分析。
代码
使用条件：\(k>0\)
void solve(int n,int k)
{
for(int comb = (1 << k) - 1; comb < (1 << n);)
{
// ...
int x = comb & -comb, y = comb + x;
comb = (((comb & ~y) / x ) >> 1) | y;
}
}证明
\[
\begin{array}{}
首先是辅助变量x,y\\
x \rightarrow comb最低位\\
y \rightarrow comb的倒数第一段1取0，该1段前一个位置的0取1\\
设上述y改变的部分为len\\
comb\&\sim y \rightarrow len前取0，len中取1，len后取0\\
(comb\&\sim y)/x \rightarrow 长度为len的全1串\\
((comb \& \sim y) / x ) >> 1 \rightarrow 右移1位,len-1\\
综上\\
(((comb \& \sim y) / x ) >> 1) | y \rightarrow 把comb的倒数第一段1的前一个位置的0取1，末尾添上该1段的长度-1个1
\end{array}
\]
然后这就是不重不漏的枚举。
所以时间复杂度\(O(\binom{n}{k})\)
版权声明：本文为autoint原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。