Bitfields in C#
-
05-07-2019 - |
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?
Solution
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[].
OTHER TIPS
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++;
}
}
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 int
s or uint
s, you could create extension methods for inserting bits into / extracting bits from the BitArray
. (BitArray
has a constructor that takes an array of int
s, but that only takes you that far.)
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#