Bit Array Equality

Question

Necesito algo más que la clase System.Collections.BitArray en mi aplicación. Específicamente, necesito la matriz de bits:

• que son inmutables
• Para poner en práctica la igualdad mediante la semántica de valor

he creado mi propia struct, copiando en gran medida el funcionamiento interno de la implementación BitArray. (Gracias, .Net Reflector!)

No trato todos los días con operaciones bit a bit, así que no tengo el más alto grado de confianza en mi implementación de igualdad. (Está pasando las pruebas de la unidad que estoy lanzando, pero puede que me falten casos extremos.) Tengo mis soluciones propuestas como respuestas a continuación. Agradecería los comentarios y respuestas de otros por algo que puede ser más correcto o eficiente.

Al igual que el CLR BitArray, el campo length se refiere al número de bits en la estructura y el campo array (o Array propiedad) se refiere a la matriz de enteros de 32 bits que representa los bits.

[ACLARACIÓN] He elegido tomar la ruta fácil en mis constructores y otros métodos para no poder confiar en que los bits innecesarios sean ceros. Por ejemplo,

• Not() se implementa por la negación bit a bit (~) sobre los elementos de la matriz de enteros.
• Hay disponible un constructor que toma una longitud y un valor booleano para inicializar todos los bits. Si el valor de inicialización es cierto, puse todos los elementos de la matriz int a -1 (en complemento a dos, representados por todos 1'S)
• Etc.

Por lo tanto, I necesidad de manejar (o, más bien, ignórelos) en la comparación. Una buena solución también sería mantener esos bits cero en todo momento, pero en mi situación que dará lugar a más trabajo (tanto para el equipo y para mí!)

Answer 1

actualización: mi análisis original era incorrecta a continuación ...

Desafortunadamente, era incorrecta sobre el comportamiento de << 32 - C# exige que el operador de desplazamiento a la izquierda restrinja el número de desplazamiento a los 5 bits más bajos del operando derecho (6 bits para un cambio que implica un 64 bits a la izquierda operando). De modo que su código original estaba bien definido y era correcto en C# (es un comportamiento indefinido en C/C++). En esencia, esta expresión turno:

(this.Array[i] << shift) 

es equivalente a:

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

yo probablemente todavía cambiar el turno de hacer explícita de que (si no por otra razón por la que cuando miraba a ese código de 6 meses más tarde no me tropezaría con el mismo error de análisis) utilizando el anterior en lugar del cheque if (shift == 32).

El análisis original:

---

OK, así que aquí tiene una segunda respuesta. Lo más importante, creo que su solución original tiene un error en el caso donde la longitud de bit de su ImmutableBitArray es un múltiplo de 32 bits, devolverá true para 2 matrices que difieren en el último elemento de matriz Int32[].

Por ejemplo, considere ImmutableBitArray s con una longitud de bits de 32 bits diferente. El método original Equals() llevará a cabo la operación de desplazamiento en la primera y única Int32 en la matriz - sino que va a cambiar los valores de 32 bits, ya que

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

evaluará a 32.

Eso significa que la próxima prueba:

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

pondrá a prueba para (0 != 0) y por lo tanto no se ejecutará la return false.

Cambiaría su método Equals() a algo como el siguiente, que no es un cambio importante - Creo que se ocupa de la falla mencionada anteriormente y cambia un par de otras cosas que están estrictamente relacionadas con el estilo, por lo que no tiene algún interés para ti. También tenga en cuenta que no he hecho compilado y probar mi método Equals(), así que hay una probabilidad de casi el 100% de que hay un error (o por lo menos un error de sintaxis):

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

Nota que, estrictamente hablando, el original GetHashCode() El método no tiene errores, aunque tiene el mismo defecto, porque incluso si no mezcla correctamente el último elemento cuando la longitud del bit es un múltiplo de 32, el objeto igual devolvería el mismo código hash. Pero probablemente todavía decidiría abordar la falla de la misma manera en GetHashCode().

Answer 2

El método de la igualdad:

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

Y GetHashCode la anulación necesaria:

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

Si en el constructor de los ImmutableBitArray los no utilizados bits de relleno '' en el último elemento se ven obligados a cero no es necesario pasar por el aro sólo para comprobar los bits válidos en el último elemento, ya que el relleno será el ame en instancias iguales.

Eso va a simplificar los métodos y Equals()GetHashCode() muy bien:

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

Después de varias horas de búsqueda y estudio, finalmente obtuve mi respuesta y me gustaría compartirla. No he revisado el rendimiento ya que solo me importa la legibilidad.

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;