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

Question

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

我有兴趣检查给定掩码/整数的集合位的所有子集，但我不知道快速找到这些子集的好方法。

我一直在使用的解决方案是

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

但这需要从j = 1to循环mask，我认为应该有比这更快的解决方案。

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

我的后续问题是，如果我想将子集限制为固定大小（即固定数量的设置位），是否也有一种简单的方法可以做到这一点？

标签： algorithmlanguage-agnosticbit-manipulation

Answer 1

在 C++ 中迭代所有的subset：state

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

这个技巧通常用于位掩码+dp问题。总的时间复杂度是 O(3^n) 来迭代 all subsetof all state，如果使用这个问题中的代码，这比 O(4^n) 有了很大的改进。