trovare il genitore comune di più BitSet java

Question

Non riuscivo a trovare una soluzione adeguata a questa semplice domanda nei metodi Bitset. La domanda è trovare il genitore comune di bitset, partendo dal bit più a sinistra. Ecco alcuni esempi:

011 
010 
001 
Common Parent: 0 

00 
010 
Common Parent: 0 

00 
11 
10 
Common Parent: None 

1101 
111 
1100 
Common Parent: 11 

mia soluzione era quella ed il bitset, e quindi trovare la lunghezza corretta, cercando per il primo bit impostato su XOR di questi bitset. Ha funzionato per alcuni casi ma ha fallito per gli altri. Ho un'altra idea che implica il looping dei Bitset che sarei molto felice di evitare se hai una soluzione.

[So che possono essere presentati come un albero binario, ma ciò comporta un sovraccarico della memoria che vorrei evitare operando solo sui bitset e alcune operazioni booleane (AND, OR, NOR, NAND, XOR) ]

Answer 1

Si potrebbe per esempio fare qualcosa di simile:

String[] input = {"011","010","001"}; 

    if(input.length==0) return ; 
    int n=input[0].length(); 
    List<BitSet> bitsets = new ArrayList<>(); 
    for(String in:input){ 
     // n is the min length of the inputs 
     n=Math.min(n,in.length()); 
     // If you start counting the indices from the left, you need to reverse the inputs 
     String reverse = new StringBuilder(in).reverse().toString(); 
     // Create the actual bitsets 
     BitSet b = BitSet.valueOf(new long[] { Long.parseLong(reverse, 2) }); 
     bitsets.add(b); 
    } 

    for(int i=0;i<n;i++){ 
     boolean equals=true; 
     for(int j=1;j<bitsets.size();j++) 
      equals &= bitsets.get(j-1).get(i)==bitsets.get(j).get(i); 
     if(equals) 
      System.out.print(bitsets.get(0).get(i)?"1":"0"); 
     // You can also print the indices if needed. 
    } 

ho scritto un paio di commenti nel codice. Spero possa essere d'aiuto!

Answer 2

È possibile AND e OR tutti i set di bit e memorizzare in due variabili. Esegui simultaneamente le due variabili da MSB a LSB. Se OR[i] è 0, tutti i set di bit hanno 0 nella posizione i ^th. Se AND[i] è 1, tutti i set di bit hanno 1 in quella posizione in cui vengono mescolati.

Answer 3

Raccomanderei di invertire le cifre e trovare il genitore da destra, quindi invertirlo con il genitore per trovare la cosa reale.

Penso che la situazione più difficile che hai è

1101 
111 
1100 
Common Parent: 11 

e invertire si ottiene fuori di esso.