When we use one of the built-in data types, like char or int, for processing bits, we run into the issue of having only a limited number of bits to play with. For example, an unsigned char can give us only 8 bits and an unsigned int can give us only 32 bits (on a 32-bit machine). This is okay as long as we need only a limited number of bits. Sometimes, that is not enough. Often applications might need to handle hundreds of bits and using an int or even a double would no longer suffice. We are going to need a bigger boat!
The workaround for such cases is to use a bitmap. Also known as a bit array, a bitmap allows us to have an array, where each element can hold a built-in storage like an integer or a char and each of these array elements store bit-information. Thus, if we have a bitmap array with 100 char elements, then we have a total of 800 bits since each char element can in turn store 8 bits. A bitmap allows us to manipulate (set or clear) any bit out of these 800 bits as if it were one single variable.
Bitmaps can support all bit-related operations like setting a bit, clearing a bit, and checking if a bit is set, and many more. Since a bitmap stores individual bits in its array elements, each of these operations need to find two offsets. First, the array index of the element that houses the bit. Second, the position of the bit within that array element.
In the above example of 800 bits bitmap, if we wanted to set the 100th bit, then we would need to locate the array offset first. To locate array offset, we can divide the specified bit with the size of the array element, in this case, 8. Thus, the 100th bit would be present in the 100/8 or in the 12th element. Next, to locate the offset within that element, we can use the modulo of the specified bit with the size of the array element. In this case, that would be 100 % 8, which is 4. So, the 100th bit would be the 4th bit sitting in the 12th element.
Next, we provide an example to help us understand bitmaps a little better. The example (provided below) uses an array (bitStream) of unsigned chars and has a total of 6 chars. Thus, this storage equals 48 bits. The implementation offers 4 bitmap operations: setBitmapArray() to set the kth bit (from right-end), clearBitmapArray() to clear the kth bit (from right-end), checkBitmapArray() to check if the kth bit (from right-end) is set or not, and printBitmapArray() to print all bits of the bitmap. Here is the example:
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define NUM_OF_BYTES 6
#define TOTAL_LEN (NUM_OF_BYTES * 8 + 3 + 1)
#define BYTE_COUNT(x) ((x) / 8)
#define BIT_COUNT(x) ((x) % 8)
char binary_string[TOTAL_LEN];
unsigned char *bitStream = NULL;
char *printBitmapArray () {
int i, j, temp;
int index = TOTAL_LEN - 2;
while (i <= TOTAL_LEN) {
binary_string[i++] = '0';
}
binary_string[TOTAL_LEN-1] = '\0';
for (i = 0; i < NUM_OF_BYTES; i++) {
for (j = 0; j < 8; j++) {
if ((1 << j) & bitStream[i])
binary_string[index] = '1';
index--;
}
binary_string[index--] = ' ';
}
return binary_string;
}
void setBitmapArray (int loc) {
if (loc < 1) return;
bitStream[BYTE_COUNT(loc-1)] |= (1 << BIT_COUNT(loc-1));
}
bool checkBitmapArray (int loc) {
if (loc < 1) return;
if (bitStream[BYTE_COUNT(loc-1)] & (1 << BIT_COUNT(loc-1)))
return true;
else
return false;
}
void clearBitmapArray (int loc) {
if (loc < 1) return;
bitStream[BYTE_COUNT(loc-1)] &= ~(1 << BIT_COUNT(loc-1));
}
void initBitmapArray(int num_of_bytes) {
if (!bitStream) {
bitStream = (unsigned char *)malloc(sizeof(char *) * NUM_OF_BYTES);
if (!bitStream) return;
}
bzero(bitStream, NUM_OF_BYTES);
}
int main() {
initBitmapArray(NUM_OF_BYTES);
setBitmapArray(4);
printf("[Set 4th bit] %s\n", printBitmapArray());
printf("[Check 4th bit] %d\n", checkBitmapArray(4));
setBitmapArray(12);
printf("[Set 12th bit] %s\n", printBitmapArray());
printf("[Check 12th bit] %d\n", checkBitmapArray(12));
clearBitmapArray(12);
printf("[Clear 12th bit] %s\n", printBitmapArray());
printf("[Check 12th bit] %d\n", checkBitmapArray(12));
clearBitmapArray(4);
printf("[Clear 4th bit] %s\n", printBitmapArray());
printf("[Check 4th bit] %d\n", checkBitmapArray(4));
return 0;
}
The output of the example shows that now we have 6 bytes of storage available and the set, clear, and verify operations work as if this were a regular storage like an integer or a char.
[Set 4th bit] 000000 00000000 00000000 00000000 00000000 00001000 [Check 4th bit] 1 [Set 12th bit] 000000 00000000 00000000 00000000 00001000 00001000 [Check 12th bit] 1 [Clear 12th bit] 000000 00000000 00000000 00000000 00000000 00001000 [Check 12th bit] 0 [Clear 4th bit] 000000 00000000 00000000 00000000 00000000 00000000 [Check 4th bit] 0
Please note that the example uses an unsigned char as individual storage types, but one can also use an unsigned integer to do the same. However, this may not not buy as a whole lot since we can also add more number of chars in the above example. Thus, if we want a bitmap of 800 bits, then we can either use 100 unsigned chars or use 25 unsigned ints.