位阵列平等 [英] Bit Array Equality

问题描述

我需要的东西比 System.Collections.BitArray 类多一点我的应用程序。具体而言，我需要的比特阵列：

I need something a little more than the System.Collections.BitArray class in my application. Specifically, I need the bit array:

• 要成为不可改变
• 要使用值语义实现平等

我创造了我自己的结构，主要是复制 BitArray 实施内部。 （感谢 .net反射！）

I created my own struct, largely copying the internals of the BitArray implementation. (Thanks, .Net Reflector!)

我不每天都与位运算处理，所以不具有最高程度的信任我平等的实现。 （它是通过单元测试，我扔去，但我可能会丢失边缘的情况。）我有我提出的解决方案如下答案。我想AP preciate他人的反馈和回答的东西，可能是更正确的或有效的。

I don't deal everyday with bitwise operations, so I don't have the highest degree of confidence in my equality implementation. (It's passing the unit tests I am throwing at it, but I may be missing edge cases.) I have my proposed solutions as answers below. I would appreciate others' feedback and answers for something that may be more correct or efficient.

就像CLR BitArray 的长度字段是指位在结构中的数量和阵列字段（或阵列属性）指的是32位整数数组重新presents位。

Just like the CLR BitArray, the length field refers to the number of bits in the struct and the array field (or Array property) refers to the 32-bit integer array that represents the bits.

[澄清] 我选择了采取简单的方法在我的构造函数等方法，使我不能靠无用位是零。例如，

[CLARIFICATION] I have chosen to take the easy route in my constructors and other methods so that I cannot rely on the unnecessary bits being zeros. For example,

• 不是（）被求反（<$ C C $>〜）的整数数组的元素来实现。
• 构造函数是可用的带长度和布尔值初始化所有位。如果初始值是真实的，我设置的int数组中的所有元素为-1（二进制补码，通过全1 psented重新$ P $）
• 等

• Not() is implemented by bitwise negation (~) on the integer array elements.
• A constructor is available that takes a length and boolean to initialize all bits. If the initialization value is true, I set all elements of the int array to -1 (in two's complement, represented by all 1's)
• Etc.

因此​​，我需要处理（或者说，忽略），他们在比较。罚款的解决方案也将保持零在任何时候这些位，但在我的情况，这将导致更多的工作（包括计算机和我！）

Thus, I need to handle (or, rather, ignore) them in the comparison. A fine solution would also be to keep those bits zeroed at all times, but in my situation that will result in more work (both for the computer and me!)

推荐答案

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

Update: my original analysis below was incorrect...

不幸的是，我是不正确的约＆LT的行为;＆LT; 32 - C＃强制执行左移运营商将限制转移的数量低5位右操作数（6位涉及64位左操作数的转变）。所以，你原来的code既明确界定，并在C＃中正确的是（这是在C / C不确定的行为++）。从本质上讲，这种转变EX pression：

Unfortunately, I was incorrect about the behavior of << 32 - C# enforces that the left-shift operator will restrict the number of shift to the lower 5 bits of the right operand (6 bits for a shift involving a 64-bit left operand). So your original code was both well-defined and correct in C# (it is undefined behavior in C/C++). Essentially, this shift expression:

(this.Array[i] << shift)

等同于：

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

我可能还是改变转向做出明确的（如果没有其他原因，当我看着那个code 6个月后，我就不会通过相同的错误的分析绊倒）使用上述代替在如果（转向== 32）检查。

原分析：的

好了，所以这里的第二个答案。最重要的是，我认为你原来的解决方案，与案件中的错误，你的 ImmutableBitArray 是32位的倍数，你会返回<$ C $的位长C>真 2阵列不同，在过去的Int32 [] 数组元素。

OK, so here's a second answer. Most importantly, I think that you original solution has a bug in the case where the bit-length of your ImmutableBitArray is a multiple of 32 bits you'll return true for 2 arrays that differ in the last Int32[] array element.

例如，考虑 ImmutableBitArray s的32位，它是不同的位长度。原等于（）方法进行移位操作上独一无二的的Int32 数组中 - 但它'会移值32位，因为

For example, consider ImmutableBitArrays with a bit length of 32 bits that are different. The original Equals() method will perform the shift operation on the one and only Int32 in the array - but it'll shift the values 32 bits, since

int shift = 0x20 - (this.length % 0x20);

将计算为32。

will evaluate to 32.

这意味着下一个测试：

if (this.Array[i] << shift != other.Array[i] << shift)

将测试（0！= 0）因此，返回false 将不会被执行。

Will test for (0 != 0) and therefore the return false won't be executed.

我会改变你的等于（）方法类似下面，这是不是一个重大的改变 - 我认为这需要照顾上述的bug和改变是严格的风格有关的，可能不会有任何兴趣给你一对夫妇的其他东西。另外请注意，我并​​没有实际编译和测试我的等于（）的方法，所以有近100％的机会，有一个错误（或至少是一个语法错误）：

I'd change your Equals() method to something like the following, which isn't a major change - I think it takes care of the above mentioned bug and changes a couple other things that are strictly style-related so may not have any interest to you. Also note that I haven't actually compiled and test my Equals() method, so there's a nearly 100% chance that there's a bug (or at least a syntax error):

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

注意，严格的说，原来的 GetHash code（）方法不窃听，即使它具有相同的缺陷，因为即使你不这样做在最后一个元素正确地混合时，位长度是32的倍数，等于对象仍然会返回相同的哈希code。不过，我还是很可能决定，以解决以同样的方式缺陷的 GetHash code（）。

Note that strictly speaking, the original GetHashCode() method isn't bugged even though it has the same flaw, because even if you don't properly mix in the last element when the bit-length is a multiple of 32, equal object would still return the same hashcode. But I'd still probably decide to address the flaw in the same way in GetHashCode().

这篇关于位阵列平等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！