如何迭代按位掩码的子集？

Question

我有一个表示为整数的按位掩码。掩码和整数限制为32位整数。

for(int j = 1; j <= mask; ++j)
{
  if(j & mask != 0)
  {
    // j is a valid subset of mask
  }
}

有比这更快的解决方案吗？

我的后续问题是，如果我想限制子集的大小（即，固定的设置比特数），有没有一个简单的方法做到这一点？

Answer 1

在C++中迭代状态的所有子集:

for (int subset=state; subset>0; subset=(subset-1)&state) {}

这个技巧通常用于位掩码+dp问题。迭代所有状态的所有子集的总时间复杂度为O(3^n)，如果使用本题中的代码，这比O(4^n)有了很大的改进。