Java:如何实现子集的子集？

Question

以下实现找到集合的子集，但任何人都可以解释一下 if((i&(1<<j)) > 0)正在做，为什么？

评论似乎没有帮助并尝试了控制台日志记录，但仍然很难看出它到底在做什么。

//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 one
    for(int i=0; i<(1<<n); i++) {
        System.out.print("{ ");

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

            //(1<<j) is a number with jth bit 1
            //so when we 'and' them with the 
            //subset number we get which numbers
            //are present in the subset and which are not
            if((i&(1<<j)) > 0) {
                System.out.print(set[j] + " ");
            }
        }
            System.out.println("}");
    }
}

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

Answer 1

在一个子集中，每个元素可能存在，也可能不存在。所以每个元素只有 2 种可能的状态:in 或 out。 1 或 0。如果我们查看从 0 到 2^n -1 的数字的二进制表示, 其中n是元素的数量，例如 n=3 ，我们有:

    cba
0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111

有8个可能的子集，位代表一个元素是否在子集中。 这是程序使用的思路:

• 外循环来自0直到 2^n-1 .
• 内部循环来自0直到 n-1 .
• 1<<j是 1 向左移动 j次。

例如，当i=3 ，对应于位 011 . 我们从 0 开始循环直到 2 , 比较 i反对001 , 010 , 和 100 . 对于这些值，表达式 i & (1 << j)将被评估为 011 & 001 = 001 , 011 & 010 = 010 , 和 011 & 100 = 000 ， 分别。 前两个大于 0，最后一个不是。 所以System.out.print(set[j] + " ")将打印 a和 b .