Converting a range into a bit array

Question

I'm writing a time-critical piece of code in C# that requires me to convert two unsigned integers that define an inclusive range into a bit field. Ex:

uint x1 = 3;
uint x2 = 9;
  //defines the range [3-9]
  //                              98  7654 3
  //must be converted to:  0000 0011  1111 1000

It may help to visualize the bits in reverse order

The maximum value for this range is a parameter given at run-time which we'll call max_val. Therefore, the bit field variable ought to be defined as a UInt32 array with size equal to max_val/32:

UInt32 MAX_DIV_32 = max_val / 32;
UInt32[] bitArray = new UInt32[MAX_DIV_32];

Given a range defined by the variables x1 and x2, what is the fastest way to perform this conversion?

Answer 1

You could try:

UInt32 x1 = 3;
UInt32 x2 = 9;
UInt32 newInteger = (UInt32)(Math.Pow(2, x2 + 1) - 1) & 
                   ~(UInt32)(Math.Pow(2, x1)-1);

Answer 2

Is there a reason not to use the System.Collections.BitArray class instead of a UInt32[]? Otherwise, I'd try something like this:

int minIndex = (int)x1/32;
int maxIndex = (int)x2/32;
// first handle the all zero regions and the all one region (if any)
for (int i = 0; i < minIndex; i++) {
    bitArray[i] = 0;
}
for (int i = minIndex + 1; i < maxIndex; i++) {
    bitArray[i] = UInt32.MaxValue; // set to all 1s
}
for (int i = maxIndex + 1; i < MAX_DIV_32; i++) {
    bitArray[i] = 0;
}

// now handle the tricky parts
uint maxBits = (2u << ((int)x2 - 32 * maxIndex)) - 1; // set to 1s up to max
uint minBits = ~((1u << ((int)x1 - 32 * minIndex)) - 1); // set to 1s after min

if (minIndex == maxIndex) {
    bitArray[minIndex] = maxBits & minBits;
}
else {
    bitArray[minIndex] = minBits;
    bitArray[maxIndex] = maxBits;
}

Answer 3

Try this. Calculate the range of array items that must be filled with all ones and do this by iterating over this range. Finally set the items at both borders.

Int32 startIndex = x1 >> 5;
Int32 endIndex = x2 >> 5;

bitArray[startIndex] = UInt32.MaxValue << (x1 & 31);

for (Int32 i = startIndex + 1; i <= endIndex; i++)
{
   bitArray[i] = UInt32.MaxValue;
}

bitArray[endIndex] &= UInt32.MaxValue >> (31 - (x2 & 31));

May be the code is not 100% correct, but the idea should work.

---

Just tested it and found three bugs. The calculation at start index required a mod 32 and at end index the 32 must be 31 and a logical and instead of a assignment to handle the case of start and end index being the same. Should be quite fast.

---

Just benchmarked it with equal distribution of x1 and x2 over the array. Intel Core 2 Duo E8400 3.0 GHz, MS VirtualPC with Server 2003 R2 on Windows XP host.

Array length [bits]           320         160         64
Performance [executions/s]    33 million  43 million  54 million

---

One more optimazation x % 32 == x & 31 but I am unable to meassure a performance gain. Because of only 10.000.000 iterations in my test the fluctuations are quite high. And I am running in VirtualPC making the situation even more unpredictable.

Answer 4

I was bored enough to try doing it with a char array and using Convert.ToUInt32(string, int) to convert to a uint from base 2.

uint Range(int l, int h)
{
  char[] buffer = new char[h];
  for (int i = 0; i < buffer.Length; i++)
  {
    buffer[i] = i < h - l ? '1' : '0';
  }
  return Convert.ToUInt32(new string(buffer), 2);
}

A simple benchmark shows that my method is about 5% faster than Angrey Jim's (even if you replace second Pow with a bit shift.)

It is probably the easiest to convert to producing a uint array if the upper bound is too big to fit into a single int. It's a little cryptic but I believe it works.

uint[] Range(int l, int h)
{
  char[] buffer = new char[h];
  for (int i = 0; i < buffer.Length; i++)
  {
    buffer[i] = i < h - l ? '1' : '0';
  }

  int bitsInUInt = sizeof(uint) * 8;
  int numNeededUInts = (int)Math.Ceiling((decimal)buffer.Length /
                                         (decimal)bitsInUInt);
  uint[] uints = new uint[numNeededUInts];
  for (int j = uints.Length - 1, s = buffer.Length - bitsInUInt;
       j >= 0 && s >= 0;
       j--, s -= bitsInUInt)
  {
    uints[j] = Convert.ToUInt32(new string(buffer, s, bitsInUInt), 2);
  }

  int remainder = buffer.Length % bitsInUInt;
  if (remainder > 0)
  {
    uints[0] = Convert.ToUInt32(new string(buffer, 0, remainder), 2);
  }

  return uints;
}

Answer 5

Well, I really need to get the fastest possible implementation here. I figure the answer probably involves creating some tables with pre-calculated mask values like so:

MaxTable:
    0       0000 0000 0000 0001    0x0001
    1       0000 0000 0000 0011    0x0003
    2       0000 0000 0000 0111    0x0007
    3       0000 0000 0000 1111    0x000F
    4       0000 0000 0001 1111    0x001F
    5       0000 0000 0011 1111    0x003F
    6       0000 0000 0111 1111    0x007F
    7       0000 0000 1111 1111    0x00FF
    8       0000 0001 1111 1111    0x01FF
    9       0000 0011 1111 1111    0x03FF
    10      0000 0111 1111 1111    0x07FF
    11      0000 1111 1111 1111    0x0FFF
    12      0001 1111 1111 1111    0x1FFF 
    13      0011 1111 1111 1111    0x3FFF
    14      0111 1111 1111 1111    0x7FFF
    15      1111 1111 1111 1111    0xFFFF

MinTable:
    0       0000 0000 0000 0000    0x0000
    1       0000 0000 0000 0001    0x0001
    2       0000 0000 0000 0011    0x0003
    3       0000 0000 0000 0111    0x0007
    4       0000 0000 0000 1111    0x000F
    5       0000 0000 0001 1111    0x001F
    6       0000 0000 0011 1111    0x003F
    7       0000 0000 0111 1111    0x007F
    8       0000 0000 1111 1111    0x00FF
    9       0000 0001 1111 1111    0x01FF
    10      0000 0011 1111 1111    0x03FF
    11      0000 0111 1111 1111    0x07FF
    12      0000 1111 1111 1111    0x0FFF
    13      0001 1111 1111 1111    0x1FFF
    14      0011 1111 1111 1111    0x3FFF
    15      0111 1111 1111 1111    0x7FFF

I still need to figure this out, but as a simple implementation for handling values no larger than 31 I can do:

MaxTable[x2] ^= MinTable[x1]

It would be trivial to use just one table instead, but I figure I save a decrement's worth of execution time without it. I'll try to figure out how to use this method for a true bit array next.

Answer 6

Try this:

uint x1 = 3;
uint x2 = 9;

int cbToShift = x2 - x1; // 6
int nResult = ((1 << cbToShift) - 1) << x1; 

/*
  (1<<6)-1 gives you 63 = 111111, then you shift it on 3 bits left
*/