Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Bit Array Equality

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

  • To be immutable
  • To implement equality using value semantics

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

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.

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,

  • 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!)

like image 819
Dave Mateer Avatar asked Feb 23 '10 18:02

Dave Mateer


2 Answers

Update: my original analysis below was incorrect...

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)

is equivalent to:

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

I'd probably still change the shift to make that explicit (if for no other reason that when I looked at that code 6 months later I wouldn't stumble through the same mistaken analysis) using the above instead of the if (shift == 32) check.

The original analysis:


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.

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

will evaluate to 32.

That means the next test:

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

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

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

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().

like image 166
Michael Burr Avatar answered Sep 30 '22 10:09

Michael Burr


After several hours of searching and study, I finally got my answer and would like to share. I have not reviewed the performance as I only care readability.

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;
like image 40
user2434918 Avatar answered Sep 30 '22 12:09

user2434918