Practical C Programming, 3rd Edition (2011)

---

^[14^] Soon after I discovered the bug illustrated by this program, I told my office mate, “I now understand the difference between and and and and,” and he understood me. How we understand language has always fascinated me, and the fact that I could utter such a sentence and have someone understand it without trouble amazed me.

Bitwise or (|)

The inclusive or operator (also known as just the or operator) compares its two operands and if one or the other bit is a one, the result is a one. Table 11-4 lists the truth table for the or operator.

Table 11-4. or Operator

Bit1	Bit2	Bit1 | Bit2
0	0	0
0	1	1
1	0	1
1	1	1

On a byte, this would be:

i1=0x47 01000111

| i2=0x53 01010011

_______________________

= 0x57 01010111

The Bitwise Exclusive or (^)

The exclusive or (also known as xor) operator results in a one when either of its two operands is a one, but not both. The truth table for the exclusive or operator is listed in Table 11-5.

Table 11-5. Exclusive or

Bit1	Bit2	Bit1 ^ Bit2
0	0	0
0	1	1
1	0	1
1	1	0

On a byte this would be:

i1=0x47 01000111

^ i2=0x53 01010011

_______________________

= 0x14 00010100

The Ones Complement Operator (Not) (~)

The not operator (also called the invert operator, or bit flip) is a unary operator that returns the inverse of its operand as shown in Table 11-6.

Table 11-6. not Operator

Bit	~Bit
0	1
1	0

On a byte, this is:

c= 0x45 01000101

______________________

~c= 0xBA 10111010

The Left- and Right-Shift Operators (<<, >>)

The left-shift operator moves the data to the left a specified number of bits. Any bits that are shifted out the left side disappear. New bits coming in from the right are zeros. The right shift does the same thing in the other direction. For example:

	c=0x1C	00011100
c << 1	c=0x38	00111000
c >> 2	c=0x07	00000111

Shifting left by one (x << 1) is the same as multiplying by 2 (x * 2). Shifting left by two (x << 2) is the same as multiplying by 4 (x * 4, or x * 22). You can see a pattern forming here. Shifting left by n places is the same as multiplying by 2n. Why shift instead of multiply? Shifting is faster than multiplication, so:

i = j << 3; /* Multiple j by 8 (2**3) */

is faster than:

i = j * 8;

Or it would be faster if compilers weren’t smart enough to turn “multiply by power of two” into “shift.”

Many clever programmers use this trick to speed up their programs at the cost of clarity. Don’t you do it. The compiler is smart enough to perform the speedup automatically. The result of putting in a shift gains you nothing at the expense of clarity.

The left-shift operator multiplies; the right-shift operator divides. So:

q = i >> 2;

is the same as:

q = i / 4;

Again, this trick is clever but should not be used in modern code.

Right-Shift Details

Right shifts are particularly tricky. When a variable is shifted to the right, C needs to fill the space on the left-hand side with something. For signed variables, C uses the value of the sign bit. For unsigned variables, C uses zero. Table 11-7 illustrates some typical shifts.

Table 11-7. Right-Shift Examples

	signed char	signed char	unsigned char
Expression	9 >> 2	-8 >> 2	248 >> 2
Binary Value >> 2	0000 1001 >> 2	1111 1000 >> 2	1111 1000 >> 2
Result	??00 0010	??11 1110	??11 1110
Fill	Sign Bit (0)	Sign Bit (1)[a]	Zero
Final Result (Binary)	0000 0010	1111 1110	0011 1110
Final Result (short int)	2	-2	62
[a] The ANSI standard specifies that right shifts may be arithmetic (sign bit fill) or logical (zero bit fill). Almost all compilers use the arithmetic right shift.

Setting, Clearing, and Testing Bits

A character (char) contains eight bits. Each of these can be treated as a separate flag.

Bit operations can be used to pack eight single-bit values in a single byte. For example, suppose we are writing a low-level communications program. We are going to store the characters in an 8k buffer for later use. With each character we will also store a set of status flags. The flags are listed in Table 11-8.

Table 11-8. Communications Status Values

Name	Description
ERROR	True if any error is set.
FRAMING_ERROR	A framing error occurred for this character.
PARITY_ERROR	Character had the wrong parity.
CARRIER_LOST	The carrier signal went down.
CHANNEL_DOWN	Power was lost on the communication device.

We could store each of these flags in its own character variable. That format would mean that for each character buffered, we would need five bytes of status storage. For a large buffer, that storage adds up. If we instead assign each status flag its own bit within an 8-bit status character, we cut our storage requirements down to one-fifth of our original need.

We assign our flags the bit numbers listed in Table 11-9.

Table 11-9. Bit Assignments

Bit	Name
0	ERROR
1	FRAMING_ERROR
2	PARITY_ERROR
3	CARRIER_LOST
4	CHANNEL_DOWN

Bits are numbered 76543210 by convention, as seen in Table 11-9. In the Bit numbers table, we have bits 4 and 1 set.

Bit numbers
7	6	5	4	3	2	1	0
0	0	0	1	0	0	1	0

The constants for each bit are defined in Table 11-10.

Table 11-10. Bit Values

Bit	Binary value	Hexadecimal constant
7	10000000	0x80
6	01000000	0x40
5	00100000	0x20
4	00010000	0x10
3	00001000	0x08
2	00000100	0x04
1	00000010	0x02
0	00000001	0x01

The definitions could be:

/* True if any error is set */

const int ERROR = 0x01;

/* A framing error occurred for this character */

const int FRAMING_ERROR = 0x02;

/* Character had the wrong parity */

const int PARITY_ERROR = 0x04;

/* The carrier signal went down */

const int CARRIER_LOST = 0x08;

/* Power was lost on the communication device */

const int CHANNEL_DOWN = 0x10;

This method of defining bits is somewhat confusing. Can you tell (without looking at the table) which bit number is represented by the constant 0x10? Table 11-11 shows how we can use the left-shift operator (<<) to define bits.

Table 11-11. Left-Shift Operator and Bit Definition

C Representation	Base 2 Equivalent	Result (Base 2)	Bit Number
1<<0	00000001 << 0	00000001	Bit 0
1<<1	00000001 << 1	00000010	Bit 1
1<<2	00000001 << 2	00000100	Bit 2
1<<3	00000001 << 3	00001000	Bit 3
1<<4	00000001 << 4	00010000	Bit 4
1<<5	00000001 << 5	00100000	Bit 5
1<<6	00000001 << 6	01000000	Bit 6
1<<7	00000001 << 7	10000000	Bit 7

Although you cannot easily tell what bit is represented by 0x10, you can easily tell what bit is meant by 1<<4.

So our flags can be defined as:

/* True if any error is set */

const int ERROR = (1<<0);

/* A framing error occurred for this character */

const int FRAMING_ERROR = (1<<1);

/* Character had the wrong parity */

const int PARITY_ERROR = (1<<2);

/* The carrier signal went down */

const int CARRIER_LOST = (1<<3);

/* Power was lost on the communication device */

const int CHANNEL_DOWN = (1<<4);

Now that we have defined the bits, we can manipulate them. To set a bit, use the | operator. For example:

char flags = 0; /* start all flags at 0 */

flags |= CHANNEL_DOWN; /* Channel just died */

To test a bit, we use the & operator to mask out the bits:

if ((flags & ERROR) != 0)

printf("Error flag is set\n");

else

printf("No error detected\n");

Clearing a bit is a harder task. Suppose we want to clear the bit PARITY_ERROR. In binary this bit is 00000100. We want to create a mask that has all bits set except for the bit we want to clear (11111011). This step is done with the not operator (~). The mask is then anded with the number to clear the bit.

PARITY_ERROR 00000100

~PARITY_ERROR 11111011

flags 00000101

_______________________________________

flags & ~PARITY_ERROR 00000001

In C, you should use:

flags &= ~PARITY_ERROR; /* Who cares about parity */

Question 11-1: In Example 11-2, the HIGH_SPEED flag works, but the DIRECT_CONNECT flag does not. Why? (Click here for the answer Section 11.9)

Example 11-2. high/high.c

#include <stdio.h>

const int HIGH_SPEED = (1<<7); /* modem is running fast */

/* we are using a hardwired connection */

const int DIRECT_CONNECT = (1<<8);

char flags = 0; /* start with nothing */

int main()

{

flags |= HIGH_SPEED; /* we are running fast */

flags |= DIRECT_CONNECT;/* because we are wired together */

if ((flags & HIGH_SPEED) != 0)

printf("High speed set\n");

if ((flags & DIRECT_CONNECT) != 0)

printf("Direct connect set\n");

return (0);

}

Bitmapped Graphics

More and more computers now have graphics. For the PC, there are graphics devices like EGA and VGA cards. UNIX offers the X windowing system.

In bitmapped graphics, each pixel on the screen is represented by a single bit in memory. For example, Figure 11-2 shows a 14-by-14 bitmap as it appears on the screen, and enlarged so that you can see the bits.

Figure 11-2. Bitmap, actual size and enlarged

Suppose we have a small graphic device—a 16-by-16-pixel black-and-white display. We want to set the bit at 4,7. The bitmap for this device is shown as an array of bits in Figure 11-3.

Figure 11-3. Array of bits

But we have a problem. No data type exists for an array of bits in C. The closest we can come is an array of bytes. Our 16-by-16 array of bits now becomes a 2-by-16 array of bytes, as shown in Figure 11-4.

Figure 11-4. Array of bytes

Let’s see what we need to do to transform our x, y index to a byte_x, byte_y, bit_index, and bit.

The byte_y index is the same as the y index. That transformation is simple:

byte_y = y;

A byte contains 8 bits. So, in the X direction, our byte index is eight times our bit index. This transformation leaves us with the code:

byte_x = x / 8;

Now we need the bit index. The index starts out at 0, goes to 7, and then goes back to 0. This change gives us the code:

bit_index = x % 8;

Now to specify the bit itself. A bit index of zero indicates the left-most bit or the bit represented by 1000 0000₂ or 0x80. A bit index of 1 indicates the next-to-the-left-most bit 0100 0000₂ or 0x80 >> 1. So the bit we want is given by the expression:

bit = 0x80 >> bit_index;

The full algorithm looks like:

byte_y = y;

byte_x = x / 8;

bit_index = x % 8;

bit = 0x80 >> bit_index;

graphics[byte_x][byte_y] |= bit;

This algorithm can be condensed into a single macro:

#define set_bit(x, y) graphics[(x)/8][y] |= (0x80 >> ((x)%8))

For example, to set the pixel at bit number 4,7, we need to set the fourth bit of byte 0,7. Our macro would generate the statement:

bit_array[0][7] |= (0x80 >> (4));

Example 11-3 draws a diagonal line across the graphics array and then prints the array on the terminal.

Example 11-3. graph/graph.c

#include <stdio.h>

#define X_SIZE 40 /* size of array in X direction */

#define Y_SIZE 60 /* size of array in Y direction */

/*

* We use X_SIZE/8 because we pack 8 bits per byte

*/

char graphics[X_SIZE / 8][Y_SIZE]; /* the graphics data */

#define SET_BIT(x,y) graphics[(x)/8][y] |= (0x80 >>((x)%8))

int main()

{

int loc; /* current location we are setting */

void print_graphics(void); /* print the data */

for (loc = 0; loc < X_SIZE; ++loc)

SET_BIT(loc, loc);

print_graphics();

return (0);

}

/********************************************************

* print_graphics -- Prints the graphics bit array *

* as a set of X and .'s. *

********************************************************/

void print_graphics(void)

{

int x; /* current x BYTE */

int y; /* current y location */

unsigned int bit; /* bit we are testing in the current byte */

for (y = 0; y < Y_SIZE; ++y) {

/* Loop for each byte in the array */

for (x = 0; x < X_SIZE / 8; ++x) {

/* Handle each bit */

for (bit = 0x80; bit > 0; bit = (bit >> 1)) {

if ((graphics[x][y] & bit) != 0)

printf("X");

else

printf(".");

}

}

printf("\n");

}

}

The program defines a bitmapped graphic array:

char graphics[X_SIZE / 8][Y_SIZE]; /* the graphics data */

The constant X_SIZE/8 is used because we have X_SIZE bits across, which translates to X_SIZE/8 bytes.

The main for loop:

for (loc = 0; loc < X_SIZE; ++loc)

set_bit(loc, loc);

draws a diagonal line across the graphics array.

Because we do not have a bitmapped graphics device, we will simulate it with the subroutine print_graphics.

The loop:

for (y = 0; y < Y_SIZE; ++y) {

....

prints each row. The loop:

for (x = 0; x < X_SIZE / 8; ++x) {

...

goes through every byte in the row. There are eight bits in each byte handled by the loop:

for (bit = 0x80; bit > 0; bit = (bit >> 1))

which uses an unusual loop counter. This loop causes the variable bit to start with bit 7 (the left-most bit). For each iteration of the loop, the bit is moved to the right one bit by bit = (bit >> 1). When we run out of bits, the loop exits.

The loop counter cycles through:

Binary	Hex
0000 0000 1000 0000	0x80
0000 0000 0100 0000	0x40
0000 0000 0010 0000	0x20
0000 0000 0001 0000	0x10
0000 0000 0000 1000	0x08
0000 0000 0000 0100	0x04
0000 0000 0000 0010	0x02
0000 0000 0000 0001	0x01

Finally, at the heart of the loops is the code:

if ((graphics[x][y] & bit) != 0)

printf("X");

else

printf(".");

This code tests an individual bit and writes an “X” if it is set or a “.” if it is not.

Question 11-2: In Example 11-4 the first loop works, but the second one fails. Why? (Click here for the answer Section 11.9)

Example 11-4. loop/loop.c

#include <stdio.h>

int main()

{

short int i; /* Loop counter */

signed char ch; /* Loop counter of another kind */

/* Works */

for (i = 0x80; i != 0; i = (i >> 1)) {

printf("i is %x (%d)\n", i, i);

}

/* Fails */

for (ch = 0x80; ch != 0; ch = (ch >> 1)) {

printf("ch is %x (%d)\n", ch, ch);

}

return (0);

}

Answers

Answer 11-1: DIRECT_CONNECT is defined to be bit number 8 by the expression (1<<8); however, the eight bits in a character variable are numbered 76543210. Bit number 8 does not exist. A solution to this problem is to make flags a short integer with 16 bits.

Answer 11-2: The problem is that ch is a character (8 bits). The value 0x80 represented in 8 bits is 1000 0000₂. The first bit, the sign bit, is set. When a right shift is done on this variable, the sign bit is used for fill. So, 1000 0000₂>>1 is 1100 0000₂.

The variable i works even though it is signed because it is 16 bits long. So 0x80 in 16 bits is 0000 0000 1000 0000₂. Notice that the set bit is not near the sign bit.

The solution to our problem is to declare ch as an unsigned variable.

Programming Exercises

Exercise 11-1: Write a set of parameterized macros, clear_bit and test_bit, to go with the set_bit operation defined in Example 11-3. Write a main program to test these macros.

Exercise 11-2: Write a program to draw a 10-by-10 bitmapped square. You can borrow the code from Example 11-3 to print the results.

Exercise 11-3: Change Example 11-3 so that it draws a white line across a black background.

Exercise 11-4: Write a program that counts the number of bits set in an integer. For example, the number 5 (decimal), which is 0000000000000101 (binary), has two bits set.

Exercise 11-5: Write a program that takes a 32-bit integer (long int) and splits it into eight 4-bit values. (Be careful of the sign bit.)

Exercise 11-6: Write a program that will take the bits in a number and shift them to the left end. For example, 01010110 (binary) would become 11110000 (binary).