CODEWITHSUNDEEP
c#bitwise-operatorsbitarray
runfastman
runfastman

Reputation: 947

Bitwise operators on different length BitArrays

I have 2 BitArray items and I need to know if any of bits are the same in each, "AND". However, the length of the BitArrays can be different and ether one can be larger or smaller than the other.

How can I do an "AND" of two BitArrays, without getting an exception because of different sizes? This is going to happen a lot, so I need it to be fairly quick.

Example

  int[] ids = new int[3];
  ids[0] = 1;
  ids[1] = 3;
  ids[2] = 5;
  BitArray bs1 = new BitArray(ids.Max()+1);
  for (int i = 0; i < ids.Count(); ++i)
  {
    bs1[ids[i]] = true;
  }


  ids[0] = 1;
  ids[1] = 59;
  ids[2] = 1111;
  BitArray bs2 = new BitArray(ids.Max()+1);
  for (int i = 0; i < ids.Count(); ++i)
  {
    bs2[ids[i]] = true;
  }

  ids[0] = 0;
  ids[1] = 5;
  ids[2] = 33;
  BitArray bs3 = new BitArray(ids.Max()+1);
  for (int i = 0; i < ids.Count(); ++i)
  {
    bs3[ids[i]] = true;
  }


  //if bs1 AND bs2 bitcount > 0 DisplayMessage("1 and 2 has some same items")
  //if bs1 AND bs3 bitcount > 0 DisplayMessage("1 and 3 has some same items")
  //if bs2 AND bs3 bitcount > 0 DisplayMessage("2 and 3 has some same items")

To solve my problem I modified the BitArray code and added the following

public static MyBitArray TruncateCopy(MyBitArray source, int size)
{
  MyBitArray dest = new MyBitArray(size);

  //copy all the arrays
  for (int i = 0; i < dest.m_array.Length; ++i)
  {
    dest.m_array[i] = source.m_array[i];
  }

  //remove any of the items over the given size
  for (int i = ((size % 32) + 1); i < 32; ++i)
  {
    dest.m_array[i >> 5] &= ~(1 << (i & 31));
  }

  return dest;
}

public bool HasCommonBits(MyBitArray comp)
{
  MyBitArray copied, other;

  if (this.Length < comp.Length)
  {
    other = this;
    copied = TruncateCopy(comp, this.Length);
  }
  else
  {
    copied = TruncateCopy(this, comp.Length);
    other = comp;
  }

  MyBitArray compareEq = copied.And(other);

  return (!compareEq.IsEmpty());
}

public bool IsEmpty()
{
  for (int i = 0; i < this.m_array.Length; ++i)
  {
    if (m_array[i] != 0)
      return false;
  }

  return true;
}

public bool IsFull()
{
  //run through all the full sets
  for (int i = 0; i < this.m_array.Length - 1; ++i)
  {
    if (m_array[i] != -1) //-1 is all bits set in an integer
      return false;
  }

  //go through the partial one
  for (int i = 0; i < (this.Length % 32); ++i)
  {
    if (!this[i])
      return false;
  }

  return true;
}

}

Upvotes: 0

Views: 2477

Answers (2)

LB2
LB2

Reputation: 4860

Completely revised based on this comment:

The result bitarray of your example would be 01010. My original problem states that I need to see if any of the bits are the same. Thus the a resulting bitarray with any 1's would be True and all 0's would be False

BitArrray truncateCopyBA(BitArray source, int size)
{
    BitArray dest = new BitArray(size);

    for(int i = 0; i < size; ++i)
    {
        dest[i] = source[i];
    }

    return dest;
}

bool YourFunc(BitArray a, BitArray b)
{
    BitArray one, two;

    if (a.Length < b.Length)
    {
        one = a;
        two = truncateCopyBA(b, a.Length);
    }
    else
    {
        one = truncateCopyBA(a, b.Length);
        two = b;

        // If you want to see which bits in both arrays are both ones, then use .And()
        // If you want to see which bits in both arrays are the same, use .Not(.Xor()).
        BitArray compareEq = a.And(b);
        bool anyBitsSame=false;
        for(int i = 0; i < compareEq.Length; ++i)
        {
            if(compareEq.Get(i))
            {
                return true;
            }
        }

        return false
    }
}

I believe this is what you're looking for, but honestly your question is still quite vague after clarifications.

Upvotes: 0

usr
usr

Reputation: 171178

First, define what you want to happen in case of differing lengths. Maybe you just want to compare the first Math.Min(len1, len2) elements. In that case write a for loop whose index variable ranges from 0 to Math.Min(len1, len2). Compare the respective array elements in the loop body.

I examined BitArray with reflector. There is no way to trim it, or to perform a partial And. You're out of luck with this class. Replace it with a custom-written class that supports what you need. Writing a bit array is not especially hard.

Upvotes: 1

Related Questions