बिट ऐरे समानता

Question

मुझे अपने आवेदन में System.Collections.BitArray कक्षा से कुछ और चाहिए। विशेष रूप से, मैं थोड़ा सरणी की जरूरत है:

• अपरिवर्तनीय होना करने के लिए
• का उपयोग कर मूल्य अर्थ विज्ञान

मैं अपने खुद के struct बनाया है, मोटे तौर पर BitArray कार्यान्वयन के आंतरिक भागों को कॉपी समानता लागू करने के लिए। (धन्यवाद, .Net Reflector!)

मैं हर रोज थोड़ा सा संचालन के साथ सौदा नहीं करता, इसलिए मेरे समानता कार्यान्वयन में मुझे उच्चतम आत्मविश्वास नहीं है। (यह यूनिट परीक्षणों को पार कर रहा है, मैं इसे फेंक रहा हूं, लेकिन मुझे किनारे के मामले गुम हो सकते हैं।) मेरे पास मेरे प्रस्तावित समाधान नीचे दिए गए उत्तरों के रूप में हैं। मैं उन चीज़ों के लिए दूसरों की प्रतिक्रिया और उत्तर की सराहना करता हूं जो अधिक सही या कुशल हो सकते हैं।

बस CLR BitArray की तरह, length क्षेत्र 32-बिट पूर्णांक सरणी कि बिट का प्रतिनिधित्व करने के लिए संदर्भित करता है struct में बिट्स की संख्या और array क्षेत्र (या Array संपत्ति) को दर्शाता है।

[वर्गीकरण] मैंने अपने रचनाकारों और अन्य तरीकों में आसान मार्ग लेने का चयन किया है ताकि मैं अनावश्यक बिट्स पर शून्य से भरोसा न कर सकूं। उदाहरण के लिए,

• Not() पूर्णांक सरणी तत्वों पर बिटवाइज़ निषेध (~) द्वारा कार्यान्वित किया जाता।
• एक कन्स्ट्रक्टर उपलब्ध है जो सभी बिट्स को आरंभ करने के लिए लंबाई और बूलियन लेता है। तो प्रारंभ मूल्य सच है, मैं सभी (दो के पूरक में सभी 1 के द्वारा प्रतिनिधित्व किया,) -1 को पूर्णांक सरणी के तत्वों
• आदि

इस प्रकार, मैं संभाल करने की जरूरत है (या, बल्कि, उन्हें अनदेखा करें) तुलना में उन्हें। एक अच्छा समाधान भी उन बिट्स हर समय ध्यान केंद्रित किया रखने के लिए (दोनों कंप्यूटर के लिए और मुझे!) समानता तरीका होगा, लेकिन मेरी स्थिति में है कि अधिक काम का परिणाम देगा

Answer 1

अद्यतन: नीचे अपने मूल विश्लेषण गलत थी ...

दुर्भाग्यवश, मैं << 32 के व्यवहार के बारे में गलत था - सी # लागू करता है कि बाएं-शिफ्ट ऑपरेटर दाएं ऑपरेंड के निचले 5 बिट्स में शिफ्ट की संख्या को प्रतिबंधित करेगा (64 बिट बाएं से जुड़े शिफ्ट के लिए 6 बिट्स संकार्य)। तो आपका मूल कोड सी # में अच्छी तरह से परिभाषित और सही दोनों था (यह सी/सी ++ में अपरिभाषित व्यवहार है)। अनिवार्य रूप से, इस बदलाव अभिव्यक्ति:

(this.Array[i] << shift) 

के बराबर है:

(this.Array[i] << (shift & 0x1f)) 

मैं शायद अभी भी पारी को बदल देंगे बनाने के लिए है कि स्पष्ट (यदि कोई अन्य कारण से जब मुझे लगता है कि कोड 6 को देखा है कि महीनों बाद मैं if (shift == 32) चेक के बजाय उपरोक्त का उपयोग करके एक ही गलत विश्लेषण के माध्यम से ठोकर नहीं खाऊंगा।

मूल विश्लेषण:

---

ठीक है, इसलिए यहाँ एक दूसरे सवाल का जवाब है। सबसे महत्वपूर्ण बात यह है कि, मुझे लगता है कि मूल समाधान में उस मामले में एक बग है जहां आपकी ImmutableBitArray की बिट-लंबाई 32 बिट्स का एक से अधिक है, आप true को 2 arrays के लिए वापस कर देंगे जो पिछले Int32[] सरणी तत्व में भिन्न है।

उदाहरण के लिए, 32 बिट्स की थोड़ी लंबाई के साथ ImmutableBitArray एस पर विचार करें। मूल Equals() विधि और एक पर पारी आपरेशन प्रदर्शन करेंगे केवल सरणी में Int32 - लेकिन यह मान 32 बिट शिफ्ट होगा, के बाद से

int shift = 0x20 - (this.length % 0x20); 

अगले इसका मतलब है कि 32.

करने का मूल्यांकन करेंगे परीक्षण:

if (this.Array[i] << shift != other.Array[i] << shift) 

(0 != 0) के लिए परीक्षण करेंगे और इसलिए return false निष्पादित नहीं किया जाएगा।

मैं आपकी Equals() विधि को निम्न जैसा कुछ करने के लिए बदल दूंगा, जो कि एक बड़ा बदलाव नहीं है - मुझे लगता है कि यह उपर्युक्त बग का ख्याल रखता है और कुछ अन्य चीजें बदलता है जो कड़ाई से शैली से संबंधित हैं, इसलिए हो सकता है आपके लिए कोई रूचि है यह भी ध्यान रखें कि मैं वास्तव में संकलित नहीं किया है और मेरे Equals() विधि का परीक्षण, इसलिए वहाँ एक लगभग 100% मौका वहाँ एक बग है कि (या कम से कम एक सिंटैक्स त्रुटि) है:

public bool Equals(ImmutableBitArray other) 
{ 
    if (this.length != other.length) 
    { 
     return false; 
    } 

    int finalIndex = this.Array.Length - 1; 

    for (int i = 0; i < finalIndex; i++) 
    { 
     if (this.Array[i] != other.Array[i]) 
     { 
      return false; 
     } 
    } 

    // check the last array element, making sure to ignore padding bits 

    int shift = 32 - (this.length % 32); 
    if (shift == 32) { 
     // the last array element has no padding bits - don't shift 
     shift = 0; 
    } 

    if (this.Array[finalIndex] << shift != other.Array[finalIndex] << shift) 
    { 
     return false; 
    } 

    return true; 
} 

ध्यान दें कि कडाई के मूल GetHashCode() विधि को बग नहीं किया गया है, भले ही इसमें एक ही दोष है, क्योंकि यदि आप अंतिम तत्व में सही ढंग से मिश्रण नहीं करते हैं, तो बिट-लम्बाई 32 का एक बहु है, तो बराबर ऑब्जेक्ट अभी भी एक ही हैशकोड लौटाएगा। लेकिन मैं अभी भी GetHashCode() में उसी तरह से दोष को दूर करने का निर्णय लेता हूं।

Answer 2

:

public bool Equals(ImmutableBitArray other) 
{ 
    if (this.length != other.length) 
    { 
     return false; 
    } 

    for (int i = 0; i < this.Array.Length; i++) 
    { 
     if (this.Array[i] != other.Array[i]) 
     { 
      // This does not necessarily mean that the relevant bits of the integer arrays are different. 
      // Is this before the last element in the integer arrays? 
      if (i < this.Array.Length - 1) 
      { 
       // If so, then the objects are not equal. 
       return false; 
      } 

      // If this is the last element in the array we only need to be concerned about the bits 
      // up to the length of the bit array. 
      int shift = 0x20 - (this.length % 0x20); 
      if (this.Array[i] << shift != other.Array[i] << shift) 
      { 
       return false; 
      } 
     } 
    } 

    return true; 
} 

और आवश्यक GetHashCode ओवरराइड:

public override int GetHashCode() 
{ 
    int hc = this.length; 

    for (int i = 0; i < this.Array.Length; i++) 
    { 
     if (i < this.Array.Length - 1) 
     { 
      hc ^= this.Array[i]; 
     } 
     else 
     { 
      int shift = 0x20 - (this.length % 0x20); 
      hc ^= this.Array[this.Array.Length - 1] << shift; 
     } 
    } 

    return hc; 
} 

Answer 3

शून्य आप केवल में मान्य बिट्स जाँच करने के लिए हुप्स के माध्यम से कूद करने की जरूरत नहीं है मजबूर हैं ImmutableBitArray अप्रयुक्त पिछले तत्व पर 'गद्दी बिट्स' के निर्माता में हैं अंतिम तत्व, क्योंकि पैडिंग एस होगा बराबर उदाहरणों में एएमई।

कि Equals() और GetHashCode() तरीकों अच्छी तरह से सरल बना रहे हैं:

public bool Equals(ImmutableBitArray other) 
{ 
    if (this.length != other.length) 
    { 
     return false; 
    } 

    for (int i = 0; i < this.Array.Length; i++) 
    { 
     if (this.Array[i] != other.Array[i]) 
     { 
      // since padding bits are forced to zero in the constructor, 
      // we can test those for equality just as well and the valid 
      // bits 
      return false; 
     } 
    } 

    return true; 
} 


public override int GetHashCode() 
{ 
    int hc = this.length; 

    for (int i = 0; i < this.Array.Length; i++) 
    { 
     // since padding bits are forced to zero in the constructor, 
     // we can mix those into the hashcode no problem 

     hc ^= this.Array[i]; 
    } 

    return hc; 
} 

Answer 4

खोज और अध्ययन के कई घंटों के बाद, मुझे अंततः मेरा जवाब मिला और साझा करना चाहते हैं। मैंने प्रदर्शन की समीक्षा नहीं की है क्योंकि मुझे केवल पठनीयता की परवाह है।

if (input1.length != input2.length) 
{ 
    return false; 
} 

var result = new BitArray(input1); 
result = result.Xor(input2); 

if (result.Cast<bool>().Contains(true)) 
    return false; 
return true;