位阵列相等

Question

System.Collections.BitArray在我的应用程序中,我需要比类更多的东西.具体来说,我需要位数组:

• 是不可改变的
• 使用值语义实现相等性

我创建了自己的struct,主要是复制实现的内部BitArray.(谢谢,.Net Reflector!)

我不会每天处理按位操作,因此我对我的等式实现没有最高的信心.(它正在通过我投掷的单元测试,但我可能会遗漏边缘情况.)我将我提出的解决方案作为下面的答案.我会感谢别人的反馈和答案,可能更正确或更有效.

就像CLR一样BitArray,length字段指的是结构中的位数,array字段(或Array属性)指的是表示位的32位整数数组.

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

• Not()是通过~整数数组元素上的按位取反()实现的.
• 可以使用构造函数,它使用length和boolean来初始化所有位.如果初始化值为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最后一个Int32[]数组元素不同的 2 个数组。

例如，考虑ImmutableBitArray位长度为 32 位的 s 是不同的。原始方法将仅对数组中的Equals()1 执行移位操作- 但它会将值移位 32 位，因为Int32

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()方法没有 bug，即使它具有相同的缺陷，因为即使当位长度是 32 的倍数时，即使您没有正确混合最后一个元素，equal 对象仍然会返回相同的哈希码。但我仍然可能决定以同样的方式解决该缺陷GetHashCode()。