Bitfields in C#

Question

So, bitfields. Specifically, large bitfields. I understand how to manipulate individual values in a bitfield, but how would I go about doing this on a large set, such as say:

uint[] bitfield = new uint[4] { 0x0080000, 0x00FA3020, 0x00C8000, 0x0FF00D0 };

The specific problem I'm having is doing left and right shifts that carry through across the whole array. So for instance, if I did a >> 4 on the above array, I'd end up with:

uint[4] { 0x0008000, 0x000FA302, 0x000C800, 0x00FF00D };

Now, an (overly) simplistic algorithm here might look something like (this is me writting code on the fly):

int shift = 4;
for (int i = 0; i <= shift; i++) {
    for (int j = bitfield.GetUpperBound(0); j > 0; j--) {
        bitfield[j] = bitfield[j] >> 1;
        bitfield[j] = bitfield[j] + ((bitfield[j-1] & 1) << (sizeof(uint)*8));
    }
    bitfield[0] = bitfield[0] >> 1;
}

Is there anything built in that might ease working with this sort of data?

Answer 1

What makes you think that BitArray uses bools internally? It uses Boolean values to represent the bits in terms of the API, but under the hood I believe it uses an int[].

Answer 2

BigInteger?

Answer 3

Using extension methods, you could do this:

public static class BitArrayExtensions
{
 public static void DownShift(this BitArray bitArray, int places)
 {
  for (var i = 0; i < bitArray.Length; i++)
  {
   bitArray[i] = i + places < bitArray.Length && bitArray[i + places];
  }
 }

 public static void UpShift(this BitArray bitArray, int places)
 {
  for (var i = bitArray.Length - 1; i >= 0; i--)
  {
   bitArray[i] = i - places >= 0 && bitArray[i - places];
  }
 }
}

Unfortunately, I couldn't come up with a way to overload the shift operators. (Mainly because BitArray is sealed.)

If you intend to manipulate ints or uints, you could create extension methods for inserting bits into / extracting bits from the BitArray. (BitArray has a constructor that takes an array of ints, but that only takes you that far.)

Answer 4

This doesn't cover specifically shifting, but could be useful for working with large sets. It's in C, but I think it could be easily adapted to C#

http://stackoverflow.com/questions/177054/is-there-a-practical-limit-to-the-size-of-bit-masks#177092

Answer 5

I'm not sure if it's the best way to do it, but this could work (constraining shifts to be in the range 0-31.

 public static void ShiftLeft(uint[] bitfield, int shift) {

  if(shift < 0 || shift > 31) {
   // handle error here
   return;
  }

  int len = bitfield.Length;
  int i = len - 1;
  uint prev = 0;

  while(i >= 0) {
   uint tmp  = bitfield[i];
   bitfield[i] = bitfield[i] << shift;
   if(i < len - 1) {
    bitfield[i] |= (uint)(prev & (1 >> shift) - 1 ) >> (32 - shift);
   }
   prev = tmp;

   i--;
  }

 }

 public static void ShiftRight(uint[] bitfield, int shift) {

  if(shift < 0 || shift > 31) {
   // handle error here
   return;
  }
  int len = bitfield.Length;
  int i = 0;
  uint prev = 0;

  while(i < len) {
   uint tmp  = bitfield[i];
   bitfield[i] = bitfield[i] >> shift;
   if(i > 0) {
    bitfield[i] |= (uint)(prev & (1 << shift) - 1 ) << (32 - shift);
   }
   prev = tmp;

   i++;
  }

 }

PD: With this change, you should be able to handle shifts greater than 31 bits. Could be refactored to make it look a little less ugly, but in my tests, it works and it doesn't seem too bad performance-wise (unless, there's actually something built in to handle large bitsets, which could be the case).

 public static void ShiftLeft(uint[] bitfield, int shift) {

  if(shift < 0) {
   // error
   return;
  } 

  int intsShift = shift >> 5;

  if(intsShift > 0) {
   if(intsShift > bitfield.Length) {
    // error
    return;
   }

   for(int j=0;j < bitfield.Length;j++) {
    if(j > intsShift + 1) {  
     bitfield[j] = 0;
    } else {
     bitfield[j] = bitfield[j+intsShift];
    }
   }

   BitSetUtils.ShiftLeft(bitfield,shift - intsShift * 32);
   return;
  }

  int len = bitfield.Length;
  int i = len - 1;
  uint prev = 0;

  while(i >= 0) {
   uint tmp = bitfield[i];
   bitfield[i] = bitfield[i] << shift;
   if(i < len - 1) {
    bitfield[i] |= (uint)(prev & (1 >> shift) - 1 ) >> (32 - shift);
   }
   prev = tmp;

   i--;
  }

 }

 public static void ShiftRight(uint[] bitfield, int shift) {

  if(shift < 0) {
   // error
   return;
  } 

  int intsShift = shift >> 5;

  if(intsShift > 0) {
   if(intsShift > bitfield.Length) {
    // error
    return;
   }

   for(int j=bitfield.Length-1;j >= 0;j--) {
    if(j >= intsShift) {  
     bitfield[j] = bitfield[j-intsShift];
    } else {
     bitfield[j] = 0;
    }
   }

   BitSetUtils.ShiftRight(bitfield,shift - intsShift * 32);
   return;
  }


  int len = bitfield.Length;
  int i = 0;
  uint prev = 0;

  while(i < len) {
   uint tmp = bitfield[i];
   bitfield[i] = bitfield[i] >> shift;
   if(i > 0) {
    bitfield[i] |= (uint)(prev & (1 << shift) - 1 ) << (32 - shift);
   }
   prev = tmp;

   i++;
  }

 }