6

System.Collections.BitArrayアプリケーションのクラスよりも少し多くのものが必要です。具体的には、ビット配列が必要です。

  • 不変であること
  • 値のセマンティクスを使用して等価性を実装するには

実装structの内部を大部分コピーして、独自の を作成しました。BitArray(ありがとう、.Net Reflector !)

私は毎日ビット単位の演算を扱っているわけではないので、等価性の実装に自信がありません。（私が投げている単体テストに合格していますが、エッジケースが欠けている可能性があります。）以下の回答として提案されたソリューションがあります。より正確または効率的なものについて、他の人のフィードバックと回答をいただければ幸いです。

CLR と同様BitArrayに、lengthフィールドは構造体のビット数を参照し、arrayフィールド (またはArrayプロパティ) はビットを表す 32 ビット整数配列を参照します。

[明確化]不要なビットがゼロであることに依存できないように、コンストラクターやその他のメソッドで簡単な方法を選択しました。例えば、

  • Not()~整数配列要素のビットごとの否定 ( ) によって実装されます。
  • すべてのビットを初期化するために長さとブール値を取るコンストラクターが利用可能です。初期化値が true の場合、int 配列のすべての要素を -1 に設定します (2 の補数で、すべて 1 で表されます)。
  • 等。

したがって、比較でそれらを処理する (というか、むしろ無視する) 必要があります。これらのビットを常にゼロにしておくことも良い解決策ですが、私の状況では、より多くの作業が必要になります (コンピューターと私の両方に!)

4

4 に答える 4

2

更新：以下の私の元の分析は間違っていました...

残念ながら、<< 32C# では、左シフト演算子が右オペランドの下位 5 ビット (64 ビットの左オペランドを含むシフトの場合は 6 ビット) にシフト数を制限することが強制されます。したがって、元のコードは C# で明確に定義され、正しいものでした (C/C++ では未定義の動作です)。基本的に、このシフト式:

(this.Array[i] << shift)

次と同等です。

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

if (shift == 32)チェックの代わりに上記を使用して、おそらくシフトを変更してそれを明示するでしょう（6か月後にそのコードを見たときに同じ間違った分析につまずくことがないという他の理由がなければ） 。

元の分析:

では、2 番目の回答を次に示します。最も重要なことは、最後の配列要素が異なる2つの配列に対してImmutableBitArray返されるビット長が32ビットの倍数である場合、元のソリューションにバグがあると思います。trueInt32[]

たとえば、ImmutableBitArray異なるビット長 32 ビットの s を考えてみましょう。元の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().

于 2010-02-24T07:31:57.447 に答える
2

最後の要素の未使用の「パディングビット」のコンストラクターで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;
}
于 2010-02-23T18:46:42.530 に答える
2

数時間の検索と研究の後、ようやく答えを得たので、共有したいと思います。読みやすさだけが気になるので、パフォーマンスはレビューしていません。

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;
于 2014-07-31T02:03:06.583 に答える
1

平等法:

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;
}
于 2010-02-23T18:37:03.597 に答える