Java: Wie implementiert man Teilmengen einer Teilmenge?

Question

Folgende Implementierung findet Teilmengen eines Satzes, aber könnte jemand bitte erklären, was if((i&(1<<j)) > 0) tut und aus welchem ​​Grund?

Der Kommentar scheint nicht zu helfen und versuchte Konsolenprotokollierung, aber es ist immer noch schwierig zu sehen, was es genau macht.

//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

In einer Untergruppe kann jedes Element entweder vorhanden sein oder nicht. Jedes Element hat also nur zwei mögliche Zustände: ein oder aus. 1 oder 0. Wenn wir die binäre Darstellung von Zahlen 0-2^n -1 schauen, wo n die Anzahl der Elemente ist, zum Beispiel wenn n=3, haben wir:

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

Es gibt 8 mögliche Teilmengen, und die Bits stellen dar, ob ein Element in der Teilmenge ist oder nicht. Das ist die Idee von dem Programm verwendet:

• Die äußere Schleife geht von 0 bis 2^n-1. Die innere Schleife geht von 0 bis n-1.
• 1<<j wird 1 nach links j mal verschoben.

Zum Beispiel, wenn i=3, entspricht das Bits 011. Wir schleifen von 0 bis 2, wobei i gegen 001, 010 und 100 verglichen werden. Für diese Werte wird der Ausdruck i & (1 << j) als 011 & 001 = 001, 011 & 010 = 010 bzw. 011 & 100 = 000 ausgewertet. Die ersten beiden sind größer als 0, der letzte nicht. So System.out.print(set[j] + " ") wird a und b drucken.