Large bit arrays in C

Our OS professor mentioned that for assigning a process id to a new process, the kernel incrementally searches for the first zero bit in a array of size equivalent to the maximum number of processes(~32,768 by default), where an allocated process id has 1 stored in it.

As far as 开发者_Python百科I know, there is no bit data type in C. Obviously, there's something I'm missing here.

Is there any such special construct from which we can build up a bit array? How is this done exactly?

More importantly, what are the operations that can be performed on such an array?

Bit arrays are simply byte arrays where you use bitwise operators to read the individual bits.

Suppose you have a 1-byte char variable. This contains 8 bits. You can test if the lowest bit is true by performing a bitwise AND operation with the value 1, e.g.

 char a = /*something*/;
 if (a & 1) {
    /* lowest bit is true */
 }

Notice that this is a single ampersand. It is completely different from the logical AND operator &&. This works because a & 1 will "mask out" all bits except the first, and so a & 1 will be nonzero if and only if the lowest bit of a is 1. Similarly, you can check if the second lowest bit is true by ANDing it with 2, and the third by ANDing with 4, etc, for continuing powers of two.

So a 32,768-element bit array would be represented as a 4096-element byte array, where the first byte holds bits 0-7, the second byte holds bits 8-15, etc. To perform the check, the code would select the byte from the array containing the bit that it wanted to check, and then use a bitwise operation to read the bit value from the byte.

As far as what the operations are, like any other data type, you can read values and write values. I explained how to read values above, and I'll explain how to write values below, but if you're really interested in understanding bitwise operations, read the link I provided in the first sentence.

How you write a bit depends on if you want to write a 0 or a 1. To write a 1-bit into a byte a, you perform the opposite of an AND operation: an OR operation, e.g.

 char a = /*something*/;
 a = a | 1; /* or a |= 1 */

After this, the lowest bit of a will be set to 1 whether it was set before or not. Again, you could write this into the second position by replacing 1 with 2, or into the third with 4, and so on for powers of two.

Finally, to write a zero bit, you AND with the inverse of the position you want to write to, e.g.

 char a = /*something*/;
 a = a & ~1; /* or a &= ~1 */

Now, the lowest bit of a is set to 0, regardless of its previous value. This works because ~1 will have all bits other than the lowest set to 1, and the lowest set to zero. This "masks out" the lowest bit to zero, and leaves the remaining bits of a alone.

A struct can assign members bit-sizes, but that's the extent of a "bit-type" in 'C'.

struct int_sized_struct {
   int foo:4;
   int bar:4;
   int baz:24;
};

The rest of it is done with bitwise operations. For example. searching that PID bitmap can be done with:

extern uint32_t *process_bitmap;
uint32_t *p = process_bitmap;
uint32_t bit_offset = 0;
uint32_t bit_test;

/* Scan pid bitmap 32 entries per cycle. */
while ((*p & 0xffffffff) == 0xffffffff) {
  p++;
}

/* Scan the 32-bit int block that has an open slot for the open PID */
bit_test = 0x80000000;
while ((*p & bit_test) == bit_test) {
   bit_test >>= 1;
   bit_offset++;
}
pid = (p - process_bitmap)*8 + bit_offset;

This is roughly 32x faster than doing a simple for loop scanning an array with one byte per PID. (Actually, greater than 32x since more of the bitmap is will stay in CPU cache.)

see http://graphics.stanford.edu/~seander/bithacks.html

No bit type in C, but bit manipulation is fairly straight forward. Some processors have bit specific instructions which the code below would nicely optimize for, even without that should be pretty fast. May or may not be faster using an array of 32 bit words instead of bytes. Inlining instead of functions would also help performance.

If you have the memory to burn just use a whole byte to store one bit (or whole 32 bit number, etc) greatly improve performance at the cost of memory used.

unsigned char data[SIZE];

unsigned char get_bit ( unsigned int offset )
{
    //TODO: limit check offset
    if(data[offset>>3]&(1<<(offset&7))) return(1);
    else return(0);
}
void set_bit ( unsigned int offset, unsigned char bit )
{
    //TODO: limit check offset
    if(bit) data[offset>>3]|=1<<(offset&7);
    else    data[offset>>3]&=~(1<<(offset&7));
}