我有一个用整数表示的逐位掩码。掩码和整数限制为32位整数。
我对检查给定掩码/整数的集合位的所有子集很感兴趣，但我不知道快速找到这些子集的好方法。
我一直使用的解决方案是
for(int j = 1; j <= mask; ++j)
{
if(j & mask != 0)
{
// j is a valid subset of mask
}
}
但这需要从j = 1循环到mask，我认为应该有比这更快的解决方案。
有比这更快的解决方案吗？
我的后续问题是，如果我想将子集约束为固定大小(即，固定数量的集合位(，有没有一种简单的方法可以做到这一点？
在C++中迭代state的所有subset：
for (int subset=state; subset>0; subset=(subset-1)&state) {}
这个技巧通常用于位掩码+dp问题。迭代所有state的所有subset的总时间复杂度为O(3^n(，如果使用本问题中的代码，这比O(4^n(有很大的改进。
对于长度为n的位掩码，集合位的最大子集数可以是2^n - 1。因此，如果你想检查它们，我们必须遍历所有的子集，因此最好的复杂性是O(mask)。该代码无法进一步改进。
Ps：如果你想计算子集的总数，那么可以使用时间复杂度高得多的动态编程来解决。
给定x和mask中的一个子集，下一个子集按顺序为( (x|~mask) +1 ) & mask。如果x==mask。
对于具有固定位数的子集，我没有超快速的方法。