6

我需要的东西比System.Collections.BitArray我的应用程序中的类多一点。具体来说，我需要位数组：

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

我创建了自己的struct，很大程度上复制了BitArray实现的内部结构。（谢谢，.Net 反射器！）

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

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

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

  • Not()~由整数数组元素的按位否定 ( ) 实现。
  • 可以使用一个构造函数，它需要一个长度和布尔值来初始化所有位。如果初始化值为真，我将 int 数组的所有元素设置为 -1（在二进制补码中，由全 1 表示）
  • 等等。

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

4

4 回答 4

2

如果在ImmutableBitArray最后一个元素上未使用的“填充位”的构造函数中被强制为零，则您不需要跳过箍来仅检查最后一个元素中的有效位，因为在相同的情况下填充将是相同的.

这将很好地简化Equals()andGetHashCode()方法：

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

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

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

(this.Array[i] << shift)

相当于：

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

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

原文分析：

好的，这是第二个答案。最重要的是，我认为您的原始解决方案存在一个错误，即您的位长度ImmutableBitArray是 32 位的倍数，您将为true2 个在最后一个Int32[]数组元素中不同的数组返回。

例如，考虑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 的倍数时您没有正确混合最后一个元素，equal object 仍然会返回相同的哈希码。但我仍然可能决定以相同的方式在GetHashCode().

于 2010-02-24T07:31:57.447 回答
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 回答