비트 어레이 평등

Question

내 응용 프로그램에 System.Collections.BitArray 클래스보다 조금 더 필요한 것이 있습니다. 특히, 나는 비트 배열이 필요합니다

• 은 불변하기
• 이 크게 BitArray 구현의 내부를 복사, 가치의 의미가

내가 내 자신의 struct을 사용하여 만든 평등을 구현하기 위해. (고마워, .Net Reflector!)

저는 비트 연산을 매일 다루지 않으므로, 평등 구현에서 가장 높은 수준의 확신을 가지고 있지 않습니다. (그것은 내가 던지고있는 단위 테스트를 통과하고 있지만 가장자리가없는 경우가있을 수 있습니다.) 아래에 답변으로 제시된 해결책이 있습니다. 나는 다른 사람들의 피드백과보다 정확하거나 효율적인 무언가에 대한 답변에 감사 할 것입니다. 다만 CLR BitArray 등

상기 length 필드는 비트를 나타내는 32 비트 정수 배열을 지칭 구조체의 비트 수와 array 필드 (또는 Array 특성)을 의미한다.

[CLARIFICATION] 나는 불필요한 비트가 0 인 것에 의존 할 수 없도록 내 생성자 및 다른 방법으로 쉬운 경로를 선택했습니다. 예를 들어,

• Not()은 정수 배열 요소의 비트 단위 부정 (~)으로 구현됩니다.
• 길이를 가져 와서 모든 비트를 초기화하는 생성자를 사용할 수 있습니다. 초기화 값이 참이면, I는 오히려

따라서, I를 처리 할 필요가 (모두 1로 나타내는 2의 보수의) -1로 int 배열의 모든 요소

등을 설정 (또는 무시). (컴퓨터의 날 모두!) 벌금 솔루션은 또한 항상 제로 그 비트를 유지하는 것입니다,하지만 내 상황에서 그 많은 작업에서 발생합니다

Answer 1

업데이트을 아래에 내 원래의 분석이 잘못되었습니다 ...

불행히도, 나는의 동작에 대해 올바르지 않습니다. C#은 왼쪽 시프트 연산자가 오른쪽 피연산자의 하위 5 비트로 시프트 수를 제한 할 것을 강요합니다 (64 비트 왼쪽 시프트를위한 ​​6 비트 피연산자). 따라서 원래 코드는 C#에서 잘 정의되어 있고 정확합니다 (C/C++에서 정의되지 않은 동작 임). 기본적으로,이 시프트 식 :

(this.Array[i] << shift) 

은 동일합니다 : 나는 아마 아직도 만들기 위해 변화를 변경할 것

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

(즉 명시 경우 다른 이유로 내가 그 코드 6 보았다 때 몇 달 후에 나는 동일한 실수 분석을 통해 우연히 발견하지 않을 것입니다.) if (shift == 32) 수표 대신 위의 방법을 사용하십시오.

원래 분석 :

---

확인, 그래서 여기에 두 번째 대답. 가장 중요한 점은 원래 솔루션에 ImmutableBitArray의 비트 길이가 32 비트의 배수 인 경우에 버그가 있다는 것인데, 배열 요소와 다른 두 개의 배열에 대해 true을 반환 할 것입니다.

예를 들어, 비트 길이가 다른 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하지 않는 '패딩 비트'의 생성자의 경우 마지막 요소. 패딩이 s가 될 것이다. 같은 경우에.

그건 멋지게 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;