एकाधिक बिट्स जावा के सामान्य अभिभावक को ढूंढना जावा

Question

मुझे बिटसेट विधियों में इस सरल प्रश्न का उचित समाधान नहीं मिला। सवाल बाइट्स के सामान्य माता-पिता को बाएं से शुरू करने के लिए है। यहाँ कुछ उदाहरण हैं:

011 
010 
001 
Common Parent: 0 

00 
010 
Common Parent: 0 

00 
11 
10 
Common Parent: None 

1101 
111 
1100 
Common Parent: 11 

मेरे समाधान के लिए और Bitsets था, और फिर इन Bitsets की XOR पर पहला सेट बिट की तलाश द्वारा सही लंबाई पाते हैं। यह कुछ मामलों के लिए काम किया लेकिन दूसरों के लिए असफल रहा। मेरे पास एक और विचार है जिसमें बिट्ससेट्स पर लूपिंग शामिल है जो आपको समाधान देने से बचने में बहुत खुशी होगी।

[मुझे पता है कि उन्हें बाइनरी पेड़ के रूप में प्रस्तुत किया जा सकता है, लेकिन इसमें एक मेमोरी ओवरहेड शामिल है जिसे मैं केवल बिट्ससेट और कुछ बुलियन ऑपरेशंस (एंड, ओआर, एनओआर, एनएएनडी, एक्सओआर) पर परिचालन करके टालना चाहता हूं। ]

Answer 1

उदाहरण के लिए आप कुछ इस तरह कर सकता है:

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. 
    } 

मैं कोड में कुछ टिप्पणियां लिखीं। मुझे उम्मीद है यह मदद करेगा!

Answer 2

आप AND और OR सभी बिट्स और स्टोर को दो चरों में स्टोर कर सकते हैं। MSB से LSB पर एक साथ दो चरों पर एक साथ Iterate। यदि OR[i]0 है, तो सभी बिट्स में 0 है I ^वें स्थिति पर। यदि AND[i]1 है, तो सभी बिट्स में 1 है और उस स्थिति में वे मिश्रित हैं।

Answer 3

मैं अंक को उलटाने और माता-पिता को सही से ढूंढने की अनुशंसा करता हूं, फिर वास्तविक चीज़ को खोजने के लिए माता-पिता को उलट देता हूं।

मुझे लगता है कि trickiest स्थिति आपके पास

1101 
111 
1100 
Common Parent: 11 

है और पीछे आप इससे बाहर हो जाता है।