c - 给定集的幂集

给定一个集合，我想显示它的所有子集（它的幂集）。我发现了这个密码：

void printPowerSet(char *set, int set_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;

    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
      for(j = 0; j < set_size; j++)
       {

          if(counter & (1<<j))
            printf("%c", set[j]);
       }
       printf("\n");
    }
}

我不明白为什么用这个零件

 if(counter & (1<<j))

它是什么意思？
该算法的时间复杂度O(n2^n)是否有更好的方法？

最佳答案

这个if检查是否设置了位j。例如，当我们看到（为了简单起见，我使用了8位）：

XXXXXXX? & 00000001

其中j == 0是“不在乎”，我们要检查的是X。当?

XXXXXX?X & 00000010

换言之，这是一种检查位是否已设置或未设置的方便方法，它确定当前集合中是否包含相应的set元素。
至于复杂度，因为在幂集中有cc集，很难想象生成它们的更快的算法。
产生功率集的原因是二进制计数器耗尽了位值的所有组合，请参见下面的示例。
例子
集合：{1，2，3}

counter    1<<j   intermediate result   final
    000    001    N/A
    000    010    N/A
    000    100    N/A
                                        {}
    001    001    3
    001    010    N/A
    001    100    N/A
                                        {3}
    < ... skip a few iterations ... >
    101    001    3
    101    010    N/A
    101    100    1
                                        {1,3}
    < ... etc ... >