位数组相等

Question

我的应用程序中需要的不仅仅是 System.Collections.BitArray 类。具体来说，我需要位数组：

• 保持不可变
• 为了使用值语义实现相等性，

我创建了自己的 struct，主要复制了 BitArray 实现的内部结构。 （谢谢，.Net Reflector！）

我并不每天处理按位运算，所以我对我的平等实施没有最大程度的信心。 （它通过了我扔给它的单元测试，但我可能会错过边缘情况。）我提出的解决方案如下。我很感激其他人的反馈和答案，这些反馈和答案可能更正确或更有效。

就像 CLR BitArray 一样，length 字段指的是结构体和 array 字段（或 Array< /code> property) 指的是表示位的 32 位整数数组。

[澄清] 我选择在构造函数和其他方法中采用简单的方法，这样我就不能依赖将不必要的位设为零。例如，

• Not() 是通过对整数数组元素进行按位求反 (~) 来实现的。
• 可以使用一个构造函数，它采用长度和布尔值来初始化所有位。如果初始化值为true，我将int数组的所有元素设置为-1（以二进制补码表示，用全1表示）
• 等等。

因此，我需要在比较中处理（或者更确切地说，忽略）它们。一个好的解决方案也是始终将这些位保持为零，但在我的情况下，这将导致更多的工作（对于计算机和我来说！）

Answer 1

更新：我下面的原始分析是不正确的...

不幸的是，我对 << 的行为是不正确的。 32 - C# 强制左移运算符将移位次数限制为右操作数的低 5 位（涉及 64 位左操作数的移位为 6 位）。因此，您的原始代码在 C# 中定义良好且正确（在 C/C++ 中是未定义的行为）。本质上，这个移位表达式：

(this.Array[i] << shift)

相当于：

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

我可能仍然会更改移位以使其明确（如果没有其他原因，当我在 6 个月后查看该代码时，我不会偶然发现相同的错误分析）使用上面的内容代替了 if (shift == 32) 检查。

原始分析：

---

好的，这是第二个答案。最重要的是，我认为你原来的解决方案有一个错误，如果你的 ImmutableBitArray 的位长度是 32 位的倍数，你将返回 true 为 2最后一个 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

如果在 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 3

经过几个小时的搜索和研究，我终于得到了答案，并分享给大家。我没有审查性能，因为我只关心可读性。

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;

Answer 4

相等方法：

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