对于如何计算幂集的代码感到困惑

Question

我在geeksforgeeks网站上找到了一个函数，可以查找给定集合的所有子集。但是我不确定嵌套的for循环中的if语句是在检查什么。我知道它使用了按位与运算符，但我不明白它如何帮助确定哪些元素在任何迭代中包含或不包含。

import java.io.IOException; 

public class Main 
{ 
    // Print all subsets of given set[] 
    static void printSubsets(char set[]) 
    { 
        int n = set.length; 

        // Run a loop for printing all 2^n 
        // subsets one by obe 
        for (int i = 0; i < (1<<n); i++) 
        { 
            System.out.print("{ "); 

            // Print current subset 
            for (int j = 0; j < n; j++) 

               //???what is this checking?????
                if ((i & (1 << j)) > 0) 
                    System.out.print(set[j] + " "); 

            System.out.println("}"); 
        } 
    } 

    // Driver code 
    public static void main(String[] args) 
    { 
        char set[] = {'a', 'b', 'c'}; 
        printSubsets(set); 
    } 
} 

- Nick Heiting

---

它设置了位j（将1左移j位）。然后它对i执行“and”操作，即将i中除位j之外的所有内容设置为0并保留位j不变。最后，它比较结果是否大于0。由于仅剩下位j，因此效果是检查i是否已经设置了位j。 - kai

Answer 1

如果一个幂集中有三个元素，那么就会有2^3种组合。

a, b, c
===
[]
[a]
[b]
[a, b]
[c]
[a, c]
[b, c]
[a, b, c]

你会注意到这遵循二进制模式，其中每个位与集合中的一个元素匹配。如果位是 0，则从结果中移除元素。

a, b, c
===
[0, 0, 0] -> [0*a, 0*b, 0*c] = []
[1, 0, 0] -> [1*a, 0*b, 0*c] = [a]
[0, 1, 0] -> [0*a, 1*b, 0*c] = [b]
[1, 1, 0] -> [1*a, 1*b, 0*c] = [a, b]
[0, 0, 1] -> [0*a, 0*b, 1*c] = [c]
[1, 0, 1] -> [1*a, 0*b, 1*c] = [a, c]
[0, 1, 1] -> [0*a, 1*b, 1*c] = [b, c]
[1, 1, 1] -> [1*a, 1*b, 1*c] = [a, b, c]

代码行 if ((i & (1 << j)) > 0) 用于检查位以过滤结果。

- flakes

Answer 2

仅考虑 i 在位级别上的排列

如果 n=3 的情况，

i=0，

0 0 0 

is arrangement

i=3,

0 1 1 

那是什么

i & (1<<j) > 0  

只是检查位级别的条件，

这是一种掩码。

因为n等于3，

在for循环中j的值为0、1、2。

如果i=3的情况，

0 1 1

你只能选择 j=0 或 1

如果 i=5 的情况，

1 0 1 

是排列

那么你只能选择 j=0,2

完成 i 0...7 的上述过程后

你就可以得到所有的幂集！

- MJ Studio

---

好的，这有助于更好地解释。谢谢。 - Nick Heiting