algorithm - 生成由c ++中整数的二进制表示给出的集合的所有子集

Question

在 c++ 中，我正在寻找一种有效的算法来生成所有整数，使得它们的二进制表示是由整数 N 的二进制表示给出的集合的子集。高效我的意思是我不想循环遍历所有小于 N 的整数来检查它们是否是子集，主要是因为 N 可能非常大。

我的一个想法是生成与 N 的汉明权重相对应的整数的所有可能子集，然后使用 << 将它们移动到正确的位置，但到目前为止我还没有找到一个好的方法来做到这一点。

例子：

对于整数 N=52 给出的集合 110100，所有可能的子集将是：

{000100,010000,010100,100000,100100,110000}

对应于整数 {4,16,20,32,36,48}，这是我想要生成的。

Answer 1

令 P 为 popcount(N)，即设置的位数。结果的数量为 2 ^P - 2。

将 N 视为布尔数组（位）。对于设置的每个位，生成两个子集：一个设置了该位，一个没有设置。这可以递归地完成，直到没有位被设置。

最后，从结果中丢弃原始 N 以及 0（根据您的示例）。

时间复杂度与输出的大小呈线性关系，即 O(2 ^P )。