Programming in C (Fourth Edition) (2015)

---

The function first ensures that the shift count, n, is valid. The code

if ( n > 0 )
n = n % 32;
else
n = -(-n % 32);

checks first to see if n is positive. If it is, the value of n modulo the size of an int (assumed to be 32 in this example) is calculated and stored back inside n. This places the shift count in the range of 0 through 31. If n is negative, its value is negated before the modulus operator is applied. This is done because C does not define the sign of the result of applying the modulus operator to a negative value. Your machine can produce either a positive or negative result. By negating the value first, you ensure the result is positive. You then apply the unary minus operator to the result to turn it negative again; that is, within the range of values −31 through 0.

If the adjusted shift count is 0, the function simply assigns value to result. Otherwise, it proceeds with the rotation.

An n-bit rotation to the left is divided into three steps by the function. First, the n leftmost bits of value are extracted and shifted to the right. This is done by shifting value to the right by the size of an int (in our case, 32) minus n. Next, value is shifted n bits to the left, and finally, the extracted bits are ORed back in. A similar procedure is followed to rotate value to the right.

In the main() routine, note the use of hexadecimal notation for a change. The first call to the rotate() function specifies that the value of w1 is to be rotated eight bits to the left. As can be seen from the program’s output, the hexadecimal value cdef00ab is returned by the rotate()function, which is in fact abcdef00 rotated to the left eight bits.

The second call to the rotate() function has the effect of rotating the value of w1 16 bits to the right.

The next two calls to the rotate() function do similar things with the value of w2 and are fairly self-explanatory. The next-to-last call to rotate() specifies a rotate count of 0. The program’s output verifies that in such a case the function simply returns the value unchanged.

The final call to rotate() specifies a left rotate 44 places. This has the net effect of rotating the value left 12 bits (44 % 32 is 12).

Bit Fields

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 information 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 integer 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 11.1, which assumes that the size of packed_data is 32 bits.

Figure 11.1 Bit field assignments in packed_data.

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 member 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 integers. 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 created 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:9;
unsigned int type:4;
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 11.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 implementation dependent whether this is interpreted as a signed or unsigned value. To play it safe, use the explicit declarationssigned 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 13, ”Extending Data Types with the Enumerated Data Type, Type Definitions, and Data Type Conversions,” for a discussion on what happens when you perform bitwise operations between two values of differing integral types, for example between an unsigned long intand a short int.

Before proceeding to the next chapter, try the following exercises to test your understanding of bit operations in C.

Exercises

1. Type in and run the four programs presented in this chapter. Compare the output produced by each program with the output presented after each program in the text.

2. Write a program that determines whether your particular computer performs an arithmetic or a logical right shift.

3. Given that the expression ~0 produces an integer that contains all 1s, write a function called int_size() that returns the number of bits contained in an int on your particular machine.

4. Using the result obtained in exercise 3, modify the rotate() function from Program 11.4 so that it no longer makes any assumptions about the size of an int.

5. Write a function called bit_test() that takes two arguments: an unsigned int and a bit number n. Have the function return 1 bit number n if it is on inside the word, and 0 if it is off. Assume that bit number 0 references the leftmost bit inside the integer. Also write a corresponding function called bit_set() that takes two arguments: an unsigned int and a bit number n. Have the function return the result of turning bit n on inside the integer.

6. Write a function called bitpat_search() that looks for the occurrence of a specified pattern of bits inside an unsigned int. The function should take three arguments and should be called as shown:

bitpat_search (source, pattern, n)

The function searches the integer source, starting at the leftmost bit, to see if the rightmost n bits of pattern occur in source. If the pattern is found, have the function return the number of the bit at which the pattern begins, where the leftmost bit is bit number 0. If the pattern is not found, then have the function return −1. So, for example, the call

index = bitpat_search (0xe1f4, 0x5, 3);

causes the bitpat_search() function to search the number 0xe1f4 ( = 1110 0001 1111 0100 binary ) for the occurrence of the three-bit pattern 0x5 (= 101 binary). The function returns 11 to indicate that the pattern was found in the source beginning with bit number 11.

Make certain that the function makes no assumptions about the size of an int (see exercise 3 in this chapter).

7. Write a function called bitpat_get() to extract a specified set of bits. Have it take three arguments: the first an unsigned int, the second an integer starting bit number, and the third a bit count. Using the convention that bit numbering starts at 0 with the leftmost bit, extract the specified number of bits from the first argument and return the result. So the call

bitpat_get (x, 0, 3)

extracts the three leftmost bits from x. The call

bitpat_get (x, 3, 5)

extracts five bits starting with the fourth bit in from the left.

8. Write a function called bitpat_set() to set a specified set of bits to a particular value. The function should take four arguments: a pointer to an unsigned int in which the specified bits are to be set; another unsigned int containing the value to which the specified bits are to be set, right adjusted in the unsigned int; a third int that specifies the starting bit number (with the leftmost bit numbered 0); and a fourth int specifying the size of the field. So the call

bitpat_set (&x, 0, 2, 5);

has the effect of setting the five bits contained in x, beginning with the third bit from the left (bit number 2), to 0. Similarly, the call

bitpat_set (&x, 0x55u, 0, 8);

sets the eight leftmost bits of x to hexadecimal 55.

Make no assumptions about the particular size of an int (refer to exercise 3 in this chapter).