c# - 位数组相等

Question

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

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

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

我不是每天都处理按位运算，所以我对我的相等性实现没有高度的信心。 (它通过了我对它进行的单元测试，但我可能会遗漏边缘情况。)我在下面提出了我提出的解决方案作为答案。对于可能更正确或更有效的事情，我将不胜感激其他人的反馈和答案。

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

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

• Not() 是通过对整数数组元素按位求反 (~) 实现的。
• 有一个构造函数可用，它采用长度和 bool 值来初始化所有位。如果初始化值为真，我将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[]。

例如，考虑 ImmutableBitArray 的位长为 32 位，它们是不同的。原始的 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 的倍数时你没有正确地混合最后一个元素， equal object仍然会返回相同的哈希码。但我仍然可能决定以相同的方式解决 GetHashCode() 中的缺陷。