Bitmaps

A bitmap is a string of n binary digits that can be used to represent the status of n items. For example, suppose we have several resources, and the availability of each resource is indicated by the value of a binary digit: 0 means that the resource is available, while 1 indicates that it is unavailable (or vice-versa). The value of the ith position in the bitmap is associated with the ith resource. As an example, consider the bitmap shown below:
001011101

Resources 2, 4, 5, 6, and 8 are unavailable; resources 0, 1, 3, and 7 are available. The power of bitmaps becomes apparent when we consider their space efficiency. If we were to use an eight-bit Boolean value instead of a single bit, the resulting data structure would be eight times larger. Thus, bitmaps are commonly used when there is a need to represent the availability of a large number of resources. Disk drives provide a nice illustration. A medium-sized disk drive might be divided into several thousand individual units, called disk blocks. A bitmap can be used to indicate the availability of each disk block.

Data structures are pervasive in operating system implementations. Thus, we will see the structures discussed here, along with others, throughout this text as we explore kernel algorithms and their implementations.

Using a bitmap with n bits we can represent a set of non-negative integers in the range 0, . . ., n − 1 in the following way. For each bit in the bitmap, if the bit’s value is 1, we assume that the integer corresponding to the bit’s position in the bitmap is a member of the set. The rest of the bits represent integers that do not belong to the set.

Let us consider the sets A = {2, 3, 5} and B = {0, 2, 4}. With bitmaps of size eight these sets are written as 0011 0100 and 1010 1000, respectively. 


A = {2, 3, 5}---> 0011 0100
B = {0, 2, 4}---> 1010 1000

Bitwise operators can now be used to implement some common set theoretical operations. The bitwise AND and OR, for example, allow us to calculate the intersection and union, of two given sets, respectively. The unary bitwise not operator can be used to obtain a set’s complement. Some examples are:
 
A ∩ B = {2}
0011 0100 AND 1010 1000 = 0010 0000
 
A ∪ B = {0, 2, 3, 4, 5}
0011 0100 OR 1010 1000 = 1011 1100
 
A¯ = {0, 1, 4, 6, 7}
NOT 0011 0100 = 1100 1011

Other operations, such as set difference, can be implemented by combining these basic bitwise operators.

You can represent a list of distinct integers no larger than N using exactly N bits: if the integer i appears in your list, you set the ith bit to true. Bits for which there is no corresponding integers are set to false. For example, the integers 3, 4, 7 can be represented as 0001 1001. As another example, the integers 1, 2, 7 can be represented as 0110 0001.


{3, 4, 7}----> 0001 1001
{1, 2, 7}----> 0110 0001

Bitmaps are great to compute intersections and unions fast. For example, to compute the union between 3, 4, 7 and 1, 2, 7, all I need to do is compute the bitwise OR between 0001 1001 and 0110 0001 (=0111 1001) which a computer can do in one CPU cycle. Similarly, the intersection can be computed as the bitwise AND between 0001 1001 and 0110 0001 (=0000 0001).

Though it does not necessarily make use of fancy SSE instructions on your desktop, bitmaps are nevertheless an example of vectorization. That is, we use the fact that the processor can process several bits with one instruction.