With the bit operators discussed previously, you can proceed to perform all sorts of sophisticated operations on bits. Bit operations are frequently performed on data items that contain packed information. Just as a short int can be used to conserve memory space on some computers, so can you pack information into the bits of a byte or word if you do not need to use the entire byte or word to represent the data. For example, flags that are used for a Boolean true or false condition can be represented in a single bit on a computer. Declaring a char variable that will be used as a flag uses eight bits (one byte) on most computers, and a _Bool variable is likely to use eight bits as well. In addition, if you need to store many flags inside a large table, the amount of memory that is wasted could become significant.
Two methods are available in C that can be used to pack information together to make better use of memory. One way is to simply represent the data inside a normal int, for example, and then access the desired bits of the int using the bit operators described in the previous sections. Another way is to define a structure of packed infor- mation using a C construct known as a bit field.
To illustrate how the first method can be used, suppose you want to pack five data values into a word because you have to maintain a very large table of these values in memory. Assume that three of these data values are flags, which you call f1, f2, and f3; the fourth value is an integer called type, which ranges from 1 to 255; and the final value is an integer called index, which ranges from 0 to 100,000.
Storing the values of the flags f1, f2, and f3 only requires three bits of storage, one bit for the true/false value of each flag. Storing the value of the integer type, which ranges from 1 to 255, requires eight bits of storage. Finally, storing the value of the inte- ger index, which can assume a value from 0 to 100,000, requires 18 bits. Therefore, the total amount of storage needed to store the five data values, f1, f2, f3, type, and index, is 29 bits.You could define an integer variable that could be used to contain all five of these values, as in
unsigned int packed_data;
and could then arbitrarily assign specific bits or fields inside packed_data to be used to store the five data values. One such assignment is depicted in Figure 12.1, which assumes that the size of packed_data is 32 bits.
Note that packed_data has three unused bits.You can now apply the correct sequence of bit operations to packed_data to set and retrieve values to and from the various fields of the integer. For example, you can set the type field of packed_data to 7 by shifting the value 7 the appropriate number of places to the left and then ORing it into packed_data:
packed_data |= 7 << 18;
or you can set the type field to the value n, where n is between 0 and 255, by the statement
packed_data |= n << 18;
To ensure that n is between 0 and 255, you can AND it with 0xff before it is shifted.
Of course, the preceding statements only work if you know that the type field is zero; otherwise, you must zero it first by ANDing it with a value (frequently called a mask) that consists of 0s in the eight bit locations of the type field and 1s everywhere else:
packed_data &= 0xfc03ffff;
To save yourself the bother of having to explicitly calculate the preceding mask, and also to make the operation independent of the size of an integer, you could instead use the following statement to set the type field to zero:
packed_data &= ~(0xff << 18);
Combining the statements described previously, you can set the type field of packed_data to the value contained in the eight low-order bits of n, irrespective of any value previously stored in this field, with the following statement:
packed_data = (packed_data & ~(0xff << 18)) | ((n & 0xff) << 18);
In the preceding code, some of the parentheses are superfluous but were added to aid readability.
You can see how complex the preceding expression is for accomplishing the relatively simple task of setting the bits in the type field to a specified value. Extracting a value from one of these fields is not as bad: The field can be shifted into the low-order bits of the word and then ANDed with a mask of the appropriate bit length. So, to extract the type field of packed_data and assign it to n, the statement
n = (packed_data >> 18) & 0xff;
does the trick.
The C language does provide a more convenient way of dealing with bit fields. This method uses a special syntax in the structure definition that allows you to define a field of bits and assign a name to that field. Whenever the term “bit fields” is applied to C, it is this approach that is referenced.
To define the bit field assignments previously mentioned, you can define a structure called packed_struct, for example, as follows:
struct packed_struct
{
unsigned int :3;
unsigned int f1:1;
unsigned int f2:1;
unsigned int f3:1;
unsigned int type:8;
unsigned int index:18;
};
The structure packed_struct is defined to contain six members. The first member is not named. The :3 specifies three unnamed bits. The second member, called f1, is also an unsigned int. The :1 that immediately follows the member name specifies that this member is to be stored in one bit. The flags f2 and f3 are similarly defined as being a single bit in length. The member type is defined to occupy eight bits, whereas the mem- ber index is defined as being 18 bits long.
The C compiler automatically packs the preceding bit field definitions together. The nice thing about this approach is that the fields of a variable defined to be of type packed_struct can now be referenced in the same convenient way normal structure members are referenced. So, if you declare a variable called packed_data as follows:
struct packed_struct packed_data;
you could easily set the type field of packed_data to 7 with the simple statement
packed_data.type = 7;
or you could set this field to the value of n with the similar statement
packed_data.type = n;
In this last case, you need not worry about whether the value of n is too large to fit into the type field; only the low-order eight bits of n will be assigned to packed_data.type.
Extraction of the value from a bit field is also automatically handled, so the statement
n = packed_data.type;
extracts the type field from packed_data (automatically shifting it into the low-order bits as required) and assigns it to n.
Bit fields can be used in normal expressions and are automatically converted to inte- gers. So the statement
i = packed_data.index / 5 + 1;
is perfectly valid, as is
if ( packed_data.f2 )
…
which tests if flag f2 is true or false. One thing worth noting about bit fields is that there is no guarantee whether the fields are internally assigned from left to right or from right to left. This should not present a problem unless you are dealing with data that was creat- ed by a different program or by a different machine. In such cases, you must know how the bit fields are assigned and make the declarations appropriately.You could have defined the structure packed_struct as
struct packed_struct
{
unsigned int index:18;
unsigned int type:8;
unsigned int f3:1;
unsigned int f2:1;
unsigned int f1:1;
unsigned int :3;
};
to achieve the same representation on a machine that assigns fields from right to left as depicted in Figure 12.1. Never make any assumptions about how structure members— whether they contain bit field members or not—are stored.
You can also include normal data types within a structure that contains bit fields. So if you want to define a structure that contained an int,a char, and two one-bit flags, the following definition is valid:
struct table_entry
{
int count;
char c;
unsigned int f1:1;
unsigned int f2:1;
};
Certain points are worth mentioning with respect to bit fields. They can only be declared to be of integer or _Bool type. If just int is used in the declaration, it’s imple- mentation dependent whether this is interpreted as a signed or unsigned value. To play it safe, use the explicit declarations signed int or unsigned int.A bit field cannot be dimensioned; that is, you cannot have an array of fields, such as flag:1[5]. Finally, you cannot take the address of a bit field, and, therefore, there is obviously no such thing as a type “pointer to bit field.”
Bit fields are packed into units as they appear in the structure definition, where the size of a unit is defined by the implementation and is most likely a word.
The C compiler does not rearrange the bit field definitions to try to optimize storage space.
A final point concerning the specification of fields concerns the special case of an unnamed field of length 0. This can be used to force alignment of the next field in the structure at the start of a unit boundary.
This concludes the discussion of bit operations in C.You can see how much power and flexibility the C language provides for the efficient manipulation of bits. Operators are conveniently provided in the language for performing bitwise AND, Inclusive-OR, Exclusive-OR, ones complement, and left and right shift operations. A special bit field format enables you to allocate a specified number of bits for a data item and to easily set and retrieve its value without having to use masking and shifting.
See Chapter 14, ”More on Data Types,” for a discussion on what happens when you perform bitwise operations between two values of differing integral types, for example between an unsigned long int and a short int.
Before proceeding to the next chapter, try the following exercises to test your under-standing of bit operations in C.
Source: Kochan Stephen G. (2004), Programming in C: A Complete Introduction to the C Programming Language, Sams; Subsequent edition.