Uguaglianza bit array

Question

Ho bisogno di qualcosa di più della classe System.Collections.BitArray nella mia applicazione. In particolare, ho bisogno della matrice di bit:

• immutabili
• Per implementare l'uguaglianza utilizzando la semantica di valore

ho creato il mio struct, copiando in gran parte la struttura interna del BitArray attuazione. (Grazie, .Net Reflector!)

Non mi occupo quotidianamente di operazioni bit a bit, quindi non ho il massimo grado di fiducia nella mia implementazione di uguaglianza. (Sto superando i test unitari che sto lanciando, ma potrei mancare ai casi limite). Ho le mie soluzioni proposte come risposte di seguito. Gradirei il feedback e le risposte degli altri per qualcosa che potrebbe essere più corretto o efficiente.

Proprio come il CLR BitArray, il campo length si riferisce al numero di bit nella struct e il campo array (o Array proprietà) si riferisce alla matrice numero intero a 32 bit che rappresenta i bit.

[CHIARIMENTO] Ho scelto di prendere il percorso facile nei miei costruttori e in altri metodi in modo che non possa fare affidamento sui bit non necessari che sono zero. Ad esempio,

• Not() viene implementato da bit a bit negazione (~) sugli elementi dell'array intero.
• Un costruttore è disponibile che accetta una lunghezza e un valore booleano per inizializzare tutti i bit. Se il valore di inizializzazione è vero, ho impostato tutti gli elementi del int matrice a -1 (in complemento a due, rappresentate da tutti 1)
• Ecc

Così, ho bisogno di gestire (o, meglio, ignorarli) nel confronto. Una bella soluzione sarebbe anche quello di mantenere quei bit azzerato in ogni momento, ma nella mia situazione che si tradurrà in più lavoro (sia per il computer e per me!)

Answer 1

Aggiornamento: la mia analisi originale di sotto non era corretta ...

Sfortunatamente, non ero corretto sul comportamento di << 32 - C# impone che l'operatore di spostamento a sinistra limiterà il numero di spostamento ai 5 bit inferiori dell'operando di destra (6 bit per uno spostamento che coinvolge un 64 bit a sinistra operando). Quindi il tuo codice originale era ben definito e corretto in C# (è un comportamento indefinito in C/C++). In sostanza, questa espressione spostamento:

(this.Array[i] << shift) 

è equivalente a:

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

probabilmente sarei ancora cambiare il turno di fare che esplicita (se non altro motivo che quando ho guardato quel codice 6 mesi dopo non avrei inciampato nella stessa analisi sbagliata) usando il controllo precedente invece del controllo if (shift == 32).

L'analisi originale:

---

OK, quindi ecco una seconda risposta. Ancora più importante, penso che la soluzione originale abbia un bug nel caso in cui il bit-length del tuo ImmutableBitArray sia un multiplo di 32 bit restituirà true per 2 array che differiscono nell'ultimo elemento dell'array Int32[].

Ad esempio, considerare ImmutableBitArray s con una lunghezza di bit di 32 bit diversa. Il metodo originale Equals() eseguirà l'operazione di cambio da un solo Int32 nella matrice - ma sarà spostare i valori 32 bit, poiché

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

valuterà a 32.

Ciò significa che la prossima Test:

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

proverà per (0 != 0) e quindi non verrà eseguito il return false.

Vorrei cambiare il tuo metodo Equals() in qualcosa come il seguente, che non è un grosso cambiamento - penso che si prenda cura del bug sopra citato e cambi un paio di altre cose strettamente correlate allo stile, quindi potrebbe non ti interessa. Si noti inoltre che non ho effettivamente compilato e prova il mio metodo Equals(), quindi c'è una probabilità quasi il 100% che ci sia un bug (o almeno un errore di sintassi):

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

Si noti che a rigor di termini, l'originale GetHashCode() il metodo non è bugato anche se ha lo stesso difetto, perché anche se non si configura correttamente l'ultimo elemento quando la lunghezza del bit è un multiplo di 32, l'oggetto uguale restituirà comunque lo stesso hashcode. Ma probabilmente continuerei a decidere di risolvere il problema nello stesso modo in GetHashCode().

Answer 2

Il metodo di uguaglianza:

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

E la necessaria GetHashCode di override:

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

Se nel costruttore delle ImmutableBitArray i 'bit di riempimento' inutilizzati l'ultimo elemento sono costretti a zero non è necessario fare i salti mortali per controllare solo i bit validi nella ultimo elemento, poiché il padding sarà la s in casi uguali.

Che ti semplificano le Equals() e GetHashCode() metodi ben:

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

Dopo diverse ore di ricerca e studio, ho finalmente ottenuto la mia risposta e vorrei condividere. Non ho esaminato la performance poiché mi interessa solo la leggibilità.

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;