Bit fields in C #

Question

So, bit fields. In particular, large bit fields. I understand how to manipulate individual values ​​in a bit field, but how will I do this on a large set, for example, say:

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

The specific problem I am facing is a left and right shift going through the entire array. So, for example, if I made >> 4 in the above array, I would end with:

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

Now the (overly) simplified algorithm here might look something like this (this is where I find the 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 can make it easier to work with such data?

Answer 1

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

Answer 2

I'm not sure if this is the best way to do this, but it might work (the shift limit should be in the range of 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 will be able to handle shifts greater than 31 bits. It can be reorganized to make it a little less ugly, but it works in my tests and it doesn't seem too poor in performance (unless it has a built-in tool for processing large bits, which may be so).

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

Answer 3

Using extension methods, you can 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 could not find a way to overload the shift operators. (Mostly since BitArray sealed.)

If you intend to manipulate int or uint s, you can create extension methods to insert bits into / extract bits from BitArray . ( BitArray has a constructor that accepts an int s array, but that only goes that far.)

Answer 4

This does not apply much switching, but can be useful for working with large sets. It is in C, but I think it can be easily adapted to C #

Is there a practical limit to the size of bit masks?